侯舒娟， 宋靈燕， 孫琳

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

?

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

侯舒娟， 宋靈燕， 孫琳

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

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

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

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

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

另一方面，人們在研究卷積碼的譯碼算法時，提出了自適應維特比譯碼算法(adaptive viterbi algorithm， AVA)[11]，該算法是VA的改進算法，在VA基礎上增加了丟棄門限判決，減小了譯碼復雜度. 文獻[12-14]中對卷積碼的AVA算法進行了改進，進一步減小了譯碼復雜度，并且設計出了性能更好的AVA譯碼器結構.

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

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

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

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

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

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

(1)

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

(2)

(3)

③ 對每一個狀態(tài)轉移，其相應的輸出碼比特vi為

(4)

或

(5)

其次，對比特級網(wǎng)格進行分段和并行分解以簡化網(wǎng)格的構造[2，7]. 以縮短(38，26)BCH碼為例，考慮將其比特級網(wǎng)格均勻分成L段，則L的可能取值為38，19和2，其中當L=38時，即比特級網(wǎng)格. 當L=2時，GTOGM中存在有些行的有效時間跨度恰好位于兩個分段時刻之間，分段后各時刻狀態(tài)標記將不攜帶這些行對應的信息位，最終導致無法對這些信息位進行譯碼，因此，縮短(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)格都無法進行并行分解，因此，縮短(38，26)BCH碼的可用網(wǎng)格只有L=38和L=19的兩種形式.

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

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

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

LNBNANCNT38131068131066614393235731912560812560490111341323

2 線性分組碼的AVA算法

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

(6)

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

(7)

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

(8)

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

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

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

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

(9)

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

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

(10)

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

③ 存儲幸存路徑及度量值.

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

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

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

3 最佳丟棄門限值的估計

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

Pe，AVA=Pe，VA+Ploss.

(11)

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

考慮AWGN信道和BPSK調制的情況，用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解調后的序列，則

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

(13)

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

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

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

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

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

(18)

當τhard=t時，

因為Pb通常很小，式(19)的結果通常取決于Pb的大小，因此，Ploss可進一步近似為

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

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

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

τhard=t±ε.

(22)

或者

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

(23)

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

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

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

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

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

(Eb/N0)/dB01234τopt1818171614

4 仿真結果及分析

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

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

5 結 論

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

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

[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.

(責任編輯：劉芳)

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