數(shù)字電視卷積碼

1、15.8卷積碼卷積碼21 卷積碼的一般概念卷積碼的一般概念 卷積碼與分組碼的區(qū)別：卷積碼與分組碼的區(qū)別：本組的碼元不僅與本組的本組的碼元不僅與本組的k個信息元有關(guān)，個信息元有關(guān)，而且還與以前若干時刻輸入至編碼器的信而且還與以前若干時刻輸入至編碼器的信息元有關(guān)。息元有關(guān)。譯碼時，不僅從此時刻收到的譯碼時，不僅從此時刻收到的n個碼元中提個碼元中提取譯碼信息，而且還利用以后若干時刻收取譯碼信息，而且還利用以后若干時刻收到的碼組提取有關(guān)譯碼信息。到的碼組提取有關(guān)譯碼信息。卷積碼各碼組之間不再是相互獨立。卷積碼各碼組之間不再是相互獨立。3卷積碼的編碼器可以看作是一個由卷積碼的編碼器可以看作是一個由k個輸

2、入端和個輸入端和n個輸出端組成的時序網(wǎng)絡(luò)。個輸出端組成的時序網(wǎng)絡(luò)。設(shè)第設(shè)第i時刻輸入編碼器的時刻輸入編碼器的k個信息為：個信息為：mi（mi(1)，mi(2)，mi(k)）相應(yīng)輸出是由相應(yīng)輸出是由n0個碼元組成的子碼：個碼元組成的子碼：ci（ci(1)，ci(2)，ci(n)）4若輸入的信息序列：若輸入的信息序列：m（m0,m1,m2, ）則輸出由子碼則輸出由子碼C（c0,c1,c2, ），），定義：定義：如果如果n位長的子碼中，前位長的子碼中，前k位是原輸入位是原輸入的信息元，則稱該卷積碼為的信息元，則稱該卷積碼為系統(tǒng)碼系統(tǒng)碼，否則稱，否則稱為非系統(tǒng)碼。為非系統(tǒng)碼。5如圖二進(jìn)制卷積碼編碼器：

3、如圖二進(jìn)制卷積碼編碼器：第第i i時刻輸入信息元時刻輸入信息元m mi i，此時刻的子碼：，此時刻的子碼：c ci i（m mi i，p pi,1i,1，p pi,2i,2）, p, pi,1i,1，p pi,2i,2為校驗元為校驗元且滿足：且滿足：ci(1) m mi i ci(2) p pi,1i,1m mi im mi-1i-1 ci(3) p pi,2i,2m mi im mi-2i-26下一個時間單位輸入的信息元為下一個時間單位輸入的信息元為mi+1，則對應(yīng)的校，則對應(yīng)的校驗元：驗元：ci1(2) p pi i1,11,1m mi i1 1m mi i ci1(3) p pi i1,

4、21,2m mi i1 1m mi-1i-1第二個子碼第二個子碼ci1（ mi+1 ， ci1(2) ， ci1(3) ）如此每時刻送入編碼器如此每時刻送入編碼器1 1個（可為個（可為k k個）信息元，編個）信息元，編碼器就送出相應(yīng)的碼器就送出相應(yīng)的3 3個（可為個（可為n n個）碼元組成一個子個）碼元組成一個子碼碼c ci i送入信道。送入信道。這這n n個碼元組成的子碼個碼元組成的子碼c ci i稱為卷積碼的一個碼段或稱為卷積碼的一個碼段或子組。子組。7顯然，第顯然，第i時刻輸入的信息時刻輸入的信息組組mi及相應(yīng)碼段及相應(yīng)碼段ci，不僅，不僅與前與前m2個碼段中的碼個碼段中的碼元有關(guān)，而且

