非順序的TPC 軟判決迭代譯碼算法

盧 昊,張佳巖,馬永奎

0 引 言

Turbo乘積碼是一種兼顧誤碼率性能和譯碼復(fù)雜度的長碼[1],由兩個(gè)線性分組碼串行級(jí)聯(lián)得到。線性分組乘積碼的概念最早由Elias[2]提出,但在Turbo類譯碼器提出之前,分組乘積碼使用譯碼能力較差的硬輸入硬輸出(HIHO:Hard-Input/Hard-Output)譯碼器,其優(yōu)越的性能一直未被發(fā)現(xiàn)。直到1994年,Pyndiah以Chase算法[3]為基礎(chǔ),提出了一種適用于TPC(Turbo Product Code)碼的軟輸入軟輸出(SISO:Soft-Input/Soft-Output)Turbo類譯碼器,稱為Chase-Phydiah譯碼器。該譯碼器在具有良好譯碼性能的同時(shí)降低了算法復(fù)雜度。由此,TPC碼被廣泛研究應(yīng)用[4-8]。之后的研究多針對(duì)如何在不損失或有限損失誤碼率性能的前提下減少Chase-Phydiah譯碼器的復(fù)雜度。如文獻(xiàn)[9,10]中將Chase算法中候選碼字重新排序,以減小Chase算法的實(shí)現(xiàn)復(fù)雜度。文獻(xiàn)[11-13]估計(jì)信道情況,選擇合適的試探序列個(gè)數(shù),以減小候選碼字個(gè)數(shù),從而降低Chase算法復(fù)雜度。文獻(xiàn)[14,15]中提出HIHO譯碼器與SISO譯碼器混合使用,用HIHO譯碼器代替后幾次SISO譯碼從而減少譯碼復(fù)雜度。提高TPC誤碼性能的研究大多針對(duì)HIHO譯碼器[16,17],或利用其他最大后驗(yàn)(MAP:Maximum A Posteriori)算法作為TPC的子碼譯碼算法,但這常常伴隨譯碼復(fù)雜度的增加[18,19]。實(shí)際上,Chase-Phydiah譯碼器的復(fù)雜度不是制約其實(shí)用的原因,許多研究者已經(jīng)完成了Chase-Phydiah譯碼器的硬件設(shè)計(jì)與實(shí)現(xiàn)[20-22]。相比于關(guān)注度更高的Turbo卷積碼[23]和低密度奇偶校驗(yàn)碼[24],使用Chase-Phydiah譯碼器的TPC碼與香農(nóng)極限存在較大性能差異是TPC碼明顯的劣勢(shì)。如采用PL-log-MAP譯碼算法的Turbo卷積碼在高誤比特率情況下,所獲信噪比增益高達(dá)7～9 dB[25],而TPC碼在相同條件下,信噪比增益僅為4～6 dB。因此,如何能在不增加譯碼復(fù)雜度的情況下降低誤碼率是具有實(shí)際意義的研究方向。

2009年,Al-Dweik等[17]提出非順序(NS:Non-Sequential)譯碼。其思想是在第1次迭代時(shí),一旦接收信息到可用碼字的漢明距離大于閾值時(shí),則跳過此次譯碼,以避免引入額外錯(cuò)誤,從而提高譯碼性能。但NS譯碼思想僅用于HIHO迭代譯碼算法,而HIHO譯碼算法與SISO譯碼算法相比有2～3 dB的性能損失,無法體現(xiàn)出TPC碼的優(yōu)越性。筆者將NS譯碼思想推廣到SISO迭代譯碼算法,從而在幾乎不增加額外運(yùn)算的情況下,提高Chase-Phydiah譯碼器的誤碼率性能。

1 TPC編碼與譯碼

1.1 TPC編碼結(jié)構(gòu)

TPC碼可看做由兩個(gè)線性分組編碼編碼器串行級(jí)聯(lián)而成。其子碼Ci(i=1,2)可表示為(ni,ki,d(mii)n),其中ni,ki,d(mii)n分別表示碼長、信息位長度和最小漢明距離。TPC編碼結(jié)構(gòu)如圖1所示,其編碼過程如下:

圖1 TPC編碼結(jié)構(gòu)Fig.1 TPC code structure

1)將k1×k2信息序列排成k1×k2的矩陣;

2)用C2編碼k1行,得到k1×n2的矩陣;用C1編碼n2列,得到n1×n2編碼矩陣。

