基于可信位置排序的咬尾卷積碼譯碼算法

王曉濤 劉振華

1 引言

卷積碼在編碼時(shí)其編碼器可以用已知比特來(lái)初始化，也可以用信息比特來(lái)初始化。對(duì)于寄存器長(zhǎng)度為v的卷積碼編碼器，當(dāng)采用信息比特的最后v位來(lái)初始化編碼器時(shí)，編碼結(jié)束時(shí)編碼器的狀態(tài)和其初始狀態(tài)是相同的，同時(shí)碼字對(duì)應(yīng)的格形圖呈咬尾狀態(tài)[1,2]。我們稱這種方式得到的碼字為咬尾卷積碼（Tail-Biting Convolutional Codes, TBCC），其對(duì)應(yīng)的格形圖為咬尾格形圖。

采用咬尾方式編碼可以消除用已知比特初始化編碼器帶來(lái)的碼率損失[35]-，這種損失對(duì)于短碼來(lái)說(shuō)顯得更為嚴(yán)重，比如對(duì)于生成多項(xiàng)式為{354, 237}（8進(jìn)制），信息序列長(zhǎng)度為32的卷積碼來(lái)說(shuō)，如果不采用咬尾編碼其有效碼率損失會(huì)達(dá)到20%。因此咬尾卷積碼作為一種高效的短碼編碼方式被廣泛用于各種通信系統(tǒng)中作為控制信道和廣播信道的編碼方案，如在增強(qiáng)型數(shù)據(jù)速率 GSM 演進(jìn)技術(shù)（Enhanced Data rate for GSM Evolution, EDGE）[6]和 3GPP 長(zhǎng)期演進(jìn)項(xiàng)目（Long Term Evolution,LTE）[7]等通信系統(tǒng)。

由于咬尾卷積碼的編碼器采用信息序列進(jìn)行初始化，因此其對(duì)應(yīng)的咬尾格形圖在起始位置有2v個(gè)起始狀態(tài)，這種結(jié)構(gòu)給譯碼器的設(shè)計(jì)帶來(lái)了困難[812]-。目前咬尾卷積碼的譯碼算法主要有3大類：基于循環(huán)Viterbi算法（Circular Viterbi Algorithm,CVA）的譯碼算法，如WAVA和TD-CVA等[1,13]；基于 Viterbi算法和啟發(fā)式搜索的混合式譯碼（Viterbi-Heuristic, VH）[14]；和基于雙向搜索的有效譯碼算法（Bidirectional Efficient Algorithm for Searching code Trees, BEAST）[15]。BEAST 算法工作時(shí)需要將咬尾格形圖轉(zhuǎn)化成傳統(tǒng)格形圖，且需要保存整個(gè)格形圖的結(jié)構(gòu)信息，這將消耗大量的存儲(chǔ)空間。比如對(duì)于（24,12）的Golay碼來(lái)說(shuō)，其傳統(tǒng)格形圖的中間位置處的狀態(tài)數(shù)高達(dá)512個(gè)[15]，而其具有最低狀態(tài)復(fù)雜度的咬尾格形圖在每個(gè)位置處的狀態(tài)數(shù)只有16個(gè)[11]。VH算法分為兩個(gè)譯碼階段，在第1階段Viterbi算法將咬尾格形圖上所有位置處到達(dá)每個(gè)狀態(tài)的幸存路徑的度量值保存下來(lái)，利用這些信息進(jìn)行啟發(fā)式搜索。VH算法的兩個(gè)譯碼步驟基于兩種完全不同的搜索算法，不僅需要保存大量的中間信息，同時(shí)譯碼器實(shí)現(xiàn)復(fù)雜度高，不利于實(shí)際應(yīng)用。

CVA是一種完全基于Viterbi的譯碼算法，通過(guò)在咬尾格形圖多次迭代來(lái)尋找最優(yōu)咬尾路徑及其對(duì)應(yīng)的碼字。傳統(tǒng)的基于CVA的譯碼算法沒(méi)有考慮譯碼過(guò)程中存在的循環(huán)陷阱，這導(dǎo)致譯碼器在譯碼結(jié)束時(shí)可能無(wú)法收斂到最優(yōu)咬尾路徑，因此是一種次優(yōu)譯碼算法，如WAVA和ET-CVA等。TD-CVA從循環(huán)陷阱出發(fā)，通過(guò)在迭代過(guò)程中對(duì)非最大似然狀態(tài)的排除，使得譯碼器能最終收斂到全局最優(yōu)咬尾路徑。

