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

李朋飛，張福洪，易志強(qiáng)

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

?

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

李朋飛，張福洪，易志強(qiáng)

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

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

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

0引言

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

1算法描述

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

).

(1)

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

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

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

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

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

(2)

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

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

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

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

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

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

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

2算法復(fù)雜度分析

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

3仿真及分析

3.1仿真流程

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

3.2結(jié)果分析

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

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

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

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

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

參考文獻(xiàn)

[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].電子與信息學(xué)報(bào),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

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

中圖分類(lèi)號(hào)：TN929.5

文獻(xiàn)標(biāo)識(shí)碼：A

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