一種應(yīng)用于LTE系統(tǒng)的Viterbi譯碼算法*

李小文，羅友寶

（重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065）

1 引言

在通信系統(tǒng)中，發(fā)送端發(fā)出的信號不可避免地要受到隨機噪聲和突發(fā)噪聲的影響，信號的傳輸波形若受到破壞，則會使接收端可能發(fā)生錯誤判決。消除或降低噪聲干擾的方法包括均衡、提高發(fā)射信號功率等，但是這些方法通常不能滿足傳輸要求。

信道編碼是現(xiàn)代通信系統(tǒng)廣泛采用的一種差錯控制措施。利用將“數(shù)據(jù)序列”轉(zhuǎn)變成“更好的序列”產(chǎn)生冗余比特，這些冗余比特可以用于檢測錯誤和糾正錯誤。

卷積碼是信道編碼中最為重要的一類。根據(jù)卷積碼碼字是否以零比特結(jié)尾，可以分為零尾比特卷積碼(zero-tail CC)和咬尾卷積碼(tail-biting CC)。零尾比特卷積碼有固定的結(jié)尾清零比特作為結(jié)束狀態(tài)，譯碼相對較簡單；咬尾卷積碼沒有結(jié)尾清零比特，編碼時使用數(shù)據(jù)塊的最后m個信息比特來初始化編碼寄存器，使編碼器的初始狀態(tài)和結(jié)束狀態(tài)相同，這樣做可以提高編碼效率，節(jié)約帶寬資源，但對譯碼器來說初始狀態(tài)和結(jié)束狀態(tài)都是未知的，因此也增加了譯碼復(fù)雜度。

目前，在咬尾卷積碼Viterbi譯碼方面的研究主要有以下的情況。

[1]提出了一種自適應(yīng)的循環(huán)Viterbi譯碼算法，并且提出了3種不同的譯碼結(jié)束規(guī)則，不同的結(jié)束規(guī)則，譯碼計算復(fù)雜度和譯碼BER(bit error rate，誤比特率)不同。

·參考文獻(xiàn)[2]基于編碼判決深度，利用Viterbi譯碼的收斂性，提出了一種優(yōu)化的循環(huán)Viterbi譯碼算法。

·參考文獻(xiàn)[3]基于譯碼復(fù)雜度的考慮，提出了一種改進(jìn)的Viterbi譯碼算法，此算法可以將譯碼計算復(fù)雜度降到很低的水平。

·參考文獻(xiàn)[4]基于Viterbi譯碼的碼塊迭代思想，提出了一種環(huán)繞Viterbi譯碼算法，且在此基礎(chǔ)上提出了一種并行譯碼的雙向Viterbi譯碼算法。

·參考文獻(xiàn)[5]提出了一種改進(jìn)的環(huán)繞Viterbi譯碼算法，該算法在每個碼塊譯碼結(jié)束時都判斷當(dāng)前碼塊及之前碼塊是否滿足譯碼輸出條件，通常迭代較少次數(shù)就可以得到正確譯碼。

本文第二部分介紹LTE系統(tǒng)中的咬尾卷積碼，第三部分詳細(xì)分析幾種現(xiàn)有的咬尾卷積Viterbi譯碼算法，主要分析它們的譯碼原理和譯碼計算復(fù)雜度，并提出改進(jìn)的Viterbi譯碼算法；第四部分對幾種算法進(jìn)行仿真，并對仿真結(jié)果進(jìn)行分析，通過對BER及譯碼計算復(fù)雜度進(jìn)行比較，評判譯碼性能的優(yōu)劣。

2 LTE系統(tǒng)中的咬尾卷積碼

LTE作為準(zhǔn)4G技術(shù)，以O(shè)FDM(orthogonal frequency division multiplexing，正交頻分復(fù)用)和MIMO(multipleinput multiple-out-put，多輸入多輸出)技術(shù)為基礎(chǔ)，下行采用正交頻分多址技術(shù)，上行采用單載波頻分多址技術(shù)，在20MHz頻譜帶寬下能夠提供下行100Mbit/s與上行50Mbit/s的峰值速率，降低了系統(tǒng)延遲。

