信息論與編碼理論ch6信道編碼卷積碼2的課件

1、 我們必須有恒心，尤其要有自信力！我們必須相信我們的天賦是要用來(lái)作某種事情的，無(wú)論代價(jià)多么大，這種事情必須作到。 居里夫人 2022/8/1616.4.1 卷積碼的基本概念6.4.2 卷積碼的編碼6.4.3 卷積碼的矩陣描述6.4.4 卷積碼的譯碼6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述6.4.6 維特比譯碼的基本原理6.4.7 軟判決維特比譯碼6.4.8 維特比譯碼的性能6.4.9 維特比譯碼的應(yīng)用6.4 卷積碼2022/8/162(1) 卷積碼譯碼的種類：卷積碼的譯碼可分為代數(shù)譯碼和概率譯碼。(2) 代數(shù)譯碼：從碼的代數(shù)結(jié)構(gòu)出發(fā)，以一個(gè)約束度的接收序列為單位，對(duì)該接收序列的信息碼組進(jìn)行譯碼

2、。大數(shù)邏輯譯碼是代數(shù)譯碼的主要方法。 代數(shù)譯碼中，用矩陣描述比較方便。(3) 概率譯碼：從信道的統(tǒng)計(jì)特性出發(fā)，以遠(yuǎn)大于約束度的接收序列為單位，對(duì)信息碼組進(jìn)行最大似然的判決。維特比譯碼和序列譯碼是其最主要的方法。 在維特比譯碼中，用籬笆圖來(lái)描述碼的譯碼更為方便。 6.4.4 卷積碼的譯碼2022/8/163代數(shù)譯碼和概率譯碼：代數(shù)譯碼沿用分組碼代數(shù)譯碼的思路，先由接收序列R(D)=C(D)+E(D)求伴隨式S(D)，再由S(D)估算差錯(cuò)圖案(D)，并令譯碼估值(D)=R(D)-(D), 最后將(D)乘以轉(zhuǎn)移函數(shù)逆矩陣G-1(D) 得信息序列M(D)。受逆矩陣G-1(D)和差錯(cuò)圖案(D)計(jì)算上的限

3、制，代數(shù)譯碼一般僅用于簡(jiǎn)單的卷積碼。其優(yōu)點(diǎn)是譯碼電路簡(jiǎn)單，時(shí)延小，適合于高速譯碼。其不足之處在于：適合代數(shù)譯碼的卷積碼的編碼增益一般都不大，且僅適合于硬判決譯碼。現(xiàn)代通信使用代數(shù)譯碼的場(chǎng)合較少。6.4.4 卷積碼的譯碼2022/8/164卷積碼本質(zhì)上是一個(gè)有限狀態(tài)機(jī)，它的碼字前后相關(guān)。對(duì)于編碼器編出的任何碼字序列，在網(wǎng)格圖上一定可以找到一條連續(xù)的路徑與之對(duì)應(yīng)，這種連續(xù)性正是卷積碼碼字前后相關(guān)的體現(xiàn)。但在譯碼端，一旦傳輸、存儲(chǔ)過(guò)程中出現(xiàn)差錯(cuò)，輸入到譯碼器的接收碼字流在網(wǎng)格圖上就找不出一條對(duì)應(yīng)的連續(xù)路徑，而只有若干不確定、斷續(xù)的路徑供作譯碼參考。而從譯碼器譯出的碼字序列必須與編碼器一樣，也是對(duì)應(yīng)一

4、條連續(xù)路徑，否則肯定是譯碼出了差錯(cuò)。在編碼理論發(fā)展進(jìn)程中出現(xiàn)了多種以序列為基礎(chǔ)的譯碼方法，如序列譯碼算法、修改后的Fano算法以及堆棧算法等，但這些都不是最佳譯碼或最大似然譯碼。 6.4.4 卷積碼的譯碼2022/8/165卷積碼概率譯碼的基本思路是：以斷續(xù)的接收碼流為基礎(chǔ)，逐個(gè)計(jì)算它與其它所有可能出現(xiàn)的、連續(xù)的網(wǎng)格圖路徑的距離，選出其中可能性（概率）最大的一條作為譯碼估值輸出。概率最大在大多數(shù)場(chǎng)合可解釋為距離最小，這種最小距離譯碼體現(xiàn)的正是最大似然的準(zhǔn)則。在二進(jìn)制硬判決譯碼情況下，最大似然就是最小漢明距離；而在二維調(diào)制（PSK、QAM）和軟判決情況下， 最小距離一般是指最小歐氏（Euclid