本文利用咬尾格形圖的循環(huán)性，提出了一種基于CVA的最大似然譯碼算法。新算法首先根據(jù)接收到的似然比信息來(lái)確定可靠性最高的起始位置，然后從該起始位置處開(kāi)始譯碼。這樣經(jīng)過(guò)幾個(gè)分支的搜索以后，幸存路徑的起始狀態(tài)會(huì)收斂到更少的幸存狀態(tài)上。相對(duì)于已有的算法，本文算法具有更快的收斂速度，譯碼效率得到進(jìn)一步提高。

本文結(jié)構(gòu)如下，第2節(jié)介紹新算法的設(shè)計(jì)原理，并通過(guò)例子給出算法說(shuō)明，同時(shí)對(duì)算法的最優(yōu)性進(jìn)行證明；第3節(jié)給出算法性能仿真驗(yàn)證；第4節(jié)總結(jié)全文。

2 算法描述

2.1 變量定義

如圖 1所示的咬尾格形圖T是生成多項(xiàng)式為{7,5}、信息序列長(zhǎng)度為 L = 8 的TBCC對(duì)應(yīng)的咬尾格形圖。格形圖T中位置l處的狀態(tài)集合記為 Sl，0≤l≤L（S0= SL）。對(duì)于咬尾卷積碼來(lái)說(shuō)其咬尾格形圖是規(guī)則的[12]，即有 Si= Sj, 0 ≤ i , j ≤ L 。格形圖T中任意位置l處的狀圖s都有其對(duì)應(yīng)的咬尾格形子圖，記為Tsub（s）。圖1中實(shí)線所示為位置l=2處的狀態(tài)s=01的咬尾格形子圖。Tsub（s）上所有完整路徑都是咬尾路徑，整個(gè)咬尾格形圖T是由位置l處所有狀態(tài)的咬尾格形圖的并集組成[12]，即有

圖1 生成多項(xiàng)式為{7,5}的咬尾卷積碼格形圖

在譯碼開(kāi)始的時(shí)候，對(duì)接收到的軟信息進(jìn)行處理以選擇可靠性最高的位置lopt作為譯碼的起始位置。設(shè)信息序列長(zhǎng)度為L(zhǎng)的TBCC的碼率為 b/ c，編碼以后的碼字為∈ {0,1}，其中0≤l≤L,0≤j≤c-1。設(shè)碼字經(jīng)過(guò)BPSK調(diào)制得到映射后的符號(hào)為：= （ 1 -），不失一般性令 Es為1。經(jīng)過(guò)雙邊噪聲功率譜密度為 N0/2的高斯白噪聲（Additive White Gaussian Noise, AWGN）信道后，對(duì)應(yīng)接收到的符號(hào)為，計(jì)算得到似然比信息=/。定義l 的計(jì)算方式為opt

式 中 （l+ Q ）L= （ l+ Q ） mod L ， 其 中Q是待 確 定 的量，在具體應(yīng)用中將根據(jù)不同的碼字選擇合適的值。

2.2 算法說(shuō)明

由于CVA的譯碼過(guò)程是迭代的，即在第i次迭代中每個(gè)狀態(tài)的初始度量值是用第 i - 1次迭代得到的幸存路徑的度量值來(lái)初始化的，因此每次迭代都會(huì)得到不同的幸存路徑及其路徑度量值[1]。第i次迭代中，起始于狀態(tài)s，結(jié)束于狀態(tài)s'的幸存路徑記為 Pi（ s, s'） ，其中 s , s '∈, Pi（ s, s'） 對(duì)應(yīng)的路徑累積度量值記為 Mi（ s, s'）。如果咬尾格形圖T上的幸存路徑的起始狀態(tài)和終止?fàn)顟B(tài)相同，即 s = s '（ ∈ Slopt） ，則路徑Pi（ s, s）為咬尾路徑。T（s）是由所有從狀態(tài)subs起始并結(jié)束到狀態(tài)s的咬尾路徑的集合構(gòu)成，記Tsub（s）上對(duì)應(yīng)于接收序列度量值最大的咬尾路徑為s, s）：

