基于網(wǎng)格的縮短(38，26)BCH碼的自適應(yīng)維特比譯碼算法

侯舒娟， 宋靈燕， 孫琳

(北京理工大學(xué) 信息與電子學(xué)院，北京 100081)

?

基于網(wǎng)格的縮短(38，26)BCH碼的自適應(yīng)維特比譯碼算法

侯舒娟， 宋靈燕， 孫琳

(北京理工大學(xué) 信息與電子學(xué)院，北京 100081)

針對(duì)伽利略搜救系統(tǒng)(Galileo/SAR)物理層協(xié)議中采用的縮短(38，26)BCH碼，提出了一種自適應(yīng)維特比譯碼算法(AVA). 文中給出了縮短(38，26)BCH碼的最優(yōu)網(wǎng)格，在此基礎(chǔ)上，提出了AVA，該算法在維特比譯碼算法(VA)的基礎(chǔ)上設(shè)計(jì)了一個(gè)丟棄門限，只保留最有可能的路徑. 丟棄門限值隨著信噪比的變化，可以自適應(yīng)調(diào)整，使得AVA在保持與VA幾乎相同的誤碼率性能的基礎(chǔ)上，盡可能地降低譯碼復(fù)雜度. 同時(shí)，文中給出了丟棄門限的估計(jì)方法，并確定了不同信噪比下的最佳丟棄門限值. 仿真結(jié)果表明具有最佳丟棄門限的AVA在保持與VA誤碼性能幾乎相同的基礎(chǔ)上，譯碼復(fù)雜度有著極大程度的降低，特別是在信噪比高時(shí)，譯碼復(fù)雜度下降得更加明顯.

AVA；丟棄門限；縮短BCH碼；伽利略搜救系統(tǒng)

伽利略搜救系統(tǒng)(GALILEO/SAR)是全球衛(wèi)星搜救系統(tǒng)(COSPAS-SARSAT)的一部分[1]，其信標(biāo)信號(hào)采用的編碼方式之一便是縮短(38，26)BCH碼. 對(duì)于該縮短碼，可采用經(jīng)典的BM算法[2]對(duì)其進(jìn)行譯碼，但是BM算法的運(yùn)算量較大. 文獻(xiàn)[3]對(duì)BM算法進(jìn)行了改進(jìn)，提出了一種新的迭代停止準(zhǔn)則，減小了譯碼復(fù)雜度和譯碼延遲. 然而，經(jīng)典BM算法和改進(jìn)BM算法都是硬判決譯碼算法，誤碼率性能較差. 改進(jìn)BM算法對(duì)應(yīng)的軟判決譯碼算法是Chase-2算法[4]，仿真結(jié)果表明，相比改進(jìn)BM算法，Chase-2算法有0.5 dB的編碼增益，但是，Chase-2算法仍然是一種次優(yōu)的譯碼算法.

為了尋找縮短(38，26)BCH碼的最優(yōu)譯碼算法，本文研究了線性分組碼的網(wǎng)格構(gòu)造方法. Wolf在文獻(xiàn)[5]中首先提出了線性分組碼的網(wǎng)格構(gòu)造方法，隨后，F(xiàn)orney[6]和Lin[7]證明了一些線性分組碼具有相當(dāng)簡(jiǎn)單的網(wǎng)格結(jié)構(gòu). 文獻(xiàn)[2，8-9]中研究了最小網(wǎng)格的構(gòu)造、網(wǎng)格的并行分解方法、網(wǎng)格的一般化圖形表示方法，以設(shè)計(jì)出效率更高的基于網(wǎng)格的譯碼算法，使得實(shí)現(xiàn)線性分組碼的最大似然譯碼時(shí)，大大降低譯碼復(fù)雜度. 常用基于網(wǎng)格的譯碼算法是維特比譯碼算法(viterbi algorithm， VA)[10]，該算法遍歷所有碼字，實(shí)現(xiàn)了最大似然譯碼. 但是，其缺點(diǎn)在于譯碼復(fù)雜度與網(wǎng)格的狀態(tài)數(shù)成正比，因此，實(shí)際中通常限制網(wǎng)格各時(shí)刻狀態(tài)數(shù)不超過256，當(dāng)網(wǎng)格狀態(tài)數(shù)過大時(shí)，將不利于譯碼算法的實(shí)現(xiàn).

