一種咬尾卷積譯碼的修正算法

宋新飛，韓靖楠

(河北工業大學，天津 300400)

?

一種咬尾卷積譯碼的修正算法

宋新飛，韓靖楠

(河北工業大學，天津 300400)

在LTE系統中，物理廣播信道和物理下行控制信道均采用了咬尾卷積編碼，咬尾卷積編碼擁有很多優良的性能。針對咬尾卷積譯碼，提出了一種基于Viterbi譯碼的修正算法——正逆序結合譯碼算法，根據分支度量確定誤碼在數據幀的分布，最后確定采用正序還是逆序譯碼結果。仿真結果表明，Viterbi的修正方法有效地降低了系統誤碼率，而且具有普適性，適合應用于LTE系統。

LTE；正逆序譯碼；咬尾卷積譯碼；Viterbi譯碼

目前咬尾卷積譯碼算法主要存在以下幾種方法：循環Viterbi譯碼(CVA)[1]，它是其他改進的循環Viterbi譯碼算法基礎，其核心思想是將需要譯碼的碼塊重復連接，然后對重復拼接后的長序列譯碼；環繞Viterbi譯碼(WAVA)[2]算法的特點是隨著迭代次數增加，譯碼性能更好，但問題是譯碼延遲也會增加，因此迭代次數必須設置上限，環繞譯碼根據不同應用，綜合考慮譯碼延遲和譯碼BER設置合適的迭代次數；改進的循環Viterbi譯碼算法(Cd-CVA)[3]是將需要譯碼的碼塊重復連接，其復雜度和誤碼率都比較低，目前是比較優良的譯碼算法。

LTE系統中，在信道譯碼之前進行了子塊交織過程，子塊交織的目的是使信息發送過程中突發錯誤離散化。雖然經過子塊交織過程可以使突發錯誤離散化，但是仍存在整個待譯碼信息塊誤碼分布不均勻，即信息序列前后半部分的誤碼率分布不均。本文結合這一特點提出了正逆序結合譯碼算法。通過實驗發現，修正算法可以明顯降低誤碼率，性能提升比較明顯。

1 咬尾卷積編碼

傳統卷積編碼之前編碼器的初始狀態和結束狀態是確定的，咬尾卷積編碼的初始狀態和結束狀態都是確定的，而且是要發送信息的最后6位，這也就決定了譯碼之前不知道初始狀態，譯碼時要嘗試所有狀態，最后根據度量值決定使用哪個路徑，因此可以看出咬尾卷積譯碼比傳統的卷積譯碼算法復雜度高很多，譯碼難度增加[4]。

LTE協議中規定采用編碼效率為1/3、限制長度為7的咬尾卷積編碼，寄存器的起始狀態是發送信息元的末尾6位，這樣使得起始狀態和結束狀態保持一致[5]。如圖1為編碼器結構圖，編碼多項式是：G0=133，G1=171,G2=165[6]。

咬尾卷積編碼算法的優點是編碼率有所提高，因為不需要傳輸額外的信息，另外不影響卷積編碼的錯誤校驗屬性。缺點是譯碼延遲有所增加，因為必須確定開始狀態和回溯的初始狀態[7]。

圖1 咬尾卷積編碼器結構

2 Viterbi譯碼算法

Viterbi算法屬于最大似然算法的范疇，其采用了一種特殊結構——編碼網格(Trellis)，將它的復雜性大大降低了[8]。通過網格圖，算法比較t時刻接收序列和各個狀態距離的大小，保留最優路徑即最大似然路徑。假如到達同一個狀態的有2條路徑，那么保留度量值最小的路徑，將其稱為幸存路徑。從網格圖不斷深入，直到所有狀態都完成上述操作。上面操作會盡早地丟掉可能性小的路徑，這樣會節省資源，減少運算量。譯碼器一般由4部分構成，即分支度量單元( BMU)、加比選單元( ACSU)、幸存路徑存儲單元( SMU)和控制單元(CU)。

2.1 分支度量單元(BMU)

分支度量單元BMU的目的是計算從t時刻接收序列和到達各個狀態期望序列的距離，這個距離是所有可能傳輸碼字的后驗概率的反映。判決距離的方法有兩種：基于歐幾里德距離的軟判決和基于漢明距離的硬判決。硬判決用1 bit表示接收數據經過解調器量化得到的一個碼符號，而軟判決是用幾個比特表示接收數據的一個碼符號。歐幾里德距離的計算公式為

(1)