5、也參與了元有關(guān)，而且也參與了后后m個碼段中的校驗運算。個碼段中的校驗運算。如圖，組成卷積碼的一如圖，組成卷積碼的一個碼序列，產(chǎn)生（個碼序列，產(chǎn)生（3,1,2）系統(tǒng)卷積碼，系統(tǒng)卷積碼，或（或（n,k,m）卷積碼。）卷積碼。8描述卷積碼的主要術(shù)語：描述卷積碼的主要術(shù)語： 輸入幀：輸入幀：每個時刻同時輸入編碼器信息組中的每個時刻同時輸入編碼器信息組中的比特數(shù)（信息元個數(shù)），用比特數(shù)（信息元個數(shù)），用k表示。表示。 輸出幀：輸出幀：每個時刻同時從編碼器輸出的比特數(shù)每個時刻同時從編碼器輸出的比特數(shù)（輸出一個子碼中碼元的個數(shù)），用（輸出一個子碼中碼元的個數(shù)），用n表示。表示。 儲存階數(shù)（編碼儲存）：儲存階

6、數(shù)（編碼儲存）：表示輸入信息組在編表示輸入信息組在編碼器中需存儲的單位時間，即產(chǎn)生輸出比特的碼器中需存儲的單位時間，即產(chǎn)生輸出比特的過程中移位寄存器的最大級數(shù)，用過程中移位寄存器的最大級數(shù)，用m表示。表示。 編碼約束度：編碼約束度：表示編碼過程中相互約束的子碼表示編碼過程中相互約束的子碼個數(shù)，用個數(shù)，用Nm1表示。表示。9 編碼約束長度：編碼約束長度：表示編碼過程中相互約束表示編碼過程中相互約束的碼元數(shù)目，用的碼元數(shù)目，用NANn表示。表示。 參數(shù)參數(shù)m，N，k，n反映了編碼器的復(fù)雜程反映了編碼器的復(fù)雜程度，所以卷積碼一般用（度，所以卷積碼一般用（n，k，m）或）或（n N ，kN）表示，）表

7、示，k和和n比分組碼的比分組碼的k和和n通通常要小。常要小。 比值比值Rk/n為卷積碼的碼率，是衡量卷積為卷積碼的碼率，是衡量卷積碼傳輸信息有效性的一個重要參數(shù)。碼傳輸信息有效性的一個重要參數(shù)。102 卷積碼的矩陣描述和多項式表示卷積碼的矩陣描述和多項式表示根據(jù)（根據(jù)（3，1，2）卷積碼編碼器框圖，設(shè)編碼）卷積碼編碼器框圖，設(shè)編碼器的初始狀態(tài)全為器的初始狀態(tài)全為0，輸入信息序列分別為：，輸入信息序列分別為：m1（100），），m2（0100），），m3（00100），），則編碼器相應(yīng)輸出的碼序列分別為：則編碼器相應(yīng)輸出的碼序列分別為：c1（111 010 001 000 000）c2（000

8、111 010 001 000 000）c3（000 000 111 010 001 000 000）11當(dāng)輸入信息序列：當(dāng)輸入信息序列：mm1m2m3則輸出碼序列：則輸出碼序列：cc1c2c3用矩陣表示：用矩陣表示：可見，卷積碼生成矩陣可見，卷積碼生成矩陣G是一個半無限矩陣，是一個半無限矩陣，有無限個行與列，且每一行都是前一行右移有無限個行與列，且每一行都是前一行右移3（即（即n）位的結(jié)果。）位的結(jié)果。12G可以完全由它的第一行決定，寫成：可以完全由它的第一行決定，寫成： g111,010,001,000,000, g0,g1,g2,0,0,稱稱g為基本生成矩陣為基本生成矩陣，其中，其中g(shù)0