5、ean）距離。6.4.4 卷積碼的譯碼2022/8/166當(dāng)前最實(shí)用的卷積碼譯碼算法是維特比(VB) 算法(Viterbi,1967)。小村(Omura，1969)兩年后指出：維特比算法等價(jià)于在一個(gè)加權(quán)圖上求取最短路徑。1973年福尼(Forney)最終證明了維特比算法實(shí)質(zhì)上就是卷積碼的最大似然譯碼。后來(lái)Forney又指出，維特比算法不但可用于卷積碼譯碼，也可用于帶寬有限、存在嚴(yán)重碼間干擾的信道的信號(hào)接收，因?yàn)榇a間干擾可看成是由于信道記憶造成的，這種記憶類似于卷積編碼器中的寄存器，因而采用維特比算法可以實(shí)現(xiàn)信號(hào)的最大似然接收。由于最優(yōu)的特性和相對(duì)適中的復(fù)雜度，維特比算法在L10的卷積碼譯碼中已

6、成為首選、最普遍采用的算法。6.4.4 卷積碼的譯碼2022/8/167(1) 卷積碼的狀態(tài)定義：卷積碼編碼器要存儲(chǔ) m 段消息，這些消息數(shù)據(jù)既要因新的輸入而改變，又要影響當(dāng)前的編碼輸出，因此稱存儲(chǔ)表達(dá)這些數(shù)據(jù)的參量為卷積編碼器的內(nèi)部狀態(tài)，簡(jiǎn)稱狀態(tài)。有效存儲(chǔ)單元 M：Mk m狀態(tài)向量(l)/：(l)=(M(l), M1(l), 2(l),1(l)二元 (n,k,m) 卷積碼共有 2M 個(gè)不同的狀態(tài)，記為新的狀態(tài)(l+1)/轉(zhuǎn)移分支 (l),(l+1)/(, )輸入段 U(l)/U輸出段 V(l)/V狀態(tài)轉(zhuǎn)移方程：=(,U)輸出方程： V =(,U)6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述202

7、2/8/168例6.4.10 (2,1,2)碼的狀態(tài)向量為=(21)，共有4種狀態(tài)S0,S1,S2,S3，如圖6.4.13所示。g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111g(1,2)=g0(1,2) g1(1,2) g2(1,2) =1016.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/169其狀態(tài)變化表如表6.4.1所示。 該碼的狀態(tài)轉(zhuǎn)移方程和輸出方程分別為 1=U 2=1 V1=U +1+2 V2=U +2 6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1610其狀態(tài)轉(zhuǎn)移圖如圖6.4.14和圖5.4.15所示。6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描

8、述2022/8/16116.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1612(2) 卷積碼的狀態(tài)轉(zhuǎn)移圖閉合型的狀轉(zhuǎn)移態(tài)圖：直接地描述了卷積編碼器在任一時(shí)刻的工作狀況；開(kāi)放型的狀態(tài)轉(zhuǎn)移圖：更適合去描述一個(gè)特定輸入序列的編碼過(guò)程。6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1613例6.4.11 (3,2,1)碼的狀態(tài)向量為=(21)，共有4種狀態(tài)S0,S1,S2,S3，如圖6.4.13所示。g(1,1)=g0(1,1) g1(1,1)=11g(1,2)=g0(1,2) g1(1,2)=01g(1,3)=g0(1,3) g1(1,3)=11g(2,1)=g0(2,1) g1(2

9、,1)=01g(2,2)=g0(2,2) g1(2,2)=10g(2,3)=g0(2,3) g1(2,3)=10其狀態(tài)為 S=(21) S0=(00),S1 =(01),S2 =(10),S3 =(11) V=(V1V2V3) U=(U1U2)6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1614狀態(tài)轉(zhuǎn)移方程和輸出方程為 1=U1 2= U2 V1=U1+1+2 V2=U2+1 V2=U1+U2+16.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/16156.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1616(3) 卷積碼的柵格圖(籬笆圖)狀態(tài)圖不能反映出狀態(tài)轉(zhuǎn)移與時(shí)間的關(guān)

10、系柵格圖/籬笆圖：將開(kāi)放型的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序級(jí)聯(lián)形成一個(gè)柵格圖。編碼路徑：狀態(tài)序列在柵格圖中形成的一條有向路徑。當(dāng)有向路徑始于全“0”狀態(tài)S0，又終于S0時(shí)，表明此時(shí)編碼器又回到全“0”狀態(tài)，這條始于S0又首次終于S0的路徑是一個(gè)卷積碼碼字。6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1617紅實(shí)線表示U=0時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支；黃虛線表示U=1時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支。6.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/16186.4.5 卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述2022/8/1619(1) 維特比譯碼的度量(2) 維特比譯碼和籬笆圖(3) 碼參數(shù)和籬笆圖的關(guān)系(4) 最大似

11、然譯碼/最小距離譯碼(5) 舉例說(shuō)明維特比譯碼工作原理(6) 總結(jié)維特比算法的步驟6.4.6 維特比譯碼的基本原理2022/8/1620(1) 維特比譯碼的度量待編碼的信息序列M：M=M0, M1, ML1；編碼器輸入序列的總長(zhǎng)度：k(L+m)；后mk個(gè)碼元全為0編碼器輸出的碼序列C：C=C0, C1,CL1，其中每個(gè)子碼Ci含有n個(gè)碼元；經(jīng)離散無(wú)記憶信道(DMC)傳輸后，譯碼器接收的序列 R：R=R0, R1,RL1；對(duì)于DMC信道：碼序列 C 的路徑度量 M(R/C)：計(jì)算第 l 時(shí)刻到達(dá)狀態(tài) i 的最大似然路徑的相似度log p(R/C)；子碼 Ci 度量M(Ri/Ci) ：計(jì)算第 l

12、時(shí)刻接收子碼 Ri 相對(duì)于各碼字的相似度 log p(Ri/Ci)，也稱為分支度量。6.4.6 維特比譯碼的基本原理2022/8/1621(2) 維特比譯碼和籬笆圖在維特比譯碼中，用狀態(tài)圖和籬笆圖描述碼的譯碼比較方便。以(2,1,2)碼為例說(shuō)明 g(1,1)=g0(1,1) g1(1,1) g2(1,1) =111 g(1,2)=g0(1,2) g1(1,2) g2(1,2) =101圖6.4.20所示的是(2.1.2)碼的籬笆圖：它由結(jié)點(diǎn)和分支構(gòu)成。共有8個(gè)結(jié)點(diǎn)（單元時(shí)刻），在圖中的上方以0,1,2,7標(biāo)號(hào)，0結(jié)點(diǎn)表示第0個(gè)時(shí)刻。編碼器的工作過(guò)程：6.4.6 維特比譯碼的基本原理2022/8

13、/16226.4.6 維特比譯碼的基本原理2022/8/1623在起始的第0個(gè)到第2個(gè)時(shí)刻內(nèi)，編碼器根據(jù)輸入的信息元不同從S0狀態(tài)向四個(gè)可能的狀態(tài)之一行進(jìn)；本例假定信息序列長(zhǎng)為L(zhǎng)=5個(gè)信息組，最后 m 個(gè)信息組是全0，所以在籬笆圖上的最后兩個(gè)時(shí)刻向 S0 狀態(tài)返回；籬笆圖上各連續(xù)分支組成了可能的路徑，它們代表了各種可能的碼序列；由于可能的輸入信息序列有 2kL=25=32 個(gè)，可能的路徑有32條；每個(gè)分支上的數(shù)字表示輸出的子碼。6.4.6 維特比譯碼的基本原理2022/8/1624(3) 碼參數(shù)和籬笆圖的關(guān)系 對(duì)(n,k,m)碼而言，編碼器的可能狀態(tài)數(shù)目為2km個(gè)，進(jìn)入每個(gè)狀態(tài)的分支數(shù)為 2k

14、 個(gè)，從每個(gè)狀態(tài)輸出的分支數(shù) 2k 個(gè)，若輸入信息序列長(zhǎng)為 k(L+m)（后mk個(gè)碼元全為0），則籬笆圖上共有 2kL 條不同的路徑，相應(yīng)于編碼器輸出的 2kL 個(gè)碼序列。6.4.6 維特比譯碼的基本原理2022/8/1625(4) 最大似然譯碼/最小距離譯碼譯碼器接收到 R 序列后，按最大似然法則力圖尋找編碼器在籬笆圖上原來(lái)走過(guò)的路徑，也就是尋找具有最大度量的路徑；因此，譯碼器必須計(jì)算 maxM(R/Cj)，j=1,2,2Lk，對(duì)BSC信道，就是尋找與 R 有最小距離的路徑，即計(jì)算和尋找 mind(R, Cj)。譯碼的實(shí)現(xiàn)：6.4.6 維特比譯碼的基本原理2022/8/1626最大似然譯碼方

15、法只是提供了一個(gè)譯碼準(zhǔn)則，實(shí)現(xiàn)起來(lái)尚有一定困難。因?yàn)樗强紤]了長(zhǎng)度為 (L+m)n 的接收序列來(lái)譯碼的，這樣的序列可能有 2Lk 條；若實(shí)際接收序列中，L=50，k=2，則可能的路徑有 2100 條。譯碼器每接收一個(gè)序列 R，就要計(jì)算 1030 個(gè)似然函數(shù)才能做出譯碼判決。若 kL 再大一些，譯碼器按最大似然譯碼準(zhǔn)則譯碼將是很困難的。6.4.6 維特比譯碼的基本原理2022/8/1627(5) 舉例說(shuō)明維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計(jì)算和比較 2Lk 條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想