另一方面，人們?cè)谘芯烤矸e碼的譯碼算法時(shí)，提出了自適應(yīng)維特比譯碼算法(adaptive viterbi algorithm， AVA)[11]，該算法是VA的改進(jìn)算法，在VA基礎(chǔ)上增加了丟棄門限判決，減小了譯碼復(fù)雜度. 文獻(xiàn)[12-14]中對(duì)卷積碼的AVA算法進(jìn)行了改進(jìn)，進(jìn)一步減小了譯碼復(fù)雜度，并且設(shè)計(jì)出了性能更好的AVA譯碼器結(jié)構(gòu).

本文基于線性分組碼的網(wǎng)格構(gòu)造方法和卷積碼的AVA譯碼算法，針對(duì)縮短(38，26)BCH碼，提出了一種軟判決自適應(yīng)維特比譯碼算法，該算法在保證與VA幾乎相同的誤碼性能的基礎(chǔ)上，極大地減小了譯碼復(fù)雜度. 同時(shí)，本文還探討了丟棄門限的估計(jì)方法，仿真結(jié)果驗(yàn)證了該估計(jì)方法的有效性. 值得指出的是，盡管本文的初衷是針對(duì)縮短(38，26)BCH碼，研究其最優(yōu)譯碼算法，但是，本文所提出的方法并不限于縮短(38，26)BCH碼，由于短碼或者中等長(zhǎng)度的線性分組碼的網(wǎng)格復(fù)雜度適中，可以采用AVA算法，所以對(duì)于所有短碼或者中等長(zhǎng)度的線性分組碼，本文所提出的方法都是適用的.

1 縮短(38，26)BCH碼的最優(yōu)網(wǎng)格構(gòu)造

考慮GF(2)中的(n，k)線性分組碼，其生成矩陣是G. 采用高斯消去法，將G變成面向網(wǎng)格的矩陣GTOGM[2].GTOGM有兩個(gè)特點(diǎn)：

① 每一行的首1所處的列在其下方各行的首1所處列之前；

② 沒有兩行的尾1在同一列.

令g=[g0g1…gn-1]為GTOGM的一行，區(qū)間[i，j](0≤i≤j≤n-1)表示g中所有非零元素的最小指標(biāo)區(qū)間，定義為g的比特跨度，gi和gj分別是g的首1和尾1. 定義g的時(shí)間跨度為[i，j+1]，有效時(shí)間跨度為

(1)

首先構(gòu)造(n，k)線性分組碼的比特級(jí)網(wǎng)格. 記C是(n，k)線性分組碼的碼字集合，假設(shè)已經(jīng)完成了第i段網(wǎng)格的構(gòu)造，現(xiàn)在構(gòu)造時(shí)刻i到時(shí)刻i+1的第i+1段網(wǎng)格，步驟如下：

(2)

(3)

③ 對(duì)每一個(gè)狀態(tài)轉(zhuǎn)移，其相應(yīng)的輸出碼比特vi為

(4)

或

(5)

其次，對(duì)比特級(jí)網(wǎng)格進(jìn)行分段和并行分解以簡(jiǎn)化網(wǎng)格的構(gòu)造[2，7]. 以縮短(38，26)BCH碼為例，考慮將其比特級(jí)網(wǎng)格均勻分成L段，則L的可能取值為38，19和2，其中當(dāng)L=38時(shí)，即比特級(jí)網(wǎng)格. 當(dāng)L=2時(shí)，GTOGM中存在有些行的有效時(shí)間跨度恰好位于兩個(gè)分段時(shí)刻之間，分段后各時(shí)刻狀態(tài)標(biāo)記將不攜帶這些行對(duì)應(yīng)的信息位，最終導(dǎo)致無法對(duì)這些信息位進(jìn)行譯碼，因此，縮短(38，26)BCH碼可行的分段方式只有L=38和L=19. 此外，無論L=38還是L=19，并行分解后網(wǎng)格的最大狀態(tài)空間維數(shù)都超過了并行分解前網(wǎng)格的最大狀態(tài)空間維數(shù)，即不滿足并行分解原則[2]，則縮短(38，26)BCH碼的L段網(wǎng)格都無法進(jìn)行并行分解，因此，縮短(38，26)BCH碼的可用網(wǎng)格只有L=38和L=19的兩種形式.