9、，g1，g2等都是一個等都是一個13階（即階（即kn階）矩陣。階）矩陣。延遲算子延遲算子D：表示卷積碼編碼過程中一個單位時間：表示卷積碼編碼過程中一個單位時間（n個碼元）的延遲。個碼元）的延遲。則則G可寫成：可寫成：13基本生成矩陣基本生成矩陣g的性質(zhì)：的性質(zhì)：1）（）（3，1，2）卷積碼中，）卷積碼中，g(1)（g0,g1,g2） 可以完全確定可以完全確定g，g(1)稱為該碼的生成元稱為該碼的生成元。2）每一個）每一個gi（i=0,1,2）由）由n3個數(shù)字決定，個數(shù)字決定， 將其第一個分量取出組成一個將其第一個分量取出組成一個3維向量，即：維向量，即： g(1,1)（100），是產(chǎn)生碼元），

10、是產(chǎn)生碼元ci(1)的抽頭，的抽頭， 同理：同理：g(1,2)、g(1,3)是產(chǎn)生碼元是產(chǎn)生碼元ci(2)、ci(3) 的抽頭，的抽頭，稱稱g(1,1)、 g(1,2)、g(1,3)為該碼的為該碼的 子生成元。子生成元。14結(jié)論：結(jié)論：只要已知一個卷積碼的所有只要已知一個卷積碼的所有子生成元子生成元，該碼的生成元該碼的生成元g(1)和基本生成矩陣和基本生成矩陣g就被確定，就被確定，因而可相應(yīng)確定碼的生成矩陣因而可相應(yīng)確定碼的生成矩陣G。子生成元的物理意義：子生成元的物理意義：是編碼器電路中產(chǎn)生子是編碼器電路中產(chǎn)生子碼各碼元對應(yīng)存儲器上的抽頭。因而，若一個碼各碼元對應(yīng)存儲器上的抽頭。因而，若一個

11、卷積碼編碼器的存儲器級數(shù)與產(chǎn)生碼序列各抽卷積碼編碼器的存儲器級數(shù)與產(chǎn)生碼序列各抽頭確定了，子生成元也就確定了。頭確定了，子生成元也就確定了。由子生成元，將由子生成元，將G寫成寫成D的函數(shù)形式：的函數(shù)形式：G(D)為（為（n0,k0,m）卷積碼的生成多項式矩陣）卷積碼的生成多項式矩陣15把信息序列把信息序列M（11100）也寫成）也寫成D的函數(shù)：的函數(shù)：相應(yīng)的碼序列：相應(yīng)的碼序列：稱稱C(D)為卷積碼碼序列的多項式，其每一系數(shù)為卷積碼碼序列的多項式，其每一系數(shù)ci由由n0個分量組成，將所有系數(shù)（子碼）的第個分量組成，將所有系數(shù)（子碼）的第j（j=1,2,.n0）個分量寫成多項式）個分量寫成多項式

12、C(j)(D)：16（3，1，2）卷積碼中：）卷積碼中：因此，一旦因此，一旦C(j)(D)確定，則完全確定了確定，則完全確定了C(D)，所，所以，編碼器的任務(wù)是如何由以，編碼器的任務(wù)是如何由M(D)得到得到C(j)(D)由由CMG，可得，可得C(D)的多項式：的多項式：17顯然，與先前得到的顯然，與先前得到的C(D)結(jié)果完全相同。結(jié)果完全相同。又：又：G(D)C(D)/M(D)，是輸出與輸入之比。，是輸出與輸入之比。18例：例：k01時，卷積碼的生成矩陣和生成元：時，卷積碼的生成矩陣和生成元：如圖為信息元并行輸入的（如圖為信息元并行輸入的（3，2，2）系統(tǒng)卷）系統(tǒng)卷積碼的編碼器，設(shè)編碼器的初始