LTE系統(tǒng)采用咬尾卷積碼和Turbo碼來實現(xiàn)前向糾錯[6]，其咬尾卷積編碼器結(jié)構(gòu)如圖1所示，它的限制長度為7，編碼速率為1/3，使用碼塊的最后6 bit信息來初始化6個編碼移位寄存器，促使編碼器的初始狀態(tài)和結(jié)束狀態(tài)相同，從而提高編碼效率。

3 咬尾卷積碼Viterbi譯碼算法

與傳統(tǒng)的Viterbi譯碼不同，咬尾卷積Viterbi譯碼不知道編碼器的初始狀態(tài)和結(jié)束狀態(tài)，因此，譯碼難度增加。本文主要討論咬尾卷積碼的循環(huán)Viterbi譯碼(circular viterbi algorithm)和環(huán)繞Viterbi譯碼 (wrap-around viterbi algorithm)。在以下的討論中，m表示編碼器移位寄存器的個數(shù)，K表示碼塊的長度。

3.1 循環(huán)Viterbi譯碼(CVA)

參考文獻(xiàn)[1]提出的循環(huán)Viterbi譯碼算法可以說是很多改進(jìn)循環(huán)Viterbi算法[2～5]的基礎(chǔ)，其基本思想為：將接收到的碼塊重復(fù)連接，對連接后的長序列進(jìn)行Viterbi譯碼，即譯碼器任意選擇一個初始狀態(tài)或從所有初始化度量相同的狀態(tài)開始進(jìn)行VA譯碼的ACS(add-compare-select，加比選)計算，這樣前一個碼塊的可用信息將傳輸?shù)胶笠粋€碼塊并在后一碼塊中累積，每個碼塊的可用信息將不會被浪費。同時，參考文獻(xiàn)[1]也提出了固定的譯碼結(jié)束規(guī)則和可變的譯碼結(jié)束規(guī)則以及二者兼顧的譯碼結(jié)束規(guī)則，不同的結(jié)束規(guī)則有著不同的譯碼性能，這在后來的改進(jìn)算法中都有所體現(xiàn)。

為了提高譯碼性能，降低譯碼復(fù)雜度，減少譯碼延遲，參考文獻(xiàn)[2]和[3]分別提出了BDD-CVA譯碼算法和Lw-CVA譯碼算法，它們都有固定的譯碼時間，且通常只需將接收碼塊部分重復(fù)。以參考文獻(xiàn) [2]提出的BDD-CVA算法為例，其算法描述為：

a.初始化所有(個)開始狀態(tài)的度量值，一般設(shè)置為0；

b.從開始的個狀態(tài)做VA譯碼的ACS操作，執(zhí)行到時刻t=Linit；

c.在t=Linit時刻選擇路徑度量最小的節(jié)點，清除其他節(jié)點的路徑，然后從選擇的節(jié)點繼續(xù)VA譯碼的ACS操作，直到 t=(2Linit－1)mod K 時刻；

d.譯碼輸出t=Linit時刻的數(shù)據(jù)符號，然后繼續(xù)向后以Lf(Lf≤Linit)為窗滑動做VA譯碼的ACS操作K－1個時刻，到達(dá)t=(Linit+Lf+K－2)mod K時刻，并譯碼輸出剩下的K-1個數(shù)據(jù)符號。

其中Linit、Lf以及后文即將提到的win的具體取值可以參見參考文獻(xiàn)[7]。換個角度看，BDD-CVA可以看作沒有滑窗，而是將碼塊重復(fù)了Linit+Lf-2個時刻，譯碼輸出數(shù)據(jù)為長碼流的中間K個數(shù)據(jù)符號。參考文獻(xiàn)[3]提出的算法(Lw-CVA)與此相似，但它省略了在t=Linit時刻選擇最小路徑度量節(jié)點，清除其他節(jié)點的操作，這在參考文獻(xiàn)[2]中也有所提到，且在實際應(yīng)用中是可容許的，它先將碼塊重復(fù)Linit+win個時刻，對長序列碼塊做Linit+K+win個時刻的VA譯碼，然后選擇最優(yōu)路徑回溯，回溯輸出中間K個時刻的數(shù)據(jù)作為最終的譯碼輸出。可以看出Lw-CVA實質(zhì)為BDD-CVA的簡化，如果把常數(shù)2加進(jìn)Lf，則以上兩種算法就相同了，因此它們的譯碼性能也幾乎是相同的。

