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

宋新飛，韓靖楠

(河北工業(yè)大學(xué)，天津 300400)

?

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

宋新飛，韓靖楠

(河北工業(yè)大學(xué)，天津 300400)

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

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

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

LTE系統(tǒng)中，在信道譯碼之前進(jìn)行了子塊交織過程，子塊交織的目的是使信息發(fā)送過程中突發(fā)錯(cuò)誤離散化。雖然經(jīng)過子塊交織過程可以使突發(fā)錯(cuò)誤離散化，但是仍存在整個(gè)待譯碼信息塊誤碼分布不均勻，即信息序列前后半部分的誤碼率分布不均。本文結(jié)合這一特點(diǎn)提出了正逆序結(jié)合譯碼算法。通過實(shí)驗(yàn)發(fā)現(xiàn)，修正算法可以明顯降低誤碼率，性能提升比較明顯。

1 咬尾卷積編碼

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

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

咬尾卷積編碼算法的優(yōu)點(diǎn)是編碼率有所提高，因?yàn)椴恍枰獋鬏旑~外的信息，另外不影響卷積編碼的錯(cuò)誤校驗(yàn)屬性。缺點(diǎn)是譯碼延遲有所增加，因?yàn)楸仨毚_定開始狀態(tài)和回溯的初始狀態(tài)[7]。

圖1 咬尾卷積編碼器結(jié)構(gòu)

2 Viterbi譯碼算法

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

2.1 分支度量單元(BMU)

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

(1)

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

2.2 加比選單元(ACSU)

ACSU作用是從網(wǎng)格圖上選擇一條與接收數(shù)據(jù)距離最小的路徑作為輸出結(jié)果。通過狀態(tài)圖看出從t時(shí)刻的兩個(gè)狀態(tài)到t+1時(shí)刻發(fā)生狀態(tài)的變化，總結(jié)得出規(guī)律：有2N-2個(gè)如上面的子網(wǎng)格圖。從t時(shí)刻的兩個(gè)狀態(tài)轉(zhuǎn)換到t+1時(shí)刻的兩個(gè)狀態(tài)中的一個(gè)，這由輸入決定。

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

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

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

3 正逆序結(jié)合譯碼

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

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

第二步，根據(jù)正序譯碼過程產(chǎn)生的分支度量，找出最優(yōu)路徑對(duì)應(yīng)的K/2處支路度量值和K處支路度量值。

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

圖2 正逆向譯碼流程圖

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

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

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

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

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

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

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

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

4 仿真及分析

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

圖3 數(shù)據(jù)幀長(zhǎng)度為40 bit仿真結(jié)果圖

圖4 數(shù)據(jù)幀長(zhǎng)度為120 bit仿真結(jié)果圖

5 結(jié)束語

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

[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]李小文, 羅友寶.一種應(yīng)用于 LTE 系統(tǒng)的Viterbi譯碼算法[J].電信科學(xué), 2010(7): 99-103.

[4]趙訓(xùn)威.3GPP 長(zhǎng)期演進(jìn)(LTE) 系統(tǒng)架構(gòu)與技術(shù)規(guī)范[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]王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼原理與方法[M].西安：西安電子科技大學(xué)出版社，2001.

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

[10]曾召華.LTE基礎(chǔ)原理與關(guān)鍵技術(shù)[M].西安：西安電子科技大學(xué)出版社, 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

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

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

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

責(zé)任編輯：薛 京