式中：ri是接收到的3 bit送至譯碼器的符號；ci是期望被傳輸碼字。

2.2 加比選單元(ACSU)

ACSU作用是從網格圖上選擇一條與接收數據距離最小的路徑作為輸出結果。通過狀態圖看出從t時刻的兩個狀態到t+1時刻發生狀態的變化，總結得出規律：有2N-2個如上面的子網格圖。從t時刻的兩個狀態轉換到t+1時刻的兩個狀態中的一個，這由輸入決定。

2.3 幸存路徑存儲單元(SMU)

由于ACSU的判決比特隨著譯碼不斷更新，幸存路徑存儲單元SMU也不斷更新其幸存路徑，選擇其中的一個狀態作為幸存路徑，這就是譯碼結果。目前有2種幸存路徑存儲單元(SMU)實現算法：寄存器交換算法(Register Exchange，RE)和回溯算法(Trace Back，TB)。

本文采用的是TB算法，TB算法會存儲判決比特，等譯到最后時刻后，根據RAM存儲的判決比特沿著網格圖向回搜索，直到最前端，這樣就搜索出了一條譯碼路徑，從而就可以輸出譯碼結果了[9]。

3 正逆序結合譯碼

下面介紹正逆序結合譯碼過程，圖2為正逆向譯碼流程圖。首先，將接收到的數據幀按照基礎算法(所謂基礎譯碼算法就是Viterbi及現有各種改進的Viterbi譯碼算法，本文提出的方法是對基礎算法修正的方法)譯碼(本文稱該過程為為正序譯碼)，然后根據譯碼產生的分支度量確定誤碼在數據幀中的分布情況。如果數據幀前半部分誤碼多于后半部分，譯碼輸出正序譯碼結果；否則將數據幀前后順序顛倒，然后采用和上述同樣的Viterbi基礎譯碼算法譯碼(本文稱該過程為為逆序譯碼)，譯碼輸出逆序譯碼結果。正逆序結合譯碼，具體過程如下：

第一步，首先用基礎譯碼(文章開篇已經介紹基礎譯碼的概念)算法完成正序譯碼。本文采用的基礎算法是改進的循環Viterbi譯碼算法。

第二步，根據正序譯碼過程產生的分支度量，找出最優路徑對應的K/2處支路度量值和K處支路度量值。

第三步，如果K/2處支路度量值的2倍大于K處的，則譯碼輸出正序譯碼結果，結束譯碼過程。反之進行下面的逆序譯碼過程，譯碼輸出逆序譯碼結果。

圖2 正逆向譯碼流程圖

下面介紹逆序譯碼過程，逆序譯碼過程如下：

1)首先，接收完一個數據幀的數據，將整個數據幀前后順序顛倒，即d′(i)=d(K+1-i)，i=1，2，…，K。

2)按照最大似然算法原則開始譯碼第1位，假設末尾狀態為q(嘗試64種狀態)，推出信息第1位的1 bit信息(即發送信息塊的第K位)。

3)根據上面得出的1 bit信息，推出第2狀態(即編碼器的倒數第2狀態)。依次進行譯碼，直到譯到第K+Ld時刻。

4)支路度量值state_pm(q,K+Ld)選出最佳的路徑state_sequence(q,K+Ld)，如果t=K時刻和t=0時刻狀態一樣，則譯碼輸出，否則，接著進行步驟4)譯碼，直到t=(K+Lc+Ld) modK時刻。

5)從t=(K+Lc+Ld) modK時刻找出最優的支路度量值state_pm(q,K+Lc+Ld)，開始從t=(K+Lc+Ld) modK到t=0時刻開始回溯，這條路徑對應的狀態序列是state_sequence(q,K+Lc+Ld)，譯出1到K+Lc個值，將第1,2,…,Lc的值用K+1,K+2,…,K+Lc的值代替，然后輸出替換完的前K個值，即譯碼的最終輸出結果。

6)將上述譯出的信息首末位置顛倒，完成逆序譯碼。

上面的逆序譯碼和正序譯碼采用同樣的基礎譯碼算法——Cd-CVA，修正算法也適用于其他基礎譯碼算法。本文有3個創新之處，第一，提出了一種逆序譯碼方法；第二，提出了用分支度量作為判斷誤碼在數據幀中分布情況的參數(定性給出)；第三，給出了正逆序譯碼結合的譯碼方式，根據度量值情況，決定采用正序譯碼結果還是逆序譯碼結果。

4 仿真及分析