16、：將接收序列 R 與籬笆圖上的路徑逐分支地比較，比較的長(zhǎng)度一般取 (56)mn，然后留下與 R 距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長(zhǎng)并存儲(chǔ)起來(lái)。幸存路徑的數(shù)目等于狀態(tài)數(shù)：2km 以 (2,1,2) 非系統(tǒng)碼為例說(shuō)明維特比譯碼的基本思想：設(shè)發(fā)送序列 C 為全0；接收序列 R=10,00,01,00,00,00,00,6.4.6 維特比譯碼的基本原理2022/8/1628假設(shè)譯碼器的初始狀態(tài)為全0；第0個(gè)時(shí)刻：接收序列的第0個(gè)分支 R0=10 進(jìn)入譯碼器。從 S0 狀態(tài)有兩個(gè)分支，它們是 00 和 11，R0與這兩個(gè)分支比較，比較的結(jié)果和到達(dá)的狀態(tài)如表

17、6.4.2 所示：每個(gè)狀態(tài)/節(jié)點(diǎn)都有兩個(gè)存儲(chǔ)器：路徑存儲(chǔ)器：存儲(chǔ)該狀態(tài)的部分路徑；路徑值存儲(chǔ)器：存儲(chǔ)達(dá)到該狀態(tài)的部分路徑值 (累加距離)。6.4.6 維特比譯碼的基本原理2022/8/1629第一個(gè)時(shí)刻：進(jìn)入譯碼器的接收碼組 R1=00 和此時(shí)刻出發(fā)的四條分支比較，比較結(jié)果和達(dá)到狀態(tài)如表6.4.3所示：從第一個(gè)時(shí)刻到第二個(gè)時(shí)刻：共有四條路徑，到達(dá)S0, S1, S2和S3。在第二個(gè)時(shí)刻以前譯碼器不做任何選擇和判決。每個(gè)狀態(tài)的路徑存儲(chǔ)器存儲(chǔ)下此時(shí)刻的幸存路徑：0000,0011,1110,1101；每個(gè)狀態(tài)的路徑值存儲(chǔ)器存儲(chǔ)了此時(shí)刻到達(dá)該狀態(tài)的幸存路徑累加值 (累加距離)。6.4.6 維特比譯碼