以上循環(huán)Viterbi譯碼算法的共同點都是先將譯碼初始狀態(tài)收斂到正確路徑，這樣就必然導(dǎo)致要將碼塊部分重復(fù)(當(dāng)Linit+win﹤K時)，然后才譯碼輸出，最后將譯碼輸出調(diào)整到正確位置，它們的譯碼計算復(fù)雜度均約為(Linit+K+win)×2m。

3.2 環(huán)繞Viterbi譯碼(WAVA)

參考文獻(xiàn)[4]提出了一種環(huán)繞Viterbi譯碼(WAVA)算法，其算法描述為：

a.初始化所有(2m個)初始狀態(tài)的度量值，設(shè)置為0；

b.從開始的2m個狀態(tài)做VA譯碼的ACS操作，迭代完第一個碼塊后，檢查最優(yōu)路徑的首末狀態(tài)是否相同，相同則停止譯碼，輸出譯碼序列，否則進(jìn)入下一步；

c.用上一次迭代結(jié)束的所有狀態(tài)度量來初始化當(dāng)前迭代的所有初始狀態(tài)的度量，然后進(jìn)行VA譯碼的ACS操作，當(dāng)前碼塊迭代完成后檢查最優(yōu)路徑中當(dāng)前碼塊首末狀態(tài)是否相同，相同則輸出當(dāng)前譯碼序列，停止譯碼，否則進(jìn)入下一步；

d.重復(fù)上一步，直到最優(yōu)路徑的首末狀態(tài)相同，或迭代次數(shù)達(dá)到最大；

e.如果最優(yōu)路徑的首尾狀態(tài)不相同，則判斷其他路徑是否首尾狀態(tài)相同，如果找到這一路徑，則輸出對應(yīng)的碼字，否則輸出具有最優(yōu)度量的路徑。

一般情況下，迭代次數(shù)越大，譯碼性能越好，但同時譯碼延遲也隨之增大，因此迭代次數(shù)也是有上限的，對于不同系統(tǒng)的應(yīng)用，應(yīng)綜合考慮譯碼BER和譯碼延遲，從而設(shè)定合適的迭代次數(shù)。參考文獻(xiàn)[5]提出了環(huán)繞Viterbi譯碼算法的一種改進(jìn)算法——L3-WAVA，與WAVA的不同之處在于：在第個碼塊迭代計算法結(jié)束時，它不僅檢查最優(yōu)路徑Plmax(l=1,2,…,L，L為最大迭代次數(shù))的當(dāng)前碼塊l的首末狀態(tài)是否相同，而且還要檢查之前的各碼塊(l-1,l-2,…,1)的首末狀態(tài)是否相同，只要有一個碼塊的首末狀態(tài)相同，則輸出相應(yīng)碼塊的譯碼數(shù)據(jù)，否則繼續(xù)迭代，直到達(dá)到迭代的最大次數(shù)，若仍無首末狀態(tài)相同的碼塊，則輸出第骔L/2」+1個碼塊的譯碼數(shù)據(jù)。

以上兩種WAVA算法都是基于碼塊迭代思想，同時利用Vitrbi譯碼的收斂性，以判斷各個碼塊的首末狀態(tài)是否相同來確定譯碼輸出，如果迭代達(dá)到最大次數(shù)，則輸出指定碼塊的譯碼數(shù)據(jù)作為最終的譯碼輸出，譯碼計算復(fù)雜度均約為（l×K）×2m，（l=1,2,…,L），這樣碼塊經(jīng)過多次迭代，各碼塊攜帶的信息在后來的碼塊累積，可以降低譯碼BER，但由于在譯碼輸出之前通常需要迭代多次，所以BER的降低是以計算復(fù)雜度的增加為代價的。

3.3 改進(jìn)Vitervi譯碼算法(Cd-CVA)