乘積碼P的參數(shù)為n=n1n2,k=k1k2,dmin=d(1)mind(2)min。由于C1,C2都是線性分組碼,因此每行或列都是C1或C2的可用碼字。筆者僅考慮C1,C2是相同擴(kuò)展BCH(Bose-Ray-Chaudhuri-Hocquenghem codes)碼的情況。因此,乘積碼P可表示為e BCH(n,k,dmin)2。

1.2 標(biāo)準(zhǔn)Chase-Phydiah譯碼算法

假定信息用BPSK(Binary Phase Shift Keying)調(diào)制方式,經(jīng)加性高斯白噪聲(AWGN:Additive White Gaussian Noise)信道到達(dá)接收端。設(shè)發(fā)送的碼字矩陣為X=[xi,j]n×n,xi,j∈{+1,-1},則X到二元域GF(2)的投影是P的一個(gè)可用碼字,其經(jīng)過AWGN信道后對(duì)應(yīng)的接收矩陣為R=[ri,j]n×n,AWGN噪聲矩陣為G=[gi,j]n×n,其中每個(gè)元素gi,j都是獨(dú)立的零均值正態(tài)分布隨機(jī)數(shù),則R=X+G。

設(shè)R′(m)和W(m)分別代表第m次譯碼(每次迭代含行、列兩次譯碼)的軟判決輸入矩陣和外信息量矩陣,則Chase-Phydiah譯碼過程可總結(jié)如下。

初始化。設(shè)定最大譯碼次數(shù)I(一次迭代過程包含行、列兩次譯碼),設(shè)定第m次譯碼的權(quán)重系數(shù)α(m)和可靠性系數(shù) β(m)(m=1,2,…,I)。第1次譯碼設(shè)置 m=1,輸入 R′(1)=R,中間緩存變量Rtemp=R。

SISO迭代過程如下。

1)用Chase-Phydiah算法計(jì)算外信息量W(m),定義W=(w1,…,wn)和R′=(r1′,…,r′n)分別對(duì)應(yīng)W(m)和R′(m)的某行,其計(jì)算過程如下。

① 用Chase-Ⅱ算法[3]譯碼R′,獲得候選碼字集合Ω。

②在集合Ω中搜索決定碼字D=(d1,…,dn)和競(jìng)爭碼字C=(c1,…,cn)。其中D是Ω中與R′歐氏距離最近的碼字,C是滿足C∈Ω,cj≠dj的碼字中與R′歐氏距離最近的碼字。對(duì)不同的j,C并不總是存在。在此規(guī)定,若對(duì)位置j不存在C,則稱j是無競(jìng)爭碼字位置。

③ 計(jì)算wj。若存在C,則

否則

2)令Rtemp←RTtemp,其中T代表矩陣轉(zhuǎn)置運(yùn)算。

3)計(jì)算下一次迭代譯碼器輸入R′(m+1)=Rtemp+α(m)W(m)T。

4)令m←m+1,若m＞I,則終止譯碼;否則,回到步驟1)重復(fù)譯碼過程。

上述譯碼過程可由圖2所示的基礎(chǔ)譯碼單元串聯(lián)得到。Pyndiah[1]指出,為減少α對(duì)乘積碼的依賴性,將所有由式(1)導(dǎo)出的外信息量的絕對(duì)值w的平均值歸一化到1。但若固定α=0.5,β=1,則不需對(duì)外信息量歸一化[10]。

圖2 TPC譯碼單元結(jié)構(gòu)框圖Fig.2 Block diagram of elementary block turbo decoder

2 NS-SISO迭代譯碼算法

TPC碼的行和列是相互聯(lián)系的,行譯碼器的輸出結(jié)果會(huì)影響列譯碼器的工作,反之亦然。因此一旦行(或列)錯(cuò)誤譯碼,會(huì)將錯(cuò)誤引入后續(xù)迭代過程中。這種錯(cuò)誤譯碼在HIHO譯碼器中會(huì)導(dǎo)致閉鏈錯(cuò)誤(close-chain error),在SISO譯碼器中,會(huì)在下一次譯碼過程中引入額外噪聲。

TPC碼NS-HIHO譯碼的思想是利用碼字可靠度將所有行(或列)分成可靠和不可靠兩類。每次行譯碼(列譯碼)僅對(duì)可靠行(或列)操作,以避免錯(cuò)誤譯碼。

2.1 碼字可靠度計(jì)算