18、的基本原理2022/8/1630從第二個(gè)時(shí)刻起：第二個(gè)接收碼組 R2=01 進(jìn)入譯碼器，從籬笆圖上可見(jiàn)，從第二個(gè)時(shí)刻到第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的分支有兩個(gè)（或者說(shuō)在第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的路徑有兩條）。譯碼器將接收碼組 R2 與進(jìn)入每個(gè)狀態(tài)的兩個(gè)分支進(jìn)行比較和判決，選擇一個(gè)累加距離（部分路徑值）最小的路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條，比較和判決的過(guò)程如下：6.4.6 維特比譯碼的基本原理2022/8/1631經(jīng)過(guò)比較后選擇：部分路徑 000000為到達(dá) S0 狀態(tài)的幸存路徑；部分路徑 000011為到達(dá) S1 狀態(tài)的幸存路徑；部分路徑 110101為到達(dá) S2 狀態(tài)的幸存路

19、徑；部分路徑 001101為到達(dá) S3 狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個(gè)時(shí)刻進(jìn)入一個(gè)碼組，沿著籬笆圖對(duì)每個(gè)狀態(tài)按部分路徑值（累加距離）的大小，選擇一條幸存路徑。在每個(gè)狀態(tài)上進(jìn)行判決時(shí)，可能出現(xiàn)進(jìn)入這一狀態(tài)的兩條路徑的距離值相同，這時(shí)可以任選其一，因?yàn)閷?duì)以后的判決而言，無(wú)論選擇那一條路徑，累加距離是相同的。6.4.6 維特比譯碼的基本原理2022/8/1632對(duì)本例而言，按上述算法進(jìn)行到第十一個(gè)分支后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達(dá)到較低的錯(cuò)誤概率。一般，約為 (56)mn，所以，維特比譯碼的延時(shí)可達(dá) (56)m 個(gè)單位時(shí)刻（每個(gè)