13、狀態(tài)全為積碼的編碼器，設(shè)編碼器的初始狀態(tài)全為0，輸入信息序列：輸入信息序列：19若第一個信息序列：若第一個信息序列： M(1) （10，00，00，）則相應(yīng)的輸出碼序列：則相應(yīng)的輸出碼序列： C(1)（c0(1)，c1(1)，c2(1)， ） （101，000，001，000，000，）當(dāng)當(dāng)M(2) （01，00，00，）則則C(2)（c0(2)，c1(2)，c2(2)， ） （011，001，000，000，）20所以，當(dāng)所以，當(dāng) MM(1)M(2) （11，00，00，）則相應(yīng)輸出的碼序列：則相應(yīng)輸出的碼序列：21顯然，若輸入信息序列：顯然，若輸入信息序列：則相應(yīng)輸出的碼序列：則相應(yīng)輸出的

14、碼序列：22寫成矩陣形式：寫成矩陣形式：顯然，顯然， G完全由最上面兩行決定，則完全由最上面兩行決定，則G的的基本生成矩陣：基本生成矩陣：Ik0p00陣陣p1p223所以：所以：gg0 g1 g2 0 上式中，從上式中，從m13段以后開始，取值均為段以后開始，取值均為0，說明某一時刻輸入的信息元，至多只影響說明某一時刻輸入的信息元，至多只影響此時刻和以后此時刻和以后m個單位時間的子碼，而在個單位時間的子碼，而在m1個時間單位以后，信息元已移出編碼個時間單位以后，信息元已移出編碼器，不再對以后各段子碼的編碼發(fā)生影響。器，不再對以后各段子碼的編碼發(fā)生影響。24由于由于k02，就有，就有2個生成元：

15、個生成元： g(1)101，000，001 g(2)011，001，001生成元與子生成元的關(guān)系為：生成元與子生成元的關(guān)系為：所以，只要碼的生成元和子生成元被確定，則所以，只要碼的生成元和子生成元被確定，則碼的碼的G也就完全確定了。也就完全確定了。25利用子生成多項式，將利用子生成多項式，將G表示為：表示為：由編碼器輸出的碼序列：由編碼器輸出的碼序列：263 卷積碼的一致校驗矩陣卷積碼的一致校驗矩陣 卷積碼是線性碼，也與分組碼一樣，生成卷積碼是線性碼，也與分組碼一樣，生成陣與校驗陣之間必滿足：陣與校驗陣之間必滿足： （n0,k0,m）卷積碼校驗矩陣的一般形式：）卷積碼校驗矩陣的一般形式：校驗陣

16、也是半無限的，校驗陣也是半無限的，其中：其中：h0,h1.hm及及0均是均是（n0-k0）n0階陣。階陣。空白處為空白處為027（3,2,2）卷積碼的卷積碼的生成陣：生成陣：由：由：28可得到：可得到：因而該碼的校驗矩陣：因而該碼的校驗矩陣：顯然，校驗陣完全由其第一列元素決定。顯然，校驗陣完全由其第一列元素決定。29（n0,k0,m）系統(tǒng)卷積碼的一致校驗矩陣：）系統(tǒng)卷積碼的一致校驗矩陣： 定義該陣的第定義該陣的第m+1行元素所組成的陣為行元素所組成的陣為碼的碼的基本校驗矩陣基本校驗矩陣：(n0-k0)k0階矩陣，是階矩陣，是生成陣中生成陣中P0,Pm的轉(zhuǎn)置陣的轉(zhuǎn)置陣第第m+1行行(n0-k0)

17、(n0-k0)階階單位矩陣單位矩陣空白處全為空白處全為0(n0-k0)(n0-k0)階階全全0矩陣矩陣30（3，2，2）卷積碼編碼器）卷積碼編碼器m(n0-k0)級串行編碼器級串行編碼器mk0級并行編碼器級并行編碼器mk0級串行編碼器級串行編碼器314 卷積碼的樹圖描述和狀態(tài)圖表示卷積碼的樹圖描述和狀態(tài)圖表示一、卷積碼的樹圖描述一、卷積碼的樹圖描述例例：（：（2，1，2）碼的生成多項式矩陣和生成）碼的生成多項式矩陣和生成矩陣分別為：矩陣分別為：32若輸入編碼器的信息序列：若輸入編碼器的信息序列：M（m0，m1，.）（）（1 1 0 1 1.）則編碼器輸出的碼序列為：則編碼器輸出的碼序列為：編碼