NS譯碼首先要度量碼字的可靠度。在NS-HIHO譯碼中[8],Al-Dweik采用了將硬判決碼字可靠度用對(duì)數(shù)似然比形式定義,一個(gè)錯(cuò)α位的碼字,其可靠度為

其中Rh為接收碼字硬判決值,Dh為決定碼字,dmin為最小碼距,e為錯(cuò)誤個(gè)數(shù)。其中

其中Pch為信道錯(cuò)誤發(fā)生概率,n為碼長。

顯然,該定義式(3)表達(dá)形式復(fù)雜,不易計(jì)算。筆者采用Lu等[15]的硬判決碼字可靠度估計(jì)值表示碼字可靠度。硬判決碼字可靠度定義為

其中σ2為噪聲方差。在σ2→0時(shí),式(5)可近似為

其中Dm表示與Rh有第2小海綿距離的碼字,am代表Dm個(gè)數(shù)。假定信號(hào)調(diào)制方式為BPSK,經(jīng)方差為σ2的高斯白噪聲信道到達(dá)接收端,則式(4)可化為

當(dāng)σ2→0時(shí),式(5)可化為

其中dmin為子碼的最小碼距,e為錯(cuò)誤個(gè)數(shù)。由式(8)可知,碼字硬判決可靠度值僅和最小碼距與錯(cuò)誤個(gè)數(shù)有關(guān)。一旦TPC子碼最小碼距確定,γh可由錯(cuò)誤個(gè)數(shù)唯一確定,因此,可用錯(cuò)誤個(gè)數(shù)作為判斷是否進(jìn)行此次譯碼的標(biāo)準(zhǔn)。

2.2 SISO迭代譯碼的NS譯碼

參考HIHO譯碼中的NS譯碼算法,SISO的NS譯碼算法過程可概括為:

1)設(shè)定錯(cuò)誤個(gè)數(shù)閾值t;

2)若決定碼字D的硬判決錯(cuò)誤個(gè)數(shù)e＞t,則跳過后續(xù)譯碼過程,譯碼器外信息量輸出結(jié)果為零,否則正常譯碼。

特別注意,與HIHO中NS譯碼算法不同,SISO的NS譯碼過程不是僅在第1次譯碼時(shí)執(zhí)行,而是在每次譯碼時(shí)都被執(zhí)行。NS-SISO具體譯碼流程圖如圖3所示。

圖3 NS-SISO譯碼算法流程Fig.3 NS-SISO decoding algorithm flow diagrams

3 仿真結(jié)果與分析

首先討論不同閾值t對(duì)BER(Bit-Error-Rate)性能的影響,然后討論在選擇合適閾值的情況下,NS-SISO算法對(duì)迭代收斂性的影響。仿真結(jié)果將對(duì)比標(biāo)準(zhǔn)SISO譯碼算法與NS-SISO譯碼算法的誤碼性能。其他參數(shù)設(shè)置為p=4,I=8,α(m)=[0,0.2,0.3,0.5,0.7,0.9,1],β(m)=[0.2,0.4,0.6,0.8,1,1,1]。圖4反應(yīng)了在譯碼e BCH(64,57,4)2時(shí)不同閾值t對(duì)NS-SISO譯碼器性能影響。由圖4可知,t=2時(shí),閾值過小,這令部分Chase譯碼器可正確譯碼的碼字未能譯碼,使譯碼性能下降。t=3時(shí),NS-SISO譯碼器在Eb/N0處于3～3.4 dB之間時(shí),誤碼率性能增益最優(yōu),僅為傳統(tǒng)SISO算法的1/4左右。但在信噪比更高的區(qū)域性能不如t=4的情況。這是因?yàn)樾旁氡仍礁?Chase譯碼器的譯碼效果越好,可糾正更不可靠的碼字,因此可靠度閾值可適度升高。t=4時(shí),NS-SISO譯碼相較于傳統(tǒng)SISO譯碼的性能增益保持穩(wěn)定。由此看出,閾值的選擇與Eb/N0有關(guān),標(biāo)準(zhǔn)SISO譯碼器誤碼率小于10-5時(shí),閾值建議選擇t=4。