20、單位時(shí)刻為 n 個(gè)碼元長(zhǎng)度）就可以對(duì)第0個(gè)接收碼組的信息元進(jìn)行判決。依此類推，對(duì)接收序列中的諸碼組進(jìn)行譯碼。維特比譯碼的一次運(yùn)算：計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑。籬笆圖中共有 2km 個(gè)狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存儲(chǔ) m 成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷積碼，其 m 不能選的太大。6.4.6 維特比譯碼的基本原理2022/8/16336.4.6 維特比譯碼的基本原理每個(gè)狀態(tài)以實(shí)線表示一條可能的分支，虛線表示另一條可能的分支，括號(hào)外為實(shí)線分支連接的路徑的累積路徑值，括號(hào)內(nèi)為虛線分支連接的路徑的累積路徑值。2022/

21、8/16346.4.6 維特比譯碼的基本原理2022/8/16356.4.6 維特比譯碼的基本原理2022/8/16366.4.6 維特比譯碼的基本原理2022/8/16376.4.6 維特比譯碼的基本原理2022/8/1638(6) 總結(jié)維特比算法的步驟在第 j(j=m)個(gè)時(shí)刻以前，譯碼器計(jì)算所有的長(zhǎng)為 m 個(gè)分支的部分路徑值，對(duì)進(jìn)入 2km 個(gè)狀態(tài)的每一條部分路徑都保留。第 m 個(gè)時(shí)刻開(kāi)始，對(duì)進(jìn)入每一個(gè)狀態(tài)的部分路徑進(jìn)行計(jì)算，這樣的路徑有 2k 條，挑選具有最小部分路徑值的部分路徑為幸存路徑，刪去進(jìn)入該狀態(tài)的其它路徑，然后，幸存路徑向前延長(zhǎng)一個(gè)分支。重復(fù)第二步的計(jì)算、比較和判決過(guò)程。若輸入

22、接收序列長(zhǎng)為 (L+m)k，其中，后 m 段是人為加入的全0段，則譯碼一直進(jìn)行到 (L+m) 個(gè)時(shí)刻為止。若進(jìn)入某個(gè)狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可任選其一作為幸存路徑。6.4.6 維特比譯碼的基本原理2022/8/1639硬判決譯碼器：以最小距離為度量的譯碼器。它適用于 BSC 信道。軟判決譯碼器：把信道解調(diào)器輸出的信號(hào)進(jìn)行 Q 電平量化，其中 Q 2，然后再輸入到維特比譯碼器進(jìn)行譯碼。充分利用了信道輸出信號(hào)的有關(guān)信息，提高譯碼的可靠性。它適用于DMC信道。軟判決譯碼器比硬判決譯碼器可以改進(jìn)碼的性能。在一定信道條件下，用軟判決譯碼器可以獲得更小的誤碼率；或者在同等誤碼率條件下，獲得較高的編碼增益。注：離散無(wú)記憶信道DMC（Disperse Memory channel） 二進(jìn)制對(duì)稱信道BSC（Binary Symmetry Channel），BSC是 DMC的一種特殊情況。6.4.7 軟