李朋飛，張福洪，易志強

(杭州電子科技大學通信工程學院，浙江 杭州 310018)

?

基于SOVA的固定時延咬尾卷積碼譯碼算法

李朋飛，張福洪，易志強

(杭州電子科技大學通信工程學院，浙江 杭州 310018)

摘要：針對咬尾卷積碼最大似然譯碼算法復雜度過高，循環(huán)維特比算法及其低復雜度改進算法譯碼延遲不固定的缺點，提出了一種基于軟輸出維特比譯碼(SOVA)的咬尾卷積碼譯碼算法，算法在降低譯碼復雜度的同時使譯碼算法保持固定的譯碼延遲.算法的主要思想是：在正式譯碼之前，采用經(jīng)過修改的SOVA算法確定編碼寄存器的初始狀態(tài)，進而把咬尾卷積碼的譯碼算法轉(zhuǎn)化為普通卷積碼的譯碼算法.仿真結(jié)果表明，在誤比特率性能上，該算法比較接近最大似然譯碼算法，并且優(yōu)于循環(huán)維特比譯碼算法.

關(guān)鍵詞：咬尾卷積碼；軟輸出viterbi算法；固定時延；軟信息

0引言

咬尾卷積碼常見的譯碼方法有最大似然(Maximum Likelihood，ML)譯碼算法[1]，循環(huán)維特比譯碼算法(Circular Viterbi Algorithm，CVA)[2]，以及基于循環(huán)維特比譯碼的其他改進算法，例如環(huán)繞維特比算法(Wrap Around Viterbi Algorithm，WAVA)[3]，雙回溯循環(huán)維特比算法(Double Traceback Viterbi Algorithm，DTVA)[4].最大似然譯碼算法雖然是咬尾卷積碼的最優(yōu)譯碼算法，但其譯碼的復雜度也是最高的.文獻[5]提出了一種基于ML的改進算法，降低了ML譯碼算法的復雜度.文獻[6]根據(jù)咬尾卷積碼的循環(huán)特性和收斂規(guī)則提出了一種基于維特比算法的改進算法.文獻[7]根據(jù)咬尾卷積碼的循環(huán)特性提出了一種基于軟輸入軟輸出維特比算法的咬尾卷積碼譯碼算法.以上提到的這些算法的迭代次數(shù)隨著信噪比的變化而變化，其譯碼延遲是不固定的.為了解決上述譯碼算法譯碼延遲不固定的缺點，本文提出了一種固定延遲的咬尾卷積碼譯碼算法，算法在降低譯碼復雜度的同時使譯碼算法同樣保持著固定的譯碼延遲.

1算法描述

咬尾卷積碼使用待編碼信息的最后幾個尾比特來初始化編碼寄存器，通過這種方法可以保證編碼寄存器擁有相同的開始和結(jié)束狀態(tài).由于咬尾卷積碼在編碼結(jié)束時不再需要額外的信息來迫使編碼寄存器恢復到某個特定的狀態(tài)，因此其編碼效率要高于普通卷積碼，但其復雜度也明顯高于普通卷積碼.咬尾卷積碼的譯碼算法之所以比普通卷積碼復雜，是因為其譯碼器沒有關(guān)于編碼器起始狀態(tài)的先驗信息.ML譯碼算法通過嘗試每個可能的初始和結(jié)束狀態(tài)來解決這個問題.CVA算法及其改進算法則利用咬尾卷積碼的循環(huán)特性[8]，重復地對接收到的待譯碼信息進行譯碼，直到某次譯碼結(jié)果滿足某個預(yù)先設(shè)定的停止條件或者重復的次數(shù)達到預(yù)先設(shè)定的最大次數(shù)為止.同上述兩類算法不同，本文嘗試在正式的譯碼開始之前，首先確定得到譯碼器的初始狀態(tài)，這樣咬尾卷積碼的譯碼過程將等同于普通卷積碼的譯碼過程.這里提到的初始狀態(tài)并不一定是卷積編碼器編碼開始時的那個狀態(tài)，可以是編碼器在編碼過程中經(jīng)歷過的任意一個狀態(tài).因為咬尾卷積碼具有循環(huán)特性，其編碼過程中的任意一個狀態(tài)都可以作為譯碼過程中的起始狀態(tài).

).