其中 s ∈Slopt, i≥1。

算法的步驟描述如下：

步驟1 根據(jù)式（2）計(jì)算最佳譯碼起始位置lopt，初始化迭代次數(shù) i = 0 ，令= S ； lopt

lopt有循環(huán)陷阱產(chǎn)生：

（a）有循環(huán)陷阱：找到具有最大路徑度量值Mi（ s, s'） 的幸存路徑 Pi（ s, s'） ，在T（s） 上執(zhí)行一

sub次 Viterbi算法得到（s, s），將s從中刪除；同時(shí)若（s, s）＞，更新；返回步驟2。

（b）無(wú)循環(huán)陷阱：返回步驟2。

步驟4 令 Po=，輸出 Po作為最終譯碼結(jié)果，譯碼結(jié)束。

2.3 最優(yōu)性證明

由文獻(xiàn)[1]可知，通過(guò)對(duì)循環(huán)陷阱的控制，譯碼算法最終會(huì)收斂到，而是譯碼器從位置lopt處開(kāi)始譯碼得到的最大似然咬尾路徑，因此證明算法的最優(yōu)性就是證明譯碼結(jié)果與起始位置無(wú)關(guān)。

定理 1 譯碼算法在咬尾格形圖上得到的最大似然咬尾路徑與譯碼起始位置相獨(dú)立，即有 Po=。

因?yàn)椋?）P s s是咬尾路徑，由咬尾路徑定義可知該路徑在咬尾格形圖上起始和結(jié)束于同一個(gè)狀態(tài)，且任意位置l處的狀態(tài)集合lS中有且僅有一個(gè)狀態(tài)在咬尾路徑上（非咬尾路徑在起始位置處不滿足此條件）。設(shè)（,）P s s經(jīng)過(guò)optlS中的狀態(tài)s'，則有

可見(jiàn)P（ s, s）是咬尾格形子圖Tsub（s'）上的咬尾路徑，設(shè)Tsub（s'）上的最優(yōu)咬尾路徑為（s',s'），且其路徑度量值為（s',s'），從而有

由式（6），式（7）兩式可知：

可見(jiàn)式（8）與假設(shè)條件式（4）相矛盾，即譯碼結(jié)束時(shí)咬尾格形圖上不存在任何咬尾路徑其度量值大于，譯碼過(guò)程與譯碼起始位置無(wú)關(guān)，中保存的即為全局最優(yōu)咬尾路徑，所以有 Po=證畢

3 仿真驗(yàn)證

本節(jié)通過(guò)兩個(gè)實(shí)驗(yàn)來(lái)驗(yàn)證本文算法的有效性，為引用方便，將本文算法記為NCVA（New CVA）。此處選用兩種經(jīng)典算法進(jìn)行性能比較，WAVA算法和VH算法，這是因?yàn)閃AVA是咬尾格形圖上基于CVA的經(jīng)典譯碼算法，而VH算法是咬尾格形圖上基于啟發(fā)式搜索的經(jīng)典算法。編碼以后的比特通過(guò)QPSK映射后經(jīng)過(guò) AWGN信道，接收端接收到信息序列以后分別采用上述3種譯碼算法進(jìn)行譯碼，譯碼過(guò)程中每個(gè)譯碼塊的平均訪問(wèn)狀態(tài)數(shù)作為衡量譯碼復(fù)雜度的標(biāo)準(zhǔn)。