18、過程可用半無限碼樹圖說明：設(shè)編碼器初編碼過程可用半無限碼樹圖說明：設(shè)編碼器初始狀態(tài)為始狀態(tài)為0，輸入信息序列為，輸入信息序列為M，輸出的碼，輸出的碼序列相應(yīng)于碼樹中的一條序列相應(yīng)于碼樹中的一條正確路徑正確路徑，而其它，而其它所有路徑都是它的不正確路徑。所有路徑都是它的不正確路徑。33（2，1，2）碼碼樹圖：）碼碼樹圖：將碼樹分成將碼樹分成上下相等的上下相等的兩部分，就是兩部分，就是把碼序列劃分把碼序列劃分成大小相等的成大小相等的兩個子集兩個子集s0和和s134 對一般的二進(jìn)制（對一般的二進(jìn)制（n0,k0,m）編碼器，每次）編碼器，每次輸入的是輸入的是k0個信息元，有個信息元，有2ko個可能的信

19、息個可能的信息組，這相應(yīng)于從碼樹每一節(jié)點上分出的分組，這相應(yīng)于從碼樹每一節(jié)點上分出的分支數(shù)有支數(shù)有2ko條，相應(yīng)于條，相應(yīng)于2ko種不同信息組的輸種不同信息組的輸入，且每條都有入，且每條都有n0個碼元，作為與此相應(yīng)個碼元，作為與此相應(yīng)的輸出子碼。的輸出子碼。 因此，碼數(shù)上所有可能的路徑，就是該卷因此，碼數(shù)上所有可能的路徑，就是該卷積碼編碼器所有可能輸出的碼序列。積碼編碼器所有可能輸出的碼序列。35碼樹中子集的劃分碼樹中子集的劃分36二、卷積碼的狀態(tài)圖二、卷積碼的狀態(tài)圖編碼器寄存器中任一時刻的存數(shù)稱為編碼器編碼器寄存器中任一時刻的存數(shù)稱為編碼器的一個狀態(tài)，以的一個狀態(tài)，以si表示，每個表示，每個

20、狀態(tài)都對應(yīng)一個不同的輸入組。狀態(tài)都對應(yīng)一個不同的輸入組。如圖為（如圖為（2，1，2）卷積碼）卷積碼編碼器狀態(tài)圖。編碼器由兩編碼器狀態(tài)圖。編碼器由兩級移存器組成，其存數(shù)只有級移存器組成，其存數(shù)只有4種可能，即種可能，即4個狀態(tài)。個狀態(tài)。實線表實線表示示0輸入、輸入、虛線表示虛線表示1輸入時輸入時的狀態(tài)轉(zhuǎn)的狀態(tài)轉(zhuǎn)移移37例：信息組例：信息組M（1100），），M(D)1D， 則，輸出的碼序列：則，輸出的碼序列： C(D)M(D)G(D)(1+D)1+D+D2,1+D2 (11)+(10)D+(01)D2+(11)D3 相應(yīng)地相應(yīng)地C（11，01，01，11）狀態(tài)圖中編碼器的狀態(tài)變化為：狀態(tài)圖中編碼

21、器的狀態(tài)變化為： s0 s1 s3 s2 s0 從從s0開始再回到開始再回到s0，所得碼序列稱為結(jié)尾碼字。這，所得碼序列稱為結(jié)尾碼字。這要求輸完信息序列后，還應(yīng)再輸入要求輸完信息序列后，還應(yīng)再輸入mk0個全個全0信息信息元，使編碼器回到全元，使編碼器回到全0狀態(tài)。狀態(tài)。1101011138三、卷積碼得距離度量三、卷積碼得距離度量衡量卷積碼的糾錯性能可用其距離特性描述，但其衡量卷積碼的糾錯性能可用其距離特性描述，但其糾錯能力與它采用的譯碼方法有關(guān)，不同的譯碼方糾錯能力與它采用的譯碼方法有關(guān)，不同的譯碼方法有不同的距離度量。法有不同的距離度量。定義（最小漢明距離）：定義（最小漢明距離）：不同初始截