本文采用的仿真軟件是MATLAB，信道是加性高斯白噪聲(AWGN)和瑞利衰落信道，調制方式是LTE協議中規定的QPSK[10]， 幀長度是40 bit和120 bit，仿真次數設置的10 000次。在上述環境下，對最大似然譯碼算法、循環維特比譯碼(Cd-CVA)和正逆序結合譯碼算法(選擇的是對Cd-CVA譯碼算法進行修正)進行仿真比較。如圖3，數據幀長度為40 bit時，Cd-CVA修正之后和之前的比較，誤碼率在10-4和10-5左右時，系統誤碼率性能有大約1 dB左右的增益。如圖4所示，數據幀長度為120 bit時，Cd-CVA修正后比之前也有一定的性能增益，本次實驗中，經過修正的算法從4 dB開始，誤碼得到完全糾正，而Cd-CVA從5 dB開始得到完全糾正。

圖3 數據幀長度為40 bit仿真結果圖

圖4 數據幀長度為120 bit仿真結果圖

5 結束語

本文對現有的咬尾卷積譯碼算法進行了修正，本修正方法可以進一步研究，可以嘗試應用到其他編碼的譯碼算法過程中，比如Turbo譯碼。本文對Cd-CVA算法修正之前和之后進行了MATLAB仿真。仿真結果表明，修正的方法能有效降低系統誤碼率，本方法對其他基礎譯碼算法具有普適性，也可以對其他Viterbi譯碼算法進行修正，修正方法適合應用到LTE系統。

[1]RICHARD V, COXAN C, SUNDBERG W.An efficient adaptive circular Viterbi algorithm for decoding generaliized tailbiting convolutional codes[J].IEEE Trans.Communications, 1994, 43(1): 57-68.

[2]SHAO R Y, LIN S, FOSSORIER M P C.Two decoding algorithms for tailbiting codes[J].IEEE Trans.Communications, 2003, 51(10): 1658-1665.

[3]李小文, 羅友寶.一種應用于 LTE 系統的Viterbi譯碼算法[J].電信科學, 2010(7): 99-103.

[4]趙訓威.3GPP 長期演進(LTE) 系統架構與技術規范[M].北京：人民郵電出版社, 2010.

[5]ZHU L, JIANG M, WU C.An improved decoding of tail-biting convolutional codes for LTE systems[C]//Proc.IEEE International Conference on Wireless Communications & Signal Processing.[S.l.]：IEEE Press, 2013: 1-4.

[6]YAO Yafu，LIU Kan.Genetic neural network based traffic flow forecasting research[J].Highways & Automotive Applications，2007(6)：28-30.

[7]SESIA S, TOUFIK I, BAKER M.LTE，The UMTS long term evolution: from theory to practice[EB/OL].[2014-10-10].http://www.ebookee.net/LTE-The-UMTS-Long-Term-Evolution-From-Theory-to-Practice_2875037.html.

[8]王新梅，肖國鎮.糾錯碼原理與方法[M].西安：西安電子科技大學出版社，2001.

[9]李剛, 黑勇, 喬樹山，等.一種高速Viterbi譯碼器的設計與實現[J].電子器件, 2007(5)：1886-1889.

[10]曾召華.LTE基礎原理與關鍵技術[M].西安：西安電子科技大學出版社, 2010.

Modified Algorithm of Tail Biting Convolutional Decoding

SONG Xinfei, HAN Jingnan

(HebeiUniversityofTechnology,Tianjin300400,China)

In the LTE system, the physical broadcast channel and the physical downlink control channel uses tail biting convolutional coding, and tail biting convolutional code has many excellent properties.In this paper, a modified decoding algorithm which calls the positive and revers e decoding algorithm is proposed, according to the branch metric to determine distribution of bit errors in the data frame.Finally, determine the positive or reverse decoding as the results.The simulation results show that the modified Viterbi method can effectively reduce the system bit error rate and is universal, suitable for LTE system.

LTE；positive and reverse decoding；tail biting convolutional decoding；Viterbi decoding

TN929.53

A

10.16280/j.videoe.2015.07.016

2014-11-10

【本文獻信息】宋新飛，韓靖楠.一種咬尾卷積譯碼的修正算法[J].電視技術,2015，39(7).

宋新飛(1988— )，碩士生，主研LTE物理層通信協議及下行物理廣播信息提取；

韓靖楠(1990— )，女，碩士生，主研自動控制數據挖掘算法。

責任編輯：薛 京