卷積碼的維特比譯碼PPT課件

1、.,1,卷積碼是把信源輸出的信息序列，以k個碼元劃分為一段，通過編碼器輸出長為n(k）的一段碼段。但是該碼段的n-k個校驗元不僅與本組的信息元有關(guān)，而且也與其前m段的信息元有關(guān)，稱m為編碼存貯，卷積碼用(n，k，m）表示。,卷積碼的概念,.,2,卷積碼的表示方法,矩陣表示法,碼樹圖表示法,多項式表示法,網(wǎng)格圖表示法,狀態(tài)圖表示法,.,3,矩陣表示,當(dāng)m=2,A0=(1 1)T，A1=(0 1)T，A2=(1 1)T時，如前3個輸入為110，則前6個輸出為111010,.,4,多項式表示法,如果把輸入信息序列M和輸出信息序列C都寫成遲延操作數(shù)D的函數(shù)形式：,因此，卷積碼編碼過程的多項式表示形式為

2、,M(D)中每一項的系數(shù)是一個k重向量，而C(D)中每一項的系數(shù)是一個n重向量(子碼)，若把式C(D)中所有系數(shù)(子碼)的第j(j=1,2,n0)個分量寫成多項式C (j)(D),則,.,5,(2,1,2)碼狀態(tài)圖,狀態(tài)圖表示法,以兩個D觸發(fā)器的組合值為狀態(tài)，如D1D2，描述從當(dāng)前狀態(tài)在不同的輸入時的輸出及將到達(dá)的狀態(tài)，每個分支上的標(biāo)注為y1y2，表示當(dāng)前的輸出。,.,6,樹形圖表示,碼樹由分支和節(jié)點組成，各連續(xù)的分支稱為路徑，他們對應(yīng)了不同的碼序列。以m=2，A0=(1 1)T，A1=(0 1)T，A2=(1 1)T為例，如前3個輸入為110，則前6個輸出為111010,.,7,網(wǎng)格圖表示法

3、,狀態(tài)流圖展示了狀態(tài)轉(zhuǎn)移的去向,但不能記錄狀態(tài)轉(zhuǎn)移的軌跡，網(wǎng)格圖可與以彌補這一缺點,使編碼的全過程躍然紙上。網(wǎng)格圖以狀態(tài)為縱軸，將狀態(tài)轉(zhuǎn)移按時間順序展開，用于描述從第k時刻的編碼器狀態(tài)到第k+1時刻的編碼狀態(tài)的轉(zhuǎn)移情況，以及在轉(zhuǎn)移過程中的輸出情況。狀態(tài)與狀態(tài)轉(zhuǎn)移的定義畫法與流圖法一樣 (圖見下頁)。,.,8,00,00,00,00,00,00,00,00,00,00,11,11,11,11,11,11,11,11,11,11,10,10,10,10,10,10,10,10,01,01,01,01,圖例 輸入比特0 輸入比特1,01,01,01,(2,1,2)截斷籬狀圖,.,9,編碼輸出,(2,

4、1,2)碼編碼電路,碼編碼電路解析,信息元輸入M,對信息序列M進行編碼之前，先將它每k個碼元分成一組，在每單元時刻內(nèi)，k個碼元串行輸入到編碼器。信息序列M=m0(1) m1(1) ,其中ml(1)表示在第l個時刻的第k=1個信息元。,編碼器由m+1個移位寄存器組構(gòu)成，每個移位寄存器組內(nèi)有k級寄存器。Di存儲當(dāng)前輸入的碼組，Di-1，Di-m存儲前m個碼組，這正體現(xiàn)了卷積碼“每個碼中的碼元不僅與此時刻的信息元有關(guān)，而且還與前m個時刻的信息元有關(guān)”的特性。,模2加法器是將與其相關(guān)的信息元進行模2 加，加法法則為：,用g(i,j)表示常數(shù)乘法器, 共有(m+1)*n個,(i=1,2, ,k;j=1,

5、2, ,n)。g(i,j)=1時常數(shù)乘法器為一條直通的連接線; g(i,j)=0時沒有連接線。,開關(guān)K在每一節(jié)拍中移動n次，每一次輸入k個信息元而輸出年n個碼元。,輸出碼子C是： Ci=Mi*Gi,.,10,維特比譯碼的描述,從第1時刻的全零狀態(tài)開始(零狀態(tài)初始度量為0，其它狀態(tài)初始度量為負(fù)無窮） 在任一時刻t，對每一個狀態(tài)只記錄到達(dá)路徑中度量最大的一個(殘留路徑）及其度量(狀態(tài)度量） 在向t+1時刻前進過程中，對t時刻的每個狀態(tài)作延伸，即在狀態(tài)度量基礎(chǔ)上加上分支度量，得到M*2k條路徑 對所得到的t+1時刻到達(dá)每一個狀態(tài)的2k條路徑進行比較，找到一個度量最大的作為殘留路徑 直到碼的終點，如果

6、確定終點是一個確定狀態(tài)，則最終保留的路徑就是譯碼結(jié)果,.,11,10,00,01,11,01,11,(2,1,2)碼維特比譯碼過程,分步度量的計算：就是求接收碼子(10)與狀態(tài)輸出碼子(00)之間的漢明距離，即對應(yīng)位不同的個數(shù)(1)。,累加度量的計算:就是求前一時刻的累加度量(1)與該時刻的分步度量(1)的和(2)。,在深度l=m(=2)，2km(4)個狀態(tài)都只有一條分支與之對應(yīng)，故在此之前各時刻個分支都作為信存路徑保留；在此之后，各狀態(tài)都有2k(2)個分支輸入和輸出，此時就要對分支進行選擇。,信存路徑選擇：對進入同一狀態(tài)的2k(2)條分支分別計算(2和3)并比較其累加度量，保留累加度量最小(

7、2)的分支為信存路徑，舍去累加度量大(3)的分支。,深度l=L(=5)(L 是編碼器所處理的信息序列長度 )時刻以后，編碼器就會被已知的0信息比特序列清零，這使得譯碼器強迫所有的路徑返回全零狀態(tài)并完成譯碼。,說明：消息序列m是進入編碼器的序列，發(fā)送序列U是編碼器輸出，接收序列R是經(jīng)信道傳輸后的譯碼器輸入，譯碼序列C是譯碼器輸出。白色碼子是編碼器清零的冗余信息，紅色比特是發(fā)生錯誤的比特位。,譯碼結(jié)果分析,.,12,維特比譯碼收尾,最大似然序列譯碼要求序列有限，因此對卷積碼來說，要求能收尾。 收尾的原則：在信息序列輸入完成后，利用輸入一些特定的比特，使M個狀態(tài)的各殘留路徑可以到達(dá)某一已知狀態(tài)(一般

8、是全零狀態(tài)）。這樣就變成只有一條殘留路徑，這就是最大似然序列。,.,13,卷積碼收尾的實現(xiàn),非遞歸卷積碼：約束長度為m+1的卷積碼，只要在信息序列輸入完成后連續(xù)送入m個0，即可使任一路徑都到達(dá)最終的狀態(tài)0。 遞歸卷積碼：也可通過將輸入值置成反饋值的負(fù)值，而使m個時鐘后的狀態(tài)到達(dá)0。,.,14,卷積碼收尾,非系統(tǒng)非遞歸碼 遞歸系統(tǒng)碼,.,15,維特比譯碼的復(fù)雜度,對信息序列長度為L，信息符號取自GF(p)，R=k/n，約束長度為m+1的卷積碼。狀態(tài)數(shù)為pkm，因此對每個時刻要做pkm次加比選得到pkm個狀態(tài)的殘留路徑，每次加比選包括pk次加法和pk-1次比較。因此總運算量約為Lpkm次加比選。同

9、時要能保存pkm條殘留路徑，因此需要Lpkm個存貯單元。,.,16,維特比譯碼的特點,維特比算法是最大似然的序列譯碼算法 譯碼復(fù)雜度與信道質(zhì)量無關(guān) 運算量與碼長呈線性關(guān)系 存貯量與碼長呈線性關(guān)系 運算量和存貯量都與狀態(tài)數(shù)呈線性關(guān)系 狀態(tài)數(shù)隨分組大小k及編碼深度m呈指數(shù)關(guān)系,.,17,吞吐量與存儲量,運算量與碼長呈線性關(guān)系意味著平均吞吐量與碼長無關(guān)。 存貯量與碼長呈線性關(guān)系意味著對無限碼長(流的情況）要求有無限的存貯量。,.,18,狀態(tài)數(shù)對維特比譯碼的影響,由于運算量與k和m呈指數(shù)關(guān)系，因此維特比譯碼算法一般只適合于k和m較小的場合。大多數(shù)情況下k=1，m10。 對狀態(tài)數(shù)很大的卷積碼，維特比算法要經(jīng)一定的修正后才可能實用，常用的算法是縮減狀態(tài)的維特比譯碼，即在每一時刻，只處理部分的狀態(tài)。,.,19,序列譯碼與維特比譯碼的比較,信道質(zhì)量對前者運算量影響較大，而對后者運算量沒有影響 前者是次優(yōu)的，后者是最優(yōu)的 前者運算量與約束長度無關(guān)，而后者運算量與約束長度呈指數(shù)關(guān)系 前者會有譯碼失敗，而后者只有譯碼錯誤 在不同場合有不同用途,.,20,10,10,01,01,11,S0,0,0,0,特別說明： 1、左圖中黃色方框表示輸入，紅色方框表示移位器； 2、將初始狀態(tài)定為00將字符用不同顏色表示，只是用于方便區(qū)別字符，