22、短碼字子集之不同初始截短碼字子集之間距離的最小值，為（間距離的最小值，為（n,k,m）卷積碼的最小漢明）卷積碼的最小漢明距離。距離。39 定理：任何相鄰定理：任何相鄰m+1段以內(nèi)的錯誤個數(shù)，不段以內(nèi)的錯誤個數(shù)，不多于多于 個，則最小距離為個，則最小距離為dmin的的（n0,k0,m）卷積碼，總可以糾正。當(dāng)然，）卷積碼，總可以糾正。當(dāng)然，若此卷積碼用來檢錯，則一定可以檢測出若此卷積碼用來檢錯，則一定可以檢測出m+1段相鄰碼段內(nèi)段相鄰碼段內(nèi)dmin1個錯誤。個錯誤。 定義：卷積碼的第定義：卷積碼的第j階階列距離列距離dj，是，是j+1段長段長截短碼樹上定義的最小漢明距離：截短碼樹上定義的最小漢明距

23、離：405 卷積碼的譯碼卷積碼的譯碼 代數(shù)譯碼：代數(shù)譯碼：譯碼方法具有一定的代數(shù)結(jié)構(gòu)，譯譯碼方法具有一定的代數(shù)結(jié)構(gòu)，譯碼簡單，便于實施。碼簡單，便于實施。 概率譯碼：概率譯碼：糾錯能力強，但算法復(fù)雜。較著名糾錯能力強，但算法復(fù)雜。較著名的有序列譯碼和維特比譯碼。的有序列譯碼和維特比譯碼。概率譯碼方法不僅基于碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上，概率譯碼方法不僅基于碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上，而且還利用了信道的統(tǒng)計特性，因而能充分而且還利用了信道的統(tǒng)計特性，因而能充分發(fā)揮卷積碼的特點，使譯碼錯誤概率達(dá)到很發(fā)揮卷積碼的特點，使譯碼錯誤概率達(dá)到很小。小。41一、維特比（一、維特比（Viterbi，VB）譯碼算法）譯碼算法 V

24、B譯碼算法是一種最大似然譯碼算法。譯碼算法是一種最大似然譯碼算法。 用柵格圖或籬笆圖可表示編碼器狀態(tài)轉(zhuǎn)移用柵格圖或籬笆圖可表示編碼器狀態(tài)轉(zhuǎn)移與時間的關(guān)系：與時間的關(guān)系：10，10，00，01，11，01，11）42 例：輸入編碼器的信息序列：例：輸入編碼器的信息序列： M（1011100） 則編碼器輸出的碼序列：則編碼器輸出的碼序列： C（11 10 00 01 10 01 11） 它相應(yīng)于籬笆圖中紅線表示的一條路徑。它相應(yīng)于籬笆圖中紅線表示的一條路徑。編碼器送出碼序列編碼器送出碼序列C，經(jīng)信道傳輸后，送入，經(jīng)信道傳輸后，送入譯譯碼器的序列碼器的序列RCE，譯碼器根據(jù)，譯碼器根據(jù)R，按最，按最

25、大似然譯碼準(zhǔn)則力圖找出編碼器在籬笆圖上大似然譯碼準(zhǔn)則力圖找出編碼器在籬笆圖上所走過的路徑。所走過的路徑。43 卷積碼的譯碼過程就是譯碼器計算、尋找卷積碼的譯碼過程就是譯碼器計算、尋找最大似然函數(shù)的過程。通過計算似然函數(shù)，最大似然函數(shù)的過程。通過計算似然函數(shù)，相當(dāng)于每一步都是尋找與相當(dāng)于每一步都是尋找與R有最小漢明距有最小漢明距離的路徑，直接譯出碼字。離的路徑，直接譯出碼字。 設(shè)（設(shè)（n0，k0，m）碼編碼器輸入：）碼編碼器輸入：m（m0，m1，.，mL1，0，00）其中其中mi（mi(1)，mi(2)，.，mi(k0)） i0，1，2，L1k0L位信息位信息k0m位全位全044 編碼器輸出的碼