依據(jù)VA譯碼的譯碼復(fù)雜度，對(duì)L=38和L=19時(shí)的兩種網(wǎng)格進(jìn)行篩選. 定義VA譯碼的譯碼復(fù)雜度為NT=NB+NA+NC，其中NB是分支度量次數(shù)，NA是加法次數(shù)，NC是比較次數(shù)，所以具有最小NT的網(wǎng)格是最優(yōu)網(wǎng)格. 表1統(tǒng)計(jì)了L=38和L=19時(shí)兩種網(wǎng)格的譯碼復(fù)雜度，由表1可知，對(duì)于縮短(38，26)BCH碼，L=38，即比特級(jí)網(wǎng)格的譯碼復(fù)雜度NT最小.

表1 縮短(38，26)BCH碼在不同分段方式下的譯碼復(fù)雜度

Tab.1 ECC of differentL-section trellis for shortened (38，26) BCH code

LNBNANCNT38131068131066614393235731912560812560490111341323

2 線性分組碼的AVA算法

AVA最早是針對(duì)卷積碼提出的，在實(shí)現(xiàn)線性分組碼的最優(yōu)網(wǎng)格構(gòu)造后，可以將其應(yīng)用于線性分組碼的譯碼. 考慮(n，k)線性分組碼，其軟判決譯碼采用歐氏距離作為可靠性度量，假設(shè)進(jìn)行Q比特量化，則歐氏距離定義為

(6)

式中:K=2Q-1;v=[v0v1…vn-1]為編碼后的碼字；c=[c0c1…cn-1]為接收端量化后的碼字. 假設(shè)(n，k)線性分組碼的最優(yōu)網(wǎng)格是均勻分成L段，每段M個(gè)比特，則有L×M=n，第j(1≤j≤L)段網(wǎng)格的分支度量值為

(7)

第i(1≤i≤L)分段點(diǎn)的路徑度量值為

(8)

圖1給出了線性分組碼的AVA譯碼過程，假設(shè)譯碼過程已經(jīng)進(jìn)行到分段點(diǎn)i-1，則分段點(diǎn)i(1≤i≤n)的譯碼步驟如下.

① 計(jì)算第i段所有分支的度量值Bi，如果分支對(duì)應(yīng)的前一分段點(diǎn)狀態(tài)已被丟棄，則不用計(jì)算該分支的度量值.

② 對(duì)第i段的每一狀態(tài)，將該狀態(tài)的分支度量值Bi和與分支相連的前一狀態(tài)的幸存路徑度量值P(i-1)相加，得到該狀態(tài)的路徑度量值P(i)，即

P(i)=P(i-1)+Bi.

(9)

設(shè)置丟棄門限τ，如果P(i)滿足

P(i)≤Pmin(i-1)+τ.

(10)

則把其對(duì)應(yīng)的路徑保留下來. 如果某一狀態(tài)的路徑都不滿足該條件，則丟棄該狀態(tài). 最后比較到達(dá)該狀態(tài)的所有滿足式(10)的路徑，選取具有最小路徑度量值的路徑為該狀態(tài)幸存路徑.

③ 存儲(chǔ)幸存路徑及度量值.

④ 比較第i分段點(diǎn)所有狀態(tài)的幸存路徑度量值，選取其中的最小值Pmin(i)用于下一分段點(diǎn)譯碼.

對(duì)后續(xù)每一分段點(diǎn)都執(zhí)行同樣的操作，一直到網(wǎng)格末端，即完成了線性分組碼的AVA譯碼過程.