圖5為采用NS-SISO算法譯碼e BCH(64,57,4)2的誤碼率隨迭代次數(shù)變化曲線,選定Eb/N0=3,t=4。從圖5可看出,隨迭代次數(shù)的增加,NS-SISO譯碼的性能優(yōu)勢(shì)逐漸明顯。這是因?yàn)镹S-SISO譯碼會(huì)跳過可靠度不高的行或列,使其在迭代次數(shù)較少時(shí)性能增益不明顯。但由于NS-SISO譯碼不引入錯(cuò)誤糾正,當(dāng)?shù)螖?shù)超過5時(shí),雙方的性能差異將開始體現(xiàn)。由圖5可見,要達(dá)到相同的誤碼性能,NS-SISO譯碼比標(biāo)準(zhǔn)SISO譯碼少半次迭代。

圖4 NS-SISO不同閾值t譯碼e BCH(64,57,4)2性能Fig.4 Performance of decoding e BCH(64,57,4)2 by different NS-SISO thresholds

圖5 不同迭代次數(shù)條件下兩種 譯碼方法比較Fig.5 Different decoding methods on different iteration number

圖6給出了兩種TPC碼型e BCH(64,57,4)2和e BCH(32,26,4)2使用NS-SISO和標(biāo)準(zhǔn)SISO譯碼方法的性能對(duì)比圖。仿真中選定p=4,I=8,t=4。從圖6中可見,對(duì)不同的TPC碼型NS-SISO譯碼算法都有一定的性能增益。

圖7給出了利用Al-dweik等[17]提出的NS譯碼算法與筆者提出的NS-SISO算法及傳統(tǒng)算法譯碼e BCH(64,57,4)2時(shí)的性能比較。顯然,軟判決算法具有明顯的性能優(yōu)勢(shì)。而筆者提出的NS-SISO算法能比傳統(tǒng)SISO算法誤碼性能更好。

圖6 兩種不同TPC碼型下NS-SISO和標(biāo)準(zhǔn)SISO譯碼性能比較Fig.6 The performance of two different TPC codes by NS-SISO decoding method and normal SISO decoding method

圖7 硬判決與軟判決NS算法 和傳統(tǒng)算法性能比較Fig.7 The performance of NSand normal decoding method

4 結(jié) 語

筆者將TPC碼的NS譯碼思想推廣到SISO譯碼中,以提高誤碼率性能,若閾值選取適當(dāng),NS-SISO算法的誤碼率僅為標(biāo)準(zhǔn)SISO算法誤碼率的1/2～1/4。該算法根據(jù)碼字可靠度選擇更可靠的行(或列)譯碼,將低于可靠度閾值的子碼碼字留到下次譯碼,以避免迭代過程中引入新的錯(cuò)誤。仿真結(jié)果表明,NS-SISO的最優(yōu)閾值與Eb/N0有關(guān)。當(dāng)選擇合適的閾值值時(shí),達(dá)到相同BER性能的情況下,NS-SISO譯碼所需的譯碼次數(shù)比標(biāo)準(zhǔn)SISO譯碼少一次。

[1]PYNDIAH R M.Near-Optimum Decoding of Product Codes:Block Turbo Codes[J].IEEE Transactions on Communications,1998,46(8):1003-1010.

[2]ELIASP.Error-Free Coding[J].Transactions of the IRE Professional Group on Information Theory,1954,4(4):29-37.[3]CHASE D.Class of Algorithms for Decoding Block Codes with Channel Measurement Information[J].IEEE Transactions on Information Theory,1972,18(1):170-182.

[4]MUKHTAR H,AL-DWEIK A,SHAMIA.Turbo Product Codes:Applications,Challenges,and Future Directions[J].IEEE Communications Surveys&Tutorials,2016,18(1):3052-3069.

[5]MUKHTAR H,AL-DWEIK A,AL-MUALLA M.CRC-Free Hybrid ARQ System Using Turbo Product Codes[J].IEEE Transactions on Communications,2014,62(12):4220-4229.

[6]馬雯,李秀花.基于Turbo乘積碼的超短波高速數(shù)傳系統(tǒng)性能研究[J].南陽理工學(xué)院學(xué)報(bào),2016,8(4):1-3.MA Wen,LI Xiuhua.Performance Research of Ultra-Short-Wave High-Speed Data Transmission System Based on Turbo Product Code[J].Journal of Nanyang Institute of Technology,2016,8(4):1-3.

[7]李安順,邢威,謝立.一種運(yùn)載火箭高碼率遙測(cè)系統(tǒng)設(shè)計(jì)方案[J].計(jì)算機(jī)測(cè)量與控制,2015,23(6):1915-1918.LI Anshun,XING Wei,XIE Li.Design of Launch Vehicle High Bit-Rate Measure System[J].Computer Measurement&Control,2015,23(6):1915-1918.