26、序列：編碼器輸出的碼序列： C（C0，C1，CmL1） 其中其中Ci（Ci(1)，Ci(2)，Ci(no)） i0，1，2，Lm1 是長為是長為n0(Lm)的二元序列。的二元序列。顯然，信息序列共有顯然，信息序列共有2koL個，對應(yīng)的碼序列也個，對應(yīng)的碼序列也有有2koL個，則（個，則（n0，k0，m）碼的籬笆圖上）碼的籬笆圖上共有共有2koL條路徑。條路徑。45 在離散無記憶信道（在離散無記憶信道（DMC）中，發(fā)送）中，發(fā)送C變變成成R的概率：的概率：P(R/C) 取取C的對數(shù)似然函數(shù)的對數(shù)似然函數(shù)logbP(R/C)，稱為，稱為R與與C的的度量度量，用，用M(R/C)表示。表示。譯碼器按最

27、大似然譯碼準(zhǔn)則力圖尋找最大似譯碼器按最大似然譯碼準(zhǔn)則力圖尋找最大似然函數(shù)：然函數(shù)：或?qū)ふ矣凶畲蠡驅(qū)ふ矣凶畲蠖攘慷攘康穆窂剑旱穆窂剑?6 已經(jīng)證明：對已經(jīng)證明：對BSC信道，最大度量的路徑等信道，最大度量的路徑等價于價于R有最小漢明距離的路徑。即：有最小漢明距離的路徑。即： 根據(jù)最大似然準(zhǔn)則，可以把根據(jù)最大似然準(zhǔn)則，可以把R與籬笆圖上的與籬笆圖上的2koL條路徑的漢明距離逐個進(jìn)行比較，條路徑的漢明距離逐個進(jìn)行比較，R與與哪條路徑距離最小，就把哪條路徑距離最小，就把R譯成那個碼序列。譯成那個碼序列。 即當(dāng)即當(dāng)d(R,Ci)d(R,Cj)時，將把時，將把R譯成譯成Ci。 但但L較大時，以上譯碼方法難

28、以實現(xiàn)。較大時，以上譯碼方法難以實現(xiàn)。47維特比譯碼算法的步驟：維特比譯碼算法的步驟：(1)(1)從某一時間單位從某一時間單位j jm m開始，對進(jìn)入每一狀態(tài)的所開始，對進(jìn)入每一狀態(tài)的所有長為有長為j j段分支的部分路徑，計算段分支的部分路徑，計算部分路徑度量部分路徑度量。對每一狀態(tài)，挑選并存貯一條有最大度量的部分路對每一狀態(tài)，挑選并存貯一條有最大度量的部分路徑及其部分度量值，稱此部分路徑為徑及其部分度量值，稱此部分路徑為留選留選( (幸存幸存) )路路徑。徑。(2)j(2)j增加增加l l，把此時刻進(jìn)入每一狀態(tài)的所有分支度量，把此時刻進(jìn)入每一狀態(tài)的所有分支度量，和同這些分支相連的前一時刻的留