AVA的自適應(yīng)性在于隨著信噪比的變化，丟棄門限值可以進(jìn)行自適應(yīng)地調(diào)整，使得AVA在保持與VA幾乎相同的誤碼率性能的基礎(chǔ)上，可以降低譯碼復(fù)雜度. 當(dāng)τ→∞時(shí)，AVA→VA. 隨著τ值的減小，當(dāng)達(dá)到某一最優(yōu)值τopt時(shí)，AVA的誤碼率性能開始變差；且AVA算法的譯碼復(fù)雜度隨著τ值的減小而減小，因此，AVA算法的關(guān)鍵在于確定最佳丟棄門限值τopt.

3 最佳丟棄門限值的估計(jì)

用t表示(n，k)線性分組碼的糾錯(cuò)能力，未量化的VA可以達(dá)到t比特的糾錯(cuò)能力. AVA是對(duì)VA的近似，由于使用了丟棄門限τ刪除路徑和狀態(tài)，AVA譯碼時(shí)有可能會(huì)丟棄正確譯碼路徑，這將導(dǎo)致譯碼錯(cuò)誤. 用Pe，VA表示VA的誤字率，則AVA的誤字率可以表示為

Pe，AVA=Pe，VA+Ploss.

(11)

其中Ploss是AVA相對(duì)VA的譯碼性能損失，表示正確路徑被丟棄的概率.

考慮AWGN信道和BPSK調(diào)制的情況，用x=[x0x1…xi…x37]表示發(fā)射端的碼字序列，則xi=1-2vi∈{1，-1}，接收端碼字

r=[r0r1…ri…r37]，

則

ri=xi+ni.

(12)

其中ni～N(0，σ2).

y=[y0y1…yi…y37]表示BPSK解調(diào)后的序列，則

yi=(1-ri)/2=vi-ni/2.

(13)

其中yi～N(vi，σ2/4).

令c=[c0c1…ci…c37]為解調(diào)后的硬判決序列，ci∈{0，1}. 由此可得到接收序列c中每個(gè)比特的錯(cuò)誤概率為

考慮在Ei種錯(cuò)誤類型中有Ni種是VA可以正確譯碼的，則由于i個(gè)比特錯(cuò)誤，導(dǎo)致AVA譯碼失敗而VA譯碼正確的概率可以表示為

通常情況下Pb較小，可認(rèn)為Pb→0，則(1-Pb)→1，故式(16)可簡(jiǎn)化為

假設(shè)當(dāng)硬判決序列c中錯(cuò)誤比特的個(gè)數(shù)小于等于硬判決的丟棄門限τhard時(shí)，VA和AVA都可以正確譯碼，隨著錯(cuò)誤比特?cái)?shù)i的增加，當(dāng)i≥t+1時(shí)，Ni將非常小，所以Ploss可表示為

(18)

當(dāng)τhard=t時(shí)，

因?yàn)镻b通常很小，式(19)的結(jié)果通常取決于Pb的大小，因此，Ploss可進(jìn)一步近似為

下面考慮VA和AVA都進(jìn)行軟判決譯碼的情況，硬判決譯碼可看作1比特量化的軟判決譯碼的特殊情況. 將上述硬判決譯碼的結(jié)論推廣到軟判決譯碼的情況下，Ploss仍然滿足式(18)～(20)，區(qū)別在于硬判決譯碼時(shí)分析的是漢明距離，即錯(cuò)誤比特?cái)?shù)i，軟判決譯碼時(shí)分析的是歐氏距離dE.

對(duì)于軟判決的情況，假設(shè)當(dāng)軟判決量化后序列c與碼字序列v的歐氏距離小于等于軟判決的丟棄門限τsoft時(shí)，VA和AVA都可以正確譯碼，隨著歐氏距離dE的增加，當(dāng)dE≥(t+1)K時(shí)，導(dǎo)致AVA譯碼失敗而VA譯碼正確的概率PdE將非常小，所以Ploss可表示為

其中K=2Q-1，Q為軟判決的量化比特?cái)?shù). 類似地，當(dāng)τsoft=[(t+1)K-1]時(shí)，Ploss滿足式(20).

τhard=t±ε.

(22)

或者