(1)

1)T=0時刻，初始化網(wǎng)格圖中所有狀態(tài)的度量M=0，初始化所有狀態(tài)的軟信息)=+∞；

2)T=T+1時刻，計算網(wǎng)格圖中的每個狀態(tài)的累積度量值；

5)更新軟信息的值.找到T時刻到達各個狀態(tài)的幸存路徑和競爭路徑中判決比特不相同的判決時刻Tr，并從小到大更新Tr對應(yīng)的度量值；

6)回到步驟2，直到處理完所有的待譯碼信息；

7)得到最后的幸存路徑及該幸存路徑上每個狀態(tài)對應(yīng)的軟信息.

(2)

圖1　不同窗口長度下找到錯誤初始狀態(tài)的概率

圖2　調(diào)整前的待譯碼信息

圖3　調(diào)整后的待譯碼信息

1)采用經(jīng)過修改的SOVA算法執(zhí)行第1次譯碼過程；

4)根據(jù)上面找到的位置對待譯碼的信息進行調(diào)整；

5)以步驟3中找到的狀態(tài)作為初始和結(jié)束狀態(tài)，對步驟4中經(jīng)過調(diào)整的待譯碼信息進行維特比譯碼；

5)對步驟5中得到的譯碼結(jié)果進行調(diào)整，得到最后的譯碼結(jié)果.

2算法復雜度分析

下面將以維特比更新次數(shù)為指標，對ML算法、CVA算法以及本文提出的算法的計算復雜度進行分析和比較.假設(shè)編碼器寄存器的個數(shù)為M，待編碼信息的長度為L.對于普通的維特比算法，其每一次更新過程包含2個步驟：2M個狀態(tài)分支累積度量值的計算，到達每個狀態(tài)的幸存路徑的選擇.因此進行1次普通的維特比譯碼總共需要更新(2M×L)次.最大似然譯碼需要2M次互相獨立的維特比譯碼，所以其總的更新次數(shù)為(22M×L)次.循環(huán)維特比算法需要的迭代次數(shù)是不固定的，其迭代的次數(shù)跟信噪比有關(guān)，假設(shè)K為迭代次數(shù)，則該算法總共需要(2M×L×K)次更新操作.本文算法總共需要進行2次維特比運算，其涉及到的更新操作為(2M+1×L)次.確定初始狀態(tài)需要的額外操作包括為了得到軟信息而進行的減法，軟信息的更新以及平均似然值的計算.這些附加的操作只會影響本算法的第1步，與維特比的更新操作相比可以忽略不計，所以新算法需要的總的更新次數(shù)為(2M+1×L)次.從上面的分析可以看出，本文提出的算法的復雜度要遠低于ML譯碼算法.循環(huán)維特比算法的計算復雜度與迭代次數(shù)有關(guān)，是一個不固定的值.本文中算法的計算量是一個固定的值，并不會隨著信噪比改變而改變.

3仿真及分析

3.1仿真流程

本文采用MATLAB對文中提出的譯碼算法及ML和CVA譯碼算法的誤比特率性能進行了仿真.仿真條件如下：仿真時所用的信道為AWGN信道和瑞利衰落信道道，待譯碼數(shù)據(jù)塊的長度分別為80bit和120bit，調(diào)制方式為BPSK調(diào)制，編碼方式采用生成多項式為[171,133]的(2,1,6)咬尾卷積碼.

3.2結(jié)果分析

圖4和圖5分別比較了在AWGN信道和瑞利衰落信道下本文提出的譯碼算法與ML，CVA算法對不同長度待譯碼數(shù)據(jù)塊的誤比特率，從中可以看出本文提出的算法在保持固定譯碼延遲的同時其誤比特率性能仍優(yōu)于CVA算法.

