基于Viterbi算法的卷積碼性能分析

1、移動通信原理課程論文基于Viterbi算法的卷積碼性能分析leengsmile 摘要:本文主要對卷積碼編碼和Viterbi譯碼進(jìn)行MATLAB實現(xiàn),并在此基礎(chǔ)上分析移位寄存器對糾錯能力的影響。論文首先根據(jù)MATLAB的存儲特點及函數(shù)特征,主要介紹卷積編碼的原理,同時給出MATLAB實現(xiàn)的核心代碼。然后根據(jù)MATLAB本身擅長矩陣運算的特點,實現(xiàn)了硬判決的維特比譯碼。本文所實現(xiàn)的卷積碼編碼和維特比譯碼程序能夠?qū)?n, k, K n > 1的情況做出正確的編譯碼,解決了部分教科書僅實現(xiàn)了(1, k, K譯碼的情況。文章最后根據(jù)所實現(xiàn)的卷積編碼維特比譯碼程序,分別對n=1和n>1的卷積碼

2、編碼結(jié)構(gòu)的性能進(jìn)行數(shù)值仿真。在一定信噪比下,卷積編碼能夠有效的降低信道誤碼率,n>1的誤碼率在較低信噪比時高于n=1的情況。關(guān)鍵字:卷積碼維特比硬判決Viterbi MATLAB1.引言:為了減小信道噪聲和干擾對譯碼輸出的影響,通常需要對信息碼元進(jìn)行信道編碼。信道編碼在發(fā)送端對信息碼元添加監(jiān)督碼元,在接收端利用信息碼元與監(jiān)督碼元之間的規(guī)律,發(fā)現(xiàn)和糾正差錯,以提高信息碼元傳輸可靠性。卷積碼屬于信道編碼中的非分組編碼,與循環(huán)碼等分組編碼不同,卷積碼通過在碼元之間引入記憶性,使得當(dāng)前編碼輸出與過去時刻的編碼相關(guān)。卷積碼可以表示成(n,k,m,其中k表示每次輸入編碼器的位數(shù),n是每次對應(yīng)輸出的位

3、數(shù),m在本文中定義為約束長度,是編碼器中所能存儲的碼元數(shù)(包括當(dāng)前輸入,m的定義與許多文獻(xiàn)不同。1本文工作主要分為兩部分:1 對卷積碼編譯碼進(jìn)行實現(xiàn)?？紤]到MATLAB的廣泛應(yīng)用,故本文主要針對MATLAB的特點,對卷積碼編碼、維特比譯碼進(jìn)行詳實的敘述,并輔以實例說明。并側(cè)重于編碼的實現(xiàn),一方面是由于MATLAB的特性及提供的數(shù)據(jù)結(jié)構(gòu)所決定,另一方面是由于在本文所實現(xiàn)的卷積碼編碼,與課本中所敘述的方式略有不同,本文將一一介紹這些特點。2 對約束長度m和編碼器輸入位數(shù)k的不同取值進(jìn)行仿真,并總結(jié)其規(guī)律。2.卷積碼編碼:卷積碼可以很容易地通過例子來描述,圖- 1是生成碼率為k/n = 1/2 的卷

4、積碼移位寄存器電路。輸入比特在時鐘處罰下從左邊移入到電路中,每次輸入k = 1 位,分別去兩個模2加法器的輸出值并復(fù)用后得到編碼器的輸出。 圖- 1 編碼為1/2的卷積碼編碼器4在MATLAB中,描述一個卷積碼編碼器需要23個參數(shù),取決于編碼器的前向反饋還是后項反饋:約束長度生成多項式反饋多項式約束長度編碼器的約束長度組成了一個向量,該向量的長度是編碼器框圖中輸入的數(shù)目,向量的各個元素表示了存儲在移位寄存器中的比特數(shù),包括當(dāng)前輸入。生成多項式若卷積碼表示為(n,k,m,則編碼生成矩陣是一個k×n的矩陣,其(i,j元素表示第i 路輸入與第j路輸出的關(guān)系。在MATLAB中可以如下構(gòu)造該矩

5、陣:i.用二進(jìn)制數(shù)據(jù)表示連接情況。若移位寄存器與模2加法器有交點,則在該處標(biāo)”1”,否則標(biāo)”0”。在該二進(jìn)制數(shù)最左邊的比特表示當(dāng)前輸入,最右邊的節(jié)點對應(yīng)著移位寄存器保存的最早的數(shù)據(jù)。ii.從最右邊開始,將二進(jìn)制數(shù)每三位一組轉(zhuǎn)換成八進(jìn)制。若比特數(shù)不是3的倍數(shù),則在最左邊添”0”。(例如,將1101010表示為001 101 010,然后轉(zhuǎn)為八進(jìn)制152在MATLAB中可以用如下指令實現(xiàn)二進(jìn)制到八進(jìn)制的轉(zhuǎn)換:str2num(dec2base(bin2dec('110',8反饋多項式反饋多項式通過一個向量刻畫,向量的長度即為每次輸入的比特數(shù)k,向量的元素用八進(jìn)制表示,該向量表示對每一

6、路輸出的影響。其構(gòu)造方法與生成矩陣相同,首先,用1中所述方式構(gòu)造二進(jìn)制的表示形式,然后將所得的二進(jìn)制轉(zhuǎn)換成八進(jìn)制。若編碼器輸入后項反饋型且是系統(tǒng)的,則編碼矩陣和與系統(tǒng)碼相關(guān)聯(lián)的反饋連接參數(shù)應(yīng)當(dāng)具有相同值。下面的框圖表示一個效率為1/2的具有后項反饋的系統(tǒng)碼編碼器。 圖 - 2 系統(tǒng)碼編碼器的反饋示意圖4由圖- 2可知,編碼器的約束長度為5,編碼器多項式矩陣為37 33,反饋連接多項式為37。由于第一路輸出與系統(tǒng)比特相關(guān)聯(lián),第一個編碼生成多項式與反饋連接多項式相一致。反饋多項式的二進(jìn)制表示形式為1 1 1 1 1,與編碼框圖中的上支路中的二進(jìn)制數(shù)相一致。這些二進(jìn)制數(shù)表示了移位寄存器與模2加法器之

7、間的連接關(guān)系,第一個”1”表示輸入比特。該二進(jìn)制數(shù)的八進(jìn)制表示形式為37。第二路生成多項式為1 1 0 1 1,與下支路的二進(jìn)制數(shù)相對應(yīng),其八進(jìn)制數(shù)為33。在MATLAB中可以調(diào)用poly2trellis函數(shù)將上述三個因素,約束長度、生成多項式、反饋多項式,表示為MATLAB中的Trellis結(jié)構(gòu)。圖- 3是MATLAB中Trellis結(jié)構(gòu)示意圖,編碼器有4個狀態(tài)(二進(jìn)制表示為0011,一位輸入,兩位輸出。實心箭頭表示表示輸入為”0”,虛箭頭表示輸入為”1”,箭頭旁標(biāo)注的八進(jìn)制數(shù)表示輸出。 圖 - 3 trellis 結(jié)構(gòu)中的狀態(tài)轉(zhuǎn)移4在MATLAB中,Trellis結(jié)構(gòu)包含5個屬性,如表-

8、1所示。表 - 1 Trellis 結(jié)構(gòu)屬性及其取值 在表- 1中, 1之間的整數(shù)。i行j列的元素表示若開始狀態(tài)為i-1,當(dāng)輸入比特數(shù)據(jù)為十進(jìn)制的j-1時,所對應(yīng)的下一個狀態(tài)。同樣地,在outputs矩陣中,i行j列的元素表示若開始狀態(tài)為i-1,當(dāng)輸入比特數(shù)據(jù)為十進(jìn)制的j-1時,所對應(yīng)八進(jìn)制輸出。一般地,在MATLAB中,通過poly2trellis函數(shù)可以將約束長度、生成矩陣所表示的編碼器轉(zhuǎn)換為Trellis結(jié)構(gòu)表示的編碼器,而Trellis結(jié)構(gòu)更直觀地體現(xiàn)了輸出、輸入之間的轉(zhuǎn)換關(guān)系。例如,對于圖- 1所表示的編碼器,其約束長度為3,生成矩陣為6 7,則其Trellis結(jié)構(gòu)可以通過如下指令獲

9、得ConstraintLength = 3;CodeGenerator = 6 7;trellis = poly2trellis(ConstraintLength, CodeGenerator;所得到的trellis結(jié)構(gòu)的各個屬性依次為:numInputSymbols: 2numOutputSymbols: 4numStates: 4nextStates: 4x2 doubleoutputs: 4x2 double其中nextStates矩陣,outputs矩陣分別為0 2 0 30 2 1 21 3 3 01 32 1在程序中,卷積碼編碼函數(shù)的聲明為:function code = conv

10、olution_encode(msg, trel其中msg 為待編碼的碼元,用二進(jìn)制表示,trel 為trellis 結(jié)構(gòu)code為卷積碼輸出其實現(xiàn)過程比較容易,只需要通過遍歷,將輸入序列分割、轉(zhuǎn)換成十進(jìn)制,然后不斷查表,更新輸出和當(dāng)前狀態(tài)。其核心實現(xiàn)代碼如下:for i = 1:k:length(msgmsgbin = msg(i : i + k -1;msgdec = bin2dec( .num2str( msgbin(:' .;code(j = outputs(currentStates + 1, msgdec + 1;currentStates = nextStates(cur

11、rentStates + 1, msgdec + 1;j = j + 1;endcode = dec2bin(code, n - 48;仍對于圖- 1所示的編碼電路,當(dāng)待編碼碼元為1 0 1 1 1 1 1 0 0 0 0 0 0編碼輸出為:1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0其中待編碼碼元后的若干個”0”將在Viterbi譯碼中解釋,主要原因是Viterbi譯碼從全0狀態(tài)出發(fā),并最終回到全”0”狀態(tài)。33.維特比譯碼:卷積碼的譯碼可以分為兩類:代數(shù)譯碼的門限譯碼、概率譯碼的序列譯碼與維特比譯碼。1而維特比算法是實現(xiàn)卷積碼最大似

12、然譯碼的巧妙方式。最大似然譯碼的功能是在給定接收到的信道輸出序列的情況下,找出與已發(fā)送序列最相似的碼字序列。2在數(shù)字通信中,通信可靠度一般采用誤碼率P e,最小平均誤碼率等效于最大后驗概率,mmmm mm PP ee =mmmm mm PP (ee |YY =mmmm mm PP (YY PP (CC CC |YY YY YY (1P (Y 為接收信號序列的概率,與譯碼方式無關(guān);e 為差錯序列;C 為接收端恢復(fù)的碼組;C 為發(fā)送的碼組。根據(jù)Bayes 準(zhǔn)則,在信源等先驗概率的條件下,最大后驗概率準(zhǔn)則與最大似然準(zhǔn)則等效。1PP (ee |YY =PP (CC PP (YY |ee (2 若P(C

13、為等概率分布時,有mmmmmmPPCC =CCYY=mmmmmm PP (YY |CC =CC (3 對于二進(jìn)制對稱信道BSC ,最大似然準(zhǔn)則可等效為最小漢明距離準(zhǔn)則,即mmmmmm ll ll PP (YY |CC =CC =mmmm mm dd (YY ,CC =mmmm mm dd (yy ll ,cc ll LL10 (4在維特比譯碼中,硬盤決中采用漢明準(zhǔn)則,軟判決常采用最大似然準(zhǔn)則,本文只考慮硬盤決譯碼方式。維特比硬盤決譯碼算法可以簡單表述如下:i. 路徑度量distance(2, , 2k = , distance(1 = 0前項節(jié)點 prev (x, y= ,其中x = 1,nu

14、mStates y = 1, ,lencode將二進(jìn)制比特流以n 為單位分組,ii. 是否遍歷所有輸入,若是,執(zhí)行vii ,否則初始化最小距離mininumdistance = iii. 第j 組輸入t ,當(dāng)前狀態(tài)依次為s ,下一狀態(tài)為nextStates(s, tiv. 譯碼距離為currentdistance ,并更新到下一狀態(tài)最短距離mininumdistance ,若更新,執(zhí)行iv ,否則執(zhí)行vv.保存前項節(jié)點s ,糾錯后的輸入t vi. distance = mininumdistance ,執(zhí)行iivii. 結(jié)束,回溯,并輸出糾錯后的卷積碼編碼C 在MATLAB 中的核心代碼如下:

15、lenDecode = floor( length(code/n ;prev = inf(numStates, lenDecode;distance = inf(numStates, 1;distance(1, 1 = 0;codedCorreceted = inf(lenDecode, 1;input = inf(numStates, lenDecode;for j = 1:lenDecode % substract the jth convcodebin = code( (j - 1*n + 1 : j*n ;mininumdistance = inf(numStates, 1;for s

16、 = 1 : numStatesfor t = 1 : numInputSymbols % t denoted to be 'input + 1'outputoct = outputs(s, t;outputbit = dec2bin( .oct2dec(outputoct, n .- 48;next = nextStates(s, t + 1; % to index from 1 to 2k,currentdistance = biterr(codebin, outputbit;d = distance(s, 1 + currentdistance;if (d < mi

17、ninumdistance( next, 1mininumdistance( next, 1 = d;prev(next, j = s;input(next, j = t;codedCorreceted(j, 1 = outputoct;endendenddistance = mininumdistance;end在MATLAB中的Viterbi 譯碼函數(shù)聲明為:function decoded, convdecoded = viterbi_decode(.code,ConstraintLength, CodeGenerator 其中code,ConstraintLength, CodeGen

18、erator如前文所述,依次為接收到到的卷積碼編碼信號,約束長度,生成矩陣,其中code可能含有噪聲所致的誤碼。對前文的發(fā)送序列1 0 1 1 1 1 1 0 0 0 0 0 0,其卷積碼輸出為:1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0若在接收端接收到的序列為:0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0其中在1、4、8位已發(fā)生錯誤,經(jīng)過Viterbi譯碼后有1 0 1 1 1 1 1 0 0 0 0 0 0可見經(jīng)Viterbi譯碼,由于信道噪聲等造成的誤碼已被糾正,正由于信

19、道編碼的糾錯特性,才使得通信系統(tǒng)的可靠性得以提高。4.性能仿真:通過MATLAB仿真,得到卷積碼編碼和維特比譯碼下的誤碼率曲線,如圖- 4所示。圖 - 4 約束長度為3,編碼生成矩陣為7 5的誤碼率曲線圖 - 4中的星線是未經(jīng)過編碼的誤碼率曲線,矩形方塊所標(biāo)示的是經(jīng)過如圖 - 1所示的卷積碼模塊編碼,維特比譯碼的誤碼率曲線,其約束長度為3,編碼生成矩陣為7 5。圖 - 6是當(dāng)卷積碼編碼器長度為n=2時的誤碼率性能曲線,其編碼器的編碼結(jié)構(gòu)如圖 - 5所示。圖 - 5 約束長度ConstraintLength = 5 4;編碼生成矩陣為CodeGenerator = 23 35 0; 0 5 13;編碼器示意圖4-5-4-3-2-101234510 101010SNR / dB B E R圖 - 6 不同譯碼長度、編碼生成矩陣下的誤碼率性能比較5. 結(jié)論:通過計算機(jī)仿真可知,通過信道編碼,可以適當(dāng)?shù)募m正信道噪聲造成的誤碼;對于不同的編碼結(jié)構(gòu),一般有著不同的抗噪聲性能;不同的約束長度m 一般靠噪聲性能不同,且對噪聲功率一定的情況下,m 越大,抗噪聲性能越強(qiáng);當(dāng)信道噪聲功率增加,即信噪比下降到約為0dB 時,