τsoft=[(t+1)K-1]±ε.

(23)

以縮短(38，26)BCH碼為例，其糾錯(cuò)能力t=2，當(dāng)該碼采用3比特均勻量化時(shí)，由式(23)可得τsoft=20±ε. 表2中給出了不同信噪比SNR下的Pe，VA和Ploss，因?yàn)镋b/N0(dB)=10lgEb/N0=10lg1/(2σ2)，則

表2 不同SNR下的Pe，VA和Ploss統(tǒng)計(jì)

圖2給出了縮短(38，26)BCH碼在Eb/N0=0～4 dB下，AVA的誤字率隨著丟棄門限τsoft變化的性能曲線，為便于比較，圖中也標(biāo)出了VA的誤字率. 根據(jù)以上分析，τsoft=20-ε，因此，τsoft以2為間隔，在區(qū)間內(nèi)取整數(shù)值. 從圖2可以看出，當(dāng)AVA的誤字率RWE接近VA的RWE時(shí)，對(duì)應(yīng)的τsoft的值即最佳丟棄門限的值. 統(tǒng)計(jì)得到的縮短(38，26)BCH碼在不同SNR下的最佳丟棄門限值τopt如表3所示.

表3 縮短(38，26)BCH碼在不同SNR下對(duì)應(yīng)的τopt值

Tab.3 Estimated optimal threshold for different SNR from simulation results for shortened (38，26) BCH code

(Eb/N0)/dB01234τopt1818171614

4 仿真結(jié)果及分析

圖3給出了AVA、VA和Chase-2算法的WER性能曲線，其中AVA算法在不同SNR下的丟棄門限值如表3所示. 從圖3可看出，在任意SNR條件下， AVA和VA的WER性能都十分接近，Chase-2算法的WER性能較差，這是因?yàn)镃hase-2算法是一種次優(yōu)的譯碼算法，而VA實(shí)現(xiàn)了最大似然譯碼，是一種最優(yōu)的譯碼算法，AVA又是VA的近似. BER性能曲線有著相同的趨勢(shì).

不同τ值的AVA的譯碼復(fù)雜度不同，采用ACS單元使用數(shù)目作為譯碼復(fù)雜度的衡量指標(biāo). VA和AVA的ACS單元使用數(shù)目與SNR的關(guān)系曲線如圖4所示，可知，當(dāng)Eb/N0=0～4 dB時(shí)，AVA的ACS單元使用數(shù)目分別是VA的26%、26%、19%、11%和5%，即隨著SNR的增大，AVA譯碼過程中利用的ACS單元數(shù)目相比VA的減小程度愈加明顯.

5 結(jié) 論

本文針對(duì)伽利略搜救系統(tǒng)中的縮短(38，26)BCH碼，提出了一種自適應(yīng)維特比譯碼算法(AVA). 該算法基于縮短(38，26)BCH的最優(yōu)網(wǎng)格，在VA的基礎(chǔ)上，增加了一個(gè)丟棄門限，丟棄門限值的大小隨著信噪比而發(fā)生變化，以保證AVA和VA具有相同的誤碼率性能的條件下，盡可能地降低譯碼復(fù)雜度. 此外，文中還給出了丟棄門限值的估計(jì)方法，并確定了各個(gè)信噪比下的最佳丟棄門限值. 仿真結(jié)果表明，AVA在保持與VA相同的誤碼率性能的基礎(chǔ)上，在Eb/N0=0～4 dB時(shí)，AVA的ACS單元使用數(shù)目分別是VA的26%、26%、19%、11%和5%.

本文提出的丟棄門限值的估計(jì)方法在推導(dǎo)的過程中有近似，所以實(shí)際的丟棄門限值要在此基礎(chǔ)上進(jìn)行修正，文中通過仿真給出了修正后的丟棄門限值，并沒有從理論上分析修正量的大小，這是作者后續(xù)要進(jìn)一步研究的問題. 此外，文中所研究的縮短(38，26)BCH碼并不適合做并行分解，因此，所研究的AVA算法也沒有涉及到并行分解問題，對(duì)并行分解的網(wǎng)格進(jìn)行AVA譯碼也是作者后續(xù)要進(jìn)一步研究的問題.