圖4　高斯信道下不同長度待譯碼數(shù)據(jù)的誤碼率曲線

圖5　瑞利衰落信道下不同長度待譯碼數(shù)據(jù)的誤碼率曲線

4結(jié)束語

本文提出了一種固定延遲的咬尾卷積碼譯碼算法，通過研究分析可知，本文提出的新算法在譯碼復雜度上遠低于ML譯碼算法，其譯碼復雜度約為普通維特比譯碼算法的2倍；在高斯信道下與CVA算法相比，新算法的誤比特率性能有了顯著地提高，但在瑞利衰落信道下，新算法的優(yōu)越性并不明顯.因此，進一步提高新算法在瑞利衰落信道下的性能將具有更好的應(yīng)用價值.

參考文獻

[1]PAIHT,HANYS,WUTY,etal.Low-complexityMLdecodingforconvolutionaltail-bitingcodes[J].CommunicationsLetters,IEEE, 2008, 12(12): 883-885.

[2]COXRV,SUNDBERGCEW.AnefficientadaptivecircularViterbialgorithmfordecodinggeneralizedtailbitingconvolutionalcodes[J].VehicularTechnology,IEEETransactionson, 1994, 43(1): 57-68.

[3]SHAORY,LINS,FOSSORIERMPC.Twodecodingalgorithmsfortailbitingcodes[J].Communications,IEEETransactionson, 2003, 51(10): 1658-1665.

[4]MINZ,JUNWEIH,JIEM,etal.Researchonan-baseddecodeoftail-bitingconvolutionalcodesandtheirperformanceanalysesusedinLTEsystem[C]//InformationTechnologyandApplications, 2009.IFITA′09.InternationalForumon.IEEE, 2009, 2: 303-306.

[5]QIANH,WANGX,KANGK,etal.ADepth-FirstMLDecodingAlgorithmforTail-BitingTrellises[J].VehicularTechnology,IEEETransactionson, 2015, 64(8):3339-3346.

[6]LID,YANGJ.Efficientimplementationofthedecoderfortailbitingconvolutionalcodes[C]//SignalProcessing,CommunicationsandComputing(ICSPCC), 2014IEEEInternationalConferenceon.IEEE, 2014: 623-626.

[7]FEDORENKOSV,TREFILOVM,WEIY.Improvedlistdecodingoftail-bitingconvolutionalcodes[C]//ProblemsofRedundancyinInformationandControlSystems(REDUNDANCY), 2014XIVInternationalSymposiumon.IEEE, 2014: 35-38.

[8]王曉濤,劉振華.基于可信位置排序的咬尾卷積碼譯碼算法[J].電子與信息學報,2015，37(7):1575-1579.

TheDecodingAlgorithmofTailbitingConvolutionalCodeBasedonSOVA

LIPengfei,ZHANGFuhong,YIZhiqiang

(School of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China)

Abstract：The complexity of maximum likelihood decoding algorithm for Tailbiting convolutional codes is too high. The delay of circular Viterbi algorithm and its improved algorithm of low complexity for Tailbiting convolutional codes is not fixed. In this paper, we propose a decoding algorithm based on the soft-output Viterbi-algorithm(SOVA), this algorithm reduces the decoding complexity and has a fixed decoding delay. The main idea of the algorithm is to use a modified version of the SOVA to determine the initial state of the encoding register before the formal decoding, and then transform the decoding algorithm of the Tailbiting convolutional codes into the decoding algorithm of the common convolutional code. Simulation results are close to the performance of the maximum-likelihood decoding, and better than the circular Viterbi algorithm.

Key words：Tailbiting convolutional codes; SOVA; fixed delay; soft metric

DOI：10.13954/j.cnki.hdu.2016.04.006

收稿日期：2015-12-16

作者簡介：李朋飛(1989-)，男，河南安陽人，碩士研究生，信號與信息處理.通信作者：張福洪教授，E-mail：fuhong@vip.sina.com.

中圖分類號：TN929.5

文獻標識碼：A

文章編號：1001-9146(2016)04-0024-05