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

王曉濤 劉振華

1 引言

卷積碼在編碼時其編碼器可以用已知比特來初始化，也可以用信息比特來初始化。對于寄存器長度為v的卷積碼編碼器，當采用信息比特的最后v位來初始化編碼器時，編碼結束時編碼器的狀態和其初始狀態是相同的，同時碼字對應的格形圖呈咬尾狀態[1,2]。我們稱這種方式得到的碼字為咬尾卷積碼（Tail-Biting Convolutional Codes, TBCC），其對應的格形圖為咬尾格形圖。

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

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

CVA是一種完全基于Viterbi的譯碼算法，通過在咬尾格形圖多次迭代來尋找最優咬尾路徑及其對應的碼字。傳統的基于CVA的譯碼算法沒有考慮譯碼過程中存在的循環陷阱，這導致譯碼器在譯碼結束時可能無法收斂到最優咬尾路徑，因此是一種次優譯碼算法，如WAVA和ET-CVA等。TD-CVA從循環陷阱出發，通過在迭代過程中對非最大似然狀態的排除，使得譯碼器能最終收斂到全局最優咬尾路徑。

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

本文結構如下，第2節介紹新算法的設計原理，并通過例子給出算法說明，同時對算法的最優性進行證明；第3節給出算法性能仿真驗證；第4節總結全文。

2 算法描述

2.1 變量定義

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

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

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

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

2.2 算法說明

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

其中 s ∈Slopt, i≥1。

算法的步驟描述如下：

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

lopt有循環陷阱產生：

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

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

（b）無循環陷阱：返回步驟2。

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

2.3 最優性證明

由文獻[1]可知，通過對循環陷阱的控制，譯碼算法最終會收斂到，而是譯碼器從位置lopt處開始譯碼得到的最大似然咬尾路徑，因此證明算法的最優性就是證明譯碼結果與起始位置無關。

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

因為（,）P s s是咬尾路徑，由咬尾路徑定義可知該路徑在咬尾格形圖上起始和結束于同一個狀態，且任意位置l處的狀態集合lS中有且僅有一個狀態在咬尾路徑上（非咬尾路徑在起始位置處不滿足此條件）。設（,）P s s經過optlS中的狀態s'，則有

可見P（ s, s）是咬尾格形子圖Tsub（s'）上的咬尾路徑，設Tsub（s'）上的最優咬尾路徑為（s',s'），且其路徑度量值為（s',s'），從而有

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

可見式（8）與假設條件式（4）相矛盾，即譯碼結束時咬尾格形圖上不存在任何咬尾路徑其度量值大于，譯碼過程與譯碼起始位置無關，中保存的即為全局最優咬尾路徑，所以有 Po=證畢

3 仿真驗證

本節通過兩個實驗來驗證本文算法的有效性，為引用方便，將本文算法記為NCVA（New CVA）。此處選用兩種經典算法進行性能比較，WAVA算法和VH算法，這是因為WAVA是咬尾格形圖上基于CVA的經典譯碼算法，而VH算法是咬尾格形圖上基于啟發式搜索的經典算法。編碼以后的比特通過QPSK映射后經過 AWGN信道，接收端接收到信息序列以后分別采用上述3種譯碼算法進行譯碼，譯碼過程中每個譯碼塊的平均訪問狀態數作為衡量譯碼復雜度的標準。

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

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

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

和 TD-CVA[1]相比，本文算法利用了可信位置排序來改進算法的收斂速度。為了驗證可信位置排序對算法收斂速度的改進，表2中給出NCVA在不同Q值下的譯碼復雜度和 TD-CVA算法的譯碼復雜度詳細對比列表。通過對比可以發現以下兩點規律：

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

表2 NCVA與TD-CVA算法復雜度對比

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

（2）當Q值越小時，可靠度的作用越明顯；由于接收序列服從正態分布，因此當Q值越大時，由式（2）計算得到的每個位置的可靠度越接近；極限情況是Q為接收序列的長度，此時每個位置的可靠度完全一樣，那么譯碼從頭開始，復雜度與TD-CVA相同。

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

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

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

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

4 結束語

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

圖3 不同譯碼算法對（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] 王曉濤, 錢驊, 徐景, 等. 基于陷阱檢測的咬尾卷積碼譯碼算法[J]. 電子與信息學報, 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]. 電子與信息學報, 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.