[1] Cospas-Sarsat Council. Specification for COSPAS-SARSAT 406 MHz distress beacons (Revision 13)[S]. [S.l.]: COSPAS-SARSAT, 2012.

[2] Lin S, Costello Jr D J. Error control coding[M]. 2nd ed. New Jersey: Pearson Prentice-Hall， 2004.

[3] Zhang D S， An J P， Fan Y Y. Improved Berlekamp-Massy algorithm and its software implementation on DSP[J]. Journal of Beijing Institute of Technology (English Edition)， 2010，19(2):207-210.

[4] Liu X J， Zhao C M， Sun X J. Low complexity Chase-2 decoding of concatenated codes[J]. Chinese Science Bulletin， 2010，55(26):3066-3070.

[5] Wolf J K. Efficient maximum likelihood decoding of linear block codes using a trellis[J]. IEEE Transactions on Information Theory， 1978，24(1):76-80.

[6] Forney Jr G D. Coset codes-part II: binary lattices and related codes[J]. IEEE Transactions on Information Theory， 1988，34(5):1152-1187.

[7] Moorthy H T， Lin S， Uehara G T. Good trellises for IC implementation of Viterbi decoders for linear block codes[J]. IEEE Transactions on Communications， 1997，45(1):52-63.

[8] Forney Jr G D， Gluesing-Luerssen H. Codes on graphs: observability， controllability， and local reducibility[J]. IEEE Transactions on Information Theory， 2013，59(1):223-237.

[9] Gluesing-Luerssen H， Forney Jr G D. Local irreducibility of tail-biting trellises[J]. IEEE Transactions on Information Theory， 2013，59(10):6597-6610.

[10] Naguib A F， Seshadri N， Calderbank A R. Increasing data rate over wireless channels[J]. IEEE Signal Processing Magazine， 2000，17(3):76-92.

[11] Chan F， Haccoun D. Adaptive Viterbi decoding of convolutional codes over memoryless channels[J]. IEEE Transactions on Communications， 1997，45(11):1389-1400.

[12] Suganya G S， Kavya G. RTL design and VLSI implementation of an efficient convolutional encoder and adaptive Viterbi decoder[C]∥International Conference on Communications and Signal Processing (ICCSP). Melmaruvathur， India:[s.n.]， 2013:494-498.

[13] Brahmbhatt C， Mishra M. Design and implementation of adaptive Viterbi decoder for high speed applications[J]. International Journal of Advanced and Innovative Research， 2013，11(2):340-343.

[14] Sonar N S， Al-Naimy F S， Mudholkar R R. An improved dynamically reconfigurable pipelined adaptive viterbi decoder for high throughput[J]. International Journal of Engineering and Innovative Technology， 2013，7(2):194-198.

(責(zé)任編輯：劉芳)

Adaptive Viterbi Decoding Algorithm for the Shortened (38,26) BCH Code Based on Trellis

HOU Shu-juan， SONG Ling-yan， SUN Lin

(School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China)

Galileo search and rescue system (Galileo/SAR) adopts the shortened (38,26) BCH code in its physical layer protocol. In this paper, an adaptive Viterbi decoding algorithm (AVA) was proposed. The best trellis for the shortened (38,26) BCH code was first presented. In the AVA, a discarding threshold was designed on the basis of the Viterbi algorithm (VA), only retaining the most likely paths. The discarding threshold could vary with the different SNR and be adjusted adaptively to reduce the decoding complexity as much as possible, with almost the same error performance as the VA. Simulation results show that, the decoding complexity of the AVA reduces greatly compared with the VA, maintaining nearly the same error performance. Especially at high SNR, the decoding complexity decreases more obviously.

AVA; discarding threshold; shortened BCH code; Galileo SAR system

2014-09-02

侯舒娟(1977—)，女，博士，副研究員，E-mail:shujuanhou@bit.edu.cn.

TN 967.1

A

1001-0645(2016)11-1205-06

10.15918/j.tbit1001-0645.2016.11.020