卷積碼編碼與譯碼

卷積碼編碼與譯碼編譯碼原理程序結(jié)果分析

通常卷積碼記為(n，k，N)碼。卷積碼的編碼過程是連續(xù)進(jìn)行的，依次連續(xù)將每k個(gè)信息元輸入編碼器，得到n個(gè)碼元，得到的碼元中的檢驗(yàn)元不僅與本碼的信息元有關(guān)，還與以前時(shí)刻輸入到編碼器的信息元(反映在編碼寄存器的內(nèi)容上)有關(guān)。

不僅要從本碼中提取譯碼信息，還要充分利用以前和以后時(shí)刻收到的碼組．從這些碼組中提取譯碼相關(guān)信息，而且譯碼也是可以連續(xù)進(jìn)行的，這樣可以保證卷積碼的譯碼延時(shí)相對(duì)比較小。通常，在系統(tǒng)條件相同的條件下，在達(dá)到相同譯碼性能時(shí)，卷積碼的信息塊長(zhǎng)度和碼字長(zhǎng)度都要比分組碼的信息塊長(zhǎng)度和碼字長(zhǎng)度小，相應(yīng)譯碼復(fù)雜性也小一些。3例：(n,k,N)=(3,1,3)卷積碼編碼器方框圖設(shè)輸入信息比特序列是

bi-2

bi-1

bibi+1

，則當(dāng)輸入bi時(shí)，此編碼器輸出3比特cidiei，輸入和輸出的關(guān)系如下：bi-2bi輸入bibi-1編碼輸出dicieiM2M3M1實(shí)際應(yīng)用時(shí)常用的卷積碼是(2,1,7)卷積碼例如：IEEE802.11a、DVB-T的內(nèi)碼；(2,1,7)卷積碼的編碼器，如圖：卷積碼的譯碼算法卷積碼的譯碼通常有如下幾個(gè)比較流行的譯碼算法：由Wozencraft和Reiffen在1961年提出，F(xiàn)ano和Jelinek分別在1963年和1969年進(jìn)行改進(jìn)了的序貫譯碼算法。該算法是基于碼字樹圖結(jié)構(gòu)的一種次最優(yōu)概率譯碼算法。電信系08信息工程-11-《信息論與編碼課程設(shè)計(jì)》由Massey在1963年提出的門限譯碼算法。這個(gè)算法利用碼字的代數(shù)結(jié)構(gòu)進(jìn)行代數(shù)譯碼。由Viterbi在1967年提出的Viterbi算法。算法是基于碼字格圖結(jié)構(gòu)的一種最大似然譯碼算法，是一種最優(yōu)譯碼算法。在Viterbi譯碼算法提出之后，卷積碼在通信系統(tǒng)中得到了極為廣泛的應(yīng)用。如GSM、3G、商業(yè)衛(wèi)星通信系統(tǒng)等。維特比譯碼算法使用最廣泛，也是這次課程討論的重點(diǎn)以前面介紹的(3,1,3)卷積碼為例bi-2bi輸入bibi-1編碼輸出dicieiM2M3M1移存器前一狀態(tài)M3

M2當(dāng)前輸入信息位

bi輸出碼元cidiei移存器下一狀態(tài)M3

M2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)abcd000111101110010011100001

在此圖中，虛線表示輸入信息位為“0”時(shí)狀態(tài)轉(zhuǎn)變的路線；實(shí)線表示輸入信息位為“1”時(shí)狀態(tài)轉(zhuǎn)變的路線。線條旁的3位數(shù)字是編碼輸出比特。利用這種狀態(tài)圖可以方便地從輸入序列得到輸出序列。110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100圖中畫出了5個(gè)時(shí)隙。在此圖中，仍用虛線表示輸入信息位為“0”時(shí)狀態(tài)轉(zhuǎn)變的路線；實(shí)線表示輸入信息位為“1”時(shí)狀態(tài)轉(zhuǎn)變的路線?？梢钥闯?，在第4時(shí)隙以后的網(wǎng)格圖形完全是重復(fù)第3時(shí)隙的圖形。這也反映了此(3,1,3)卷積碼的約束長(zhǎng)度為3。網(wǎng)格圖 將狀態(tài)圖在時(shí)間上展開，可以得到網(wǎng)格圖如下：

在上圖中給出了輸入信息位為11010時(shí)，在網(wǎng)格圖中的編碼路徑。圖中示出這時(shí)的輸出編碼序列是：111110010100011…。由上述可見，用網(wǎng)格圖表示編碼過程和輸入輸出關(guān)系比碼樹圖更為簡(jiǎn)練。 有了上面的狀態(tài)圖和網(wǎng)格圖，下面就可以討論維特比解碼算法了。abcdabcd110010001111100(3,1,3)卷積碼 設(shè)現(xiàn)在的發(fā)送信息位為1101，為了使圖中移存器的信息位全部移出，在信息位后面加入3個(gè)“0”，故編碼后的發(fā)送序列為111110010100001011000。并且假設(shè)接收序列為111010010110001011000，其中第4和第11個(gè)碼元為錯(cuò)碼。 由于這是一個(gè)(n,k,N)=(3,1,3)卷積碼，發(fā)送序列的約束度N=3，所以首先需考察nN＝9比特。第1步考察接收序列前9位“111010010”。由此碼的網(wǎng)格圖可見，沿路徑每一級(jí)有4種狀態(tài)a,b,c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑。 現(xiàn)在比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100

例如，由出發(fā)點(diǎn)狀態(tài)a經(jīng)過3級(jí)路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000000000”。它和接收序列“111010010”的漢明距離等于5；下面一條為“111001011”,它和接收序列的漢明距離等于3。同樣，由出發(fā)點(diǎn)狀態(tài)a經(jīng)過3級(jí)路徑后到達(dá)狀態(tài)b、c和d的路徑分別都有兩條，故總共有8條路徑。在下表中列出了這8條路徑和其漢明距離。序號(hào)路徑對(duì)應(yīng)序列漢明距離幸存否1aaaa0000000005否2abca1110010113是3aaab0000001116否4abcb1110011004是5aabc0001110017否6abdc1111100101是7aabd0001111106否8abdd1111101014是

現(xiàn)在將到達(dá)每個(gè)狀態(tài)的兩條路徑的漢明距離作比較，將距離小的一條路徑保留，稱為幸存路徑。若兩條路徑的漢明距離相同，則可以任意保存一條。這樣就剩下4條路徑了，即表中第2,4,6和8條路徑。

第2步繼續(xù)考察接收序列的后繼3個(gè)比特“110”。計(jì)算4條幸存路徑上增加1級(jí)后的8條可能路徑的漢明距離。結(jié)果如下表。 表中最小的總距離等于2，其路徑是abdc+b，相應(yīng)序列為111110010100。它和發(fā)送序列相同，故對(duì)應(yīng)發(fā)送信息位1101。 按照表中的幸存路徑畫出的網(wǎng)格圖示于下圖中。序號(hào)路徑原幸存路徑的距離新增路徑段新增距離總距離幸存否1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4bc37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否