由于LTE系統(tǒng)要求提供更高的數(shù)據(jù)傳輸速率，在保證傳輸可靠性的同時必須盡可能地降低譯碼延遲，因此綜合考慮譯碼BER和譯碼延遲，同時利用Viterbi譯碼的收斂性和編碼判決深度思想，以及WAVA檢查各個碼塊首末狀態(tài)的方法，現(xiàn)在Lw-CVA的基礎(chǔ)上進(jìn)行改進(jìn)，提出一種改進(jìn)的循環(huán)Vitebi算法(Cd-CVA)，其算法示意如圖2所示，圖中虛線部分表示可能不會經(jīng)歷的步驟。

算法描述如下：

a.初始化所有(個)開始狀態(tài)的度量值，設(shè)置為0；

b.從開始的個狀態(tài)做VA譯碼的ACS操作，執(zhí)行到時刻t=(K+Ld)mod K；

c.在t=(K+Ld)mod K時刻選擇最優(yōu)路徑回溯，回溯到t=0時刻，檢查t=0時刻和t=K時刻的狀態(tài)是否相同，相同則譯碼輸出，否則，接著步驟b繼續(xù)執(zhí)行VA算法ACS，直到t=(K+Lc+Ld)mod K時刻；

d.在t=(K+Lc+Ld)mod K時刻選擇最優(yōu)路徑回溯，回溯到t=0時刻，得到最優(yōu)路徑的狀態(tài)序列state_sequence(1,K+Lc+Ld)，用狀態(tài)序列的第K+1,K+2,…,K+Lc個值取代第1,2,…,Lc個值，最后譯碼輸出狀態(tài)序列的前K個值，作為最終譯碼輸出。

其中，Lc為糾正深度，Ld為編碼判決深度[7]，通常我們?nèi)c、Ld為限制長度的4～6倍，Ld≤Lc，稍微增大或減小Lc、Ld值的大小，如加 1或減 1，對譯碼 BER不會造成重大影響。由于回溯一次的時間遠(yuǎn)小于加比選操作的時間，因此,此改進(jìn)算法的譯碼計算復(fù)雜度平均略小于(K+Lc+Ld)×2m。

在t=(K+Ld)mod K時刻回溯一次是非常有必要的，這是利用了參考文獻(xiàn) [1]中提到的K+m算法給出的一種思想，即只在碼塊的末尾重復(fù)一小部分時，原碼塊的首末狀態(tài)可能已經(jīng)相同了，尤其是信噪比大的情況下，此時如果回溯路徑首末狀態(tài)相同，則譯碼輸出是正確的，如果回溯路徑首末狀態(tài)不相同，則路徑的前Lc個狀態(tài)的錯誤率最大，因此必須在K+m算法的基礎(chǔ)上采取糾正措施，即執(zhí)行改進(jìn)算法中的步驟d，最后將路徑中錯誤的狀態(tài)替換掉，保證路徑的首末狀態(tài)相同，從而提高譯碼的正確性。

4 仿真驗證及性能分析

通過仿真各種算法的BER，結(jié)合各算法的譯碼計算復(fù)雜度，比較各算法的性能優(yōu)劣，為LTE系統(tǒng)的實際應(yīng)用提供有力佐證。

4.1 仿真條件設(shè)置及仿真模型

由于在LTE系統(tǒng)中，咬尾卷積編碼主要用于PBCH（物理廣播信道）、PDCCH （物理下行控制信道）、PUCCH（物理上行控制），編碼前的數(shù)據(jù)主要是控制信息和調(diào)度信息，其數(shù)據(jù)量一般都不大，LTE Release8協(xié)議沒有明確規(guī)定碼塊的最大長度，但在LTE協(xié)議的提案中已經(jīng)提出咬尾卷積碼的最大碼塊大小為200 bit，大于200 bit時則采用Turbo編碼[8]。據(jù)此，為了適合大多數(shù)情況，在仿真中設(shè)置碼塊的大小為150 bit，每次對5 000個數(shù)據(jù)塊進(jìn)行仿真統(tǒng)計，假設(shè)調(diào)制方式采用BPSK調(diào)制，信道為加性高斯白噪聲(AWGN)信道，仿真模型如圖3所示。

4.2 仿真結(jié)果分析