在第1個(gè)實(shí)驗(yàn)中，我們選用LTE中用于控制信道編碼的咬尾卷積碼碼字（120, 40）進(jìn)行實(shí)驗(yàn)，該咬尾卷積碼生成多項(xiàng)式為（133, 171, 165）（8進(jìn)制），編碼器寄存器長(zhǎng)度為 6v= 。仿真結(jié)果如圖2所示。將WAVA 性能和 NCVA性能比較可見(jiàn)：由于循環(huán)陷阱控制的添加，以及選擇可信度更高的譯碼起始位置，能夠極大的提高譯碼效率；VH算法的性能和NCVA的性能比較可以發(fā)現(xiàn)，在信噪比從低到高變化的范圍內(nèi)NCVA都可以達(dá)到更高的譯碼效率。隨著信噪比的升高，NCVA從任何地方開(kāi)始譯碼都可以得到相同的譯碼復(fù)雜度，即執(zhí)行一次迭代即可得到最優(yōu)解；同時(shí)VH算法也只需要執(zhí)行一次Viterbi算法即可得到最優(yōu)解。因此，NCVA和VH算法的譯碼復(fù)雜度最終收斂到一起，為2vL= 2 560，這和仿真結(jié)果相吻合。

表 1中給出了幾種不同譯碼算法的誤碼率性能。由于VH算法，TD-CVA, NCVA是最優(yōu)譯碼算法，因此它們有相同的誤碼率性能，而WAVA是次優(yōu)譯碼算法，因此 WAVA算法的性能要略差于NCVA算法。

表1 不同譯碼算法對(duì)（120,40）咬尾卷積碼譯碼的誤碼率性能

和 TD-CVA[1]相比，本文算法利用了可信位置排序來(lái)改進(jìn)算法的收斂速度。為了驗(yàn)證可信位置排序?qū)λ惴ㄊ諗克俣鹊母倪M(jìn)，表2中給出NCVA在不同Q值下的譯碼復(fù)雜度和 TD-CVA算法的譯碼復(fù)雜度詳細(xì)對(duì)比列表。通過(guò)對(duì)比可以發(fā)現(xiàn)以下兩點(diǎn)規(guī)律：

（1）由于可信位置的選擇，NCVA 可以比 TDCVA獲得更快的收斂速度；

表2 NCVA與TD-CVA算法復(fù)雜度對(duì)比

圖2 不同譯碼算法對(duì)（120,40）咬尾卷積碼的譯碼性能比較

（2）當(dāng)Q值越小時(shí)，可靠度的作用越明顯；由于接收序列服從正態(tài)分布，因此當(dāng)Q值越大時(shí)，由式（2）計(jì)算得到的每個(gè)位置的可靠度越接近；極限情況是Q為接收序列的長(zhǎng)度，此時(shí)每個(gè)位置的可靠度完全一樣，那么譯碼從頭開(kāi)始，復(fù)雜度與TD-CVA相同。

綜合以上考慮，實(shí)際中選取 2Q≤ 。

在第 2個(gè)實(shí)驗(yàn)中，我們選用（24,12）Golay碼為例。Golay碼的16狀態(tài)咬尾格形圖狀態(tài)復(fù)雜度低，但是該咬尾格形圖是周期為4的咬尾格形圖，整個(gè)格形圖分為3段，長(zhǎng)度為12。這種格形圖在每個(gè)時(shí)刻的路徑輸出不同，不利于譯碼器的實(shí)現(xiàn)，本文選用其64狀態(tài)咬尾格形圖表示，該格形圖可以由生成多項(xiàng)式{103, 166}得到[1]。圖3中給出了不同譯碼算法對(duì)（24,12）Golay碼譯碼復(fù)雜度比較，可以得到和第1個(gè)實(shí)驗(yàn)相同的結(jié)論。

表3中給出了幾種算法的誤塊率性能，可見(jiàn)在信噪比比較高，即 Eb/N0≥ 3 dB 時(shí)，次優(yōu)譯碼算法WAVA的性能和NCVA性能接近。

表3 不同譯碼算法對(duì)（24,12）Golay碼譯碼的誤碼率性能

4 結(jié)束語(yǔ)