[8]朱小輝,熊省軍,謝哲,等.TPC碼在水聲中繼節(jié)點(diǎn)中的應(yīng)用研究[J].聲學(xué)與電子工程,2017(2):1-4.ZHU Xiaohui,XIONG Shengjun,XIE Zhe,et al.Application of TPC Code in Underwater Acoustic Relay Node[J].Acoustics and Electronics Engineering,2017(2):1-4.

[9]HIRST SA,HONARY B,MARKARIAN G.Fast Chase Algorithm with an Application in Turbo Decoding[J].IEEE Transactions on Communications,2001,49(10):1693-1699.

[10]ARGON C,MCLAUGHLIN S W.An Efficient Chase Decoder for Turbo Product Codes[J].IEEE Transactions on Communications,2004,52:896-898.

[11]CHEN GT,CAOL,YU L,et al.Test-Pattern-Reduced Decoding for Turbo Product Codes with Multi-Error-Correcting EBCH Codes[J].IEEE Transactions on Communications,2009,57(2):307-310.

[12]MAHRAN A,BENAISSA M.Adaptive Chase Algorithm for Block Turbo Codes[J].Electronics Letters,2003,39(7):617-619.

[13]韓明,張佳巖,趙洪林.低復(fù)雜度的TPC自適應(yīng)譯碼算法[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2017,48(1):141-147.HAN Ming,ZHANG Jiayan,ZHAO Honglin.A Low-Complexity Adaptive Decoding Algorithm for Turbo Product Code[J].Journal of Central South University:Science and Technology,2017,48(1):141-147.

[14]AL-DWEIK A,GOFF S,SHARIF B.A Hybrid Decoder for Block Turbo Codes[J].IEEE Transactions on Communications,2009,57(5):1229-1232.

[15]LU P,LU E,CHEN T.An Efficient Hybrid Decoder for Block Turbo Codes[J].IEEE Communications Letters,2014,18(12):2077-2080.

[16]AL-DWEIK A J,SHARIFB S.Closed-Chains Error Correction Technique for Turbo Product Codes[J].IEEETransactions on Communications,2011,59(3):632-638.

[17]AL-DWEIK A J,SHARIF B S.Non-Sequential Decoding Algorithm for Hard Iterative Turbo Product Codes[J].IEEE Transactions on Communications,2009,57(6):1545-1549.

[18]MARTIN P A,TAYLOR D P,FOSSORIER M P C.Soft-Input Soft-Output List-Based Decoding Algorithm[J].IEEE Transactions on Communications,2004,52(2):252-262.

[19]LONCAR M,JOHANNESSON R,BOCHAROVA IE,et al.Soft-Output BEAST Decoding with Application to Product Codes[J].IEEE Transactions on Information Theory,2008,54(3):1036-1049.

[20]ADDE P,PYNDIAH R,RAOUL O,et al.Block Turbo Decoder Design[J].Proc IEEE Int Symp Turbo Codes&Related Topics,1997,1(1):166-169.

[21]李超.基于FPGA的TPC編譯碼器設(shè)計(jì)與實(shí)現(xiàn)[J].電子科技,2015,28(5):121-123.LI Chao.Design and Realization of TPC Coding Based on FPGA[J].Electronic Sci&Tech,2015,28(5):121-123.

[22]熊玉平.一種交錯(cuò)并行高速TPC譯碼器的設(shè)計(jì)[J].電訊技術(shù),2017,57(7):830-833.XIONG Yuping.Design of a High-speed Interleaved Parallel TPC Decoder[J].Telecommunication Engineering,2017,57(7):830-833.

[23]BERROU C,GLAVIEUX A,THITIMAJSHIMA P.Near Shannon Limit Error-Correcting Coding and Decoding:Turbo-Codes[C]∥ICC'93-IEEE International Conference on Communications.Piscataway,NJ:IEEE,1993:1064-1070.

[24]CHUNG S,FORNEY GD,RICHARDSON TJ,et al.On the Design of Low-Density Parity-Check Codes within 0.004 5 dB of the Shannon Limit[J].IEEE Communications Letters,2001,5(2):58-60.

[25]ROMANYUK A N,YU YU IVANOV.A Brief Overview and Experimental Researches of Novel PL-Log-MAP Turbo Decoding Algorithm[C]∥2017 International Siberian Conference on Control and Communications.Astana:SIBCON,2017:1-6.