圖4同時對K+m算法，BDD-CVA的改進(jìn)算法Lw-CVA，WAVA的改進(jìn)算法L3-WAVA以及文章中提出的新改進(jìn)算法Cd-CVA進(jìn)行了仿真比較，為了便于比較，Linit、win、Lc、Ld 的取值均為 4(m+1)，L3-WAVA 的最大迭代次數(shù)取值為L=3?？梢钥闯?由于K+m算法沒有采取錯誤糾正措施，且m﹤Ld，其BER明顯是最大的；Lw-CVA算法次之，改進(jìn)算法Cd-CVA的BER在Lw-CVA的基礎(chǔ)上有了明顯的降低，且改進(jìn)算法Cd-CVA的譯碼計算復(fù)雜度平均略小于Lw-CVA算法的譯碼計算復(fù)雜度；同改進(jìn)環(huán)繞Viterbi譯碼算法L3-WAVA相比，改進(jìn)算法Cd-CVA幾乎與之有相同的BER，但是改進(jìn)算法Cd-CVA的譯碼計算復(fù)雜度卻大大降低，如果L3-WAVA迭代3次才譯碼結(jié)束，則改進(jìn)算法的譯碼計算復(fù)雜度約為L3-WAVA的1/2。

對于碼塊長度更小的情況，每個碼塊攜帶的可用信息量減少，因此，為了保證譯碼的正確性，可以將糾正深度和編碼判決深度的取值增大。圖5為碼塊長度為40 bit，Linit、win、Lc、Ld 的取值均為 6(m+1)的仿真 結(jié) 果 ，可以看出，即使碼塊更小，改進(jìn)算法的BER仍然比Lw-CVA算法的BER低，與L3-WAVA幾乎相同。因此，根據(jù)咬尾卷積碼碼塊長度的不同，糾正深度和編碼判決深度的取值應(yīng)有所不同，在LTE實際應(yīng)用中可根據(jù)不同的信道自適應(yīng)變化，以適應(yīng)不同信道的譯碼需求。

通過以上分析，改進(jìn)算法不僅降低了譯碼計算復(fù)雜度，譯碼的誤比特率也可以得到較好的效果，因此非常適合LTE系統(tǒng)的要求，可以應(yīng)用于LTE系統(tǒng)實現(xiàn)。

5 結(jié)束語

LTE系統(tǒng)要求提供速率更高的數(shù)據(jù)業(yè)務(wù)，因此對系統(tǒng)的實時性要求也更高，本文針對LTE系統(tǒng)對高速數(shù)據(jù)業(yè)務(wù)以及數(shù)據(jù)傳輸高可靠性的要求，對現(xiàn)有的Viterbi譯碼算法進(jìn)行了詳細(xì)分析，并綜合考慮譯碼時延與譯碼的正確性，利用現(xiàn)有算法的優(yōu)點，提出了新的改進(jìn)算法并進(jìn)行了仿真驗證，仿真結(jié)果表明，改進(jìn)算法有著更好的譯碼性能，因此LTE系統(tǒng)采用本文提出的改進(jìn)譯碼算法來實現(xiàn)具有較好的譯碼性能，值得推廣應(yīng)用。

參考文獻(xiàn)

1 Richard V,CoxAn C,Sundberg W.An efficicent adaptive circular viterbi algorithm for decoding generaliized tailbiting convolutional codes.IEEE Transactions on Communications,1994,43(1):57～68

2 John B A,Stephen M H.An optimal circular viterbi decoder for the bounded distance criterion. IEEE Transactions on Communications,2002,50(11):1736～1742

3 中興通訊股份有限公司.一種咬尾卷積碼的譯碼方法及其譯碼器.中國：200510011625,2006

4 Rose Y,Shao Shulin,Marc P C,Fossorier.Two decoding algorithms for tailbiting codes. IEEE Transactions on Communications,2003,51(10):1658～1665

5 華為技術(shù)有限公司.咬尾卷積碼的譯碼方法和裝置.中國：200810148828,2009

6 3GPP TS 36.212 v8.7.0.Multiplexing and channel coding(release 8),2009

7 Anderson J B,Balachandran K.Decision depths of convolutional codes.IEEE Transactions on Communications,1989,35(2):455～459

8 Motorola,France Telecom,GET,et al.EUTRA FEC Enhancement(R1-061050).ftp://www.3gpp.org,2006