咬尾格形圖具有循環(huán)性，在咬尾格形圖上的譯碼過(guò)程可以從任意位置開(kāi)始，最終得到的最大似然譯碼結(jié)果都是相同的。文中以定理的形式證明了這個(gè)結(jié)論，從任何位置開(kāi)始譯碼得到的最優(yōu)咬尾路徑都是全局最優(yōu)咬尾路徑。本文中提出的譯碼器利用咬尾格形圖的循環(huán)性，用接收到的信道輸出序列先計(jì)算一個(gè)可信度最高的譯碼起始位置。從該位置開(kāi)始譯碼可以發(fā)現(xiàn)譯碼器能夠更快地收斂到最優(yōu)解，最后的仿真結(jié)果也證明了算法有效性。

圖3 不同譯碼算法對(duì)（24,12）Golay碼譯碼性能比較

[1] Wang Xiao-tao, Qian Hua, Xiang Wei-dong, et al.. An efficient ML decoder for tail-biting codes based on circular trap detection[J]. IEEE Transactions on Communications,2013, 61（4）: 1212-1221.

[2] Gluesing-Luerssen H and Forney G D. Local irreducibility of tail-biting trellises[J]. IEEE Transactions on Information Theory, 2013, 59（10）: 6597-6610.

[3] 王曉濤, 錢驊, 徐景, 等. 基于陷阱檢測(cè)的咬尾卷積碼譯碼算法[J]. 電子與信息學(xué)報(bào), 2011, 33（10）: 2300-2305.Wang Xiao-tao, Qian Hua, Xu Jing, et al.. Trap detection based decoding algorithm for tail-biting convolutional codes[J]. Journal of Electronics & Information Technology, 2011,33（10）: 2300-2305.

[4] 王曉濤, 錢驊, 康凱. 基于 Viterbi-雙向搜索的咬尾碼最大似然譯碼算法[J]. 電子與信息學(xué)報(bào), 2013, 35（5）: 1017-1022.Wang X T, Qian H, and Kang K. Viterbi-bidirectional searching based ML decoding algorithm for tail-biting codes[J]. Journal of Electronics & Information Technology, 2013,35（5）: 1017-1022.

[5] Wu T Y, Chen P N, Pai H T, et al.. Reliability-based decoding for convolutional tail-biting codes[C]. IEEE Vehicular Technology Conference, Taibei, 2010: 1-4.

[6] 3GPP TS. 45.003-3rd generation partnership project;technical specification group GSM/EDGE radio access network; channel coding （release 9）[S]. 2009.

[7] 3GPP TS. 36.212-3rd generation partnership project;technical specification group radio access network; evolved universal terrestrial radio access （E-UTRA）; multiplexing and channel coding （release 8）[S]. 2009.

[8] Williamson A R, Marshall M J, and Wesel R D.Reliability-output decoding of tail-biting convolutional codes[J]. IEEE Transactions on Communications, 2014, 62（6）:1768-1778.

[9] Bin Khalid F, Masud S, and Uppal M. Design and implementation of an ML decoder for tail-biting convolutional codes[C]. IEEE International Symposium on Circuits and Systems, Beijing, 2013: 285-288.

[10] Zhu L, Jiang M, and Wu C. An improved decoding of tail-biting convolutional codes for LTE systems[C]. 2013 International Conference on Wireless Communications &Signal Processing, Hangzhou, 2013: 1-4.

[11] Calderbank A, Forney G Jr, and Vardy A. Minimal tail-biting trellises: the Golay code and more[J]. IEEE Transactions on Information Theory, 1999, 45（5）: 1435-1455.

[12] Wang X T, Qian H, Kang K, et al.. A low-complexity maximum likelihood decoder for tail-biting trellis[J].EURASIP Journal on Wireless Communications and Networking, 2013, 130（1）: 1-11.

[13] Shao R Y, Lin S, and Fossorier M P C. Two decoding algorithms for tailbiting codes[J]. IEEE Transactions on Communications, 2003, 51（10）: 1658-1665.

[14] Pai H T, Han Y, Wu T, et al.. Low-complexity ML decoding for convolutional tail-biting codes[J]. IEEE Communications Letters, 2008, 12（12）: 883-885.

[15] Bocharova I, Johannesson R, Kudryashov B, et al.. BEAST decoding for block codes[J]. European Transactions on Telecommunications, 2004, 15（1）: 297-305.