29、選路徑的度量相和同這些分支相連的前一時刻的留選路徑的度量相加，得到了此時刻進(jìn)入每一狀態(tài)的留選路徑，加以加，得到了此時刻進(jìn)入每一狀態(tài)的留選路徑，加以存貯并刪去其它所有路徑，因此留選路徑延長了一存貯并刪去其它所有路徑，因此留選路徑延長了一個分支。個分支。 48(3)(3)若若jL+mjL+m，則重復(fù)以上各步，否則停止，則重復(fù)以上各步，否則停止，譯碼器得到了有最大路徑度量的路徑。譯碼器得到了有最大路徑度量的路徑。由此可知，在籬笆圖上用由此可知，在籬笆圖上用VB譯碼算法得到的譯碼算法得到的路徑一定是一條最大似然路徑，因而這種譯路徑一定是一條最大似然路徑，因而這種譯碼方法是最佳的。碼方法是最佳的。定理：

30、定理： 49例：例：編碼器如圖，編碼器如圖，輸入信息序列：輸入信息序列：M（1011100）輸出碼序列：輸出碼序列：C（11，10，00，01，10，01，11）通過通過BSC送入譯碼器的序列：送入譯碼器的序列：R （10，10，00，01，11，01，11）求利用求利用VB譯碼算法時，譯碼器輸出的估值信息序列譯碼算法時，譯碼器輸出的估值信息序列50解：解：VB譯碼器譯譯碼器譯R的過程：的過程：51由于由于d大，大，紅色路徑被刪除紅色路徑被刪除雖然雖然d相同，均為相同，均為3但綠色路徑被舍去但綠色路徑被舍去11527.第第7時刻接收子碼時刻接收子碼 R611能用以上有限狀態(tài)組成的籬笆圖描述其編

31、、譯碼過程的能用以上有限狀態(tài)組成的籬笆圖描述其編、譯碼過程的碼稱為網(wǎng)格碼或籬笆碼，也稱碼稱為網(wǎng)格碼或籬笆碼，也稱Trellis碼，是碼樹的一個碼，是碼樹的一個大類。大類。最后幸存最后幸存一條最大一條最大似然路徑似然路徑譯碼輸出：譯碼輸出：11,10,00,01,10,01,1110，10，00，01，11，01，11）53VB譯碼算法的特點：譯碼算法的特點：1）（）（n,k,m）卷積碼編碼器共有）卷積碼編碼器共有2km個狀態(tài)，個狀態(tài)，則譯碼器必有則譯碼器必有2km個存儲器，存儲個存儲器，存儲2km個幸存?zhèn)€幸存路徑（或信息序列）以及每一單個路徑與路徑（或信息序列）以及每一單個路徑與Rj的距離。譯

32、碼器的復(fù)雜性隨的距離。譯碼器的復(fù)雜性隨km指數(shù)增加，指數(shù)增加，一般選擇一般選擇m10。2）信息序列存儲器存儲的信息長度為）信息序列存儲器存儲的信息長度為kL，L很大時，譯碼器的存儲量也隨之增大，難以很大時，譯碼器的存儲量也隨之增大，難以實用。實用。54二、軟判決二、軟判決VB譯碼譯碼 把信道輸出的信號進(jìn)行把信道輸出的信號進(jìn)行Q（Q2m）電平量化，然）電平量化，然后再輸入后再輸入VB譯碼器，能適應(yīng)這種譯碼器，能適應(yīng)這種Q進(jìn)制輸入的進(jìn)制輸入的VB譯碼器稱為軟判決譯碼器稱為軟判決VB譯碼器。譯碼器。 軟判決軟判決VB譯碼器的結(jié)構(gòu)和譯碼過程，完全與硬判譯碼器的結(jié)構(gòu)和譯碼過程，完全與硬判決相同，只須在決相同，只須在 R與與C中用中用Q進(jìn)制的值代替二進(jìn)制進(jìn)制的值代替二進(jìn)制值即可。值即可。 軟判決輸出有更高的度量值，性能更好。一般采軟判決輸出有更高的度量值，性能更好。一般采用八電平均勻量化，可達(dá)最大似然譯碼性能。用八電平均勻量化，可達(dá)最大似然譯碼性能。556 調(diào)制與卷積碼的結(jié)合（調(diào)制與卷積碼的結(jié)合（T