【正文】 1b11a0000aab110010cbd0111c00acb111010cdd0101db11a圖 411 （ 2，1， 3）卷積碼的樹狀表示 第 4章 信道編碼技術(shù) 當(dāng)?shù)谝粋€(gè)輸入位 m1＝ 0時(shí) ,輸出位 x1, 1 x2, 1＝ 00； 當(dāng) m1＝ 1時(shí) ,輸出位 x1, 1 x2, 1＝ 11； 因此從 a點(diǎn)出發(fā)有兩條分支 (樹叉 )可以選擇 ,也就是 m1＝ 0時(shí)取上面一條分支 ,m1＝ 1時(shí)取下面一條分支 。 當(dāng)輸入第二位時(shí) ,移位寄存器右移一位后 ,在上分支情況下 ,移位寄存器的狀態(tài)仍為 00,下分支的狀態(tài)則為 01,把 01狀態(tài)記作b。 當(dāng)新的一位輸入時(shí) ,隨著移位寄存器狀態(tài)和輸入位的不同 ,樹狀圖繼續(xù)分叉成 4條分支 ,兩條向上 ,兩條向下 。 上分支對(duì)應(yīng)于輸入 0狀態(tài) ,下分支對(duì)應(yīng)于輸入 1狀態(tài) 。 如此繼續(xù)下去 ,即可得到圖 411所示的二叉樹圖形 。 樹狀圖中 ,每條樹叉上所標(biāo)注的碼元為輸出狀態(tài) ,每個(gè)節(jié)點(diǎn)上標(biāo)注的 a、 b、 c、 d表示移位寄存器的狀態(tài) ,也就是以前輸入的信息 ,a狀態(tài)表示 mj2mj1＝ 00,b狀態(tài)表示 mj2mj1＝ 01,c狀態(tài)表示 mj2mj1＝ 10,d狀態(tài)表示 mj2mj1＝11。 顯然 ,對(duì)于第 j個(gè)輸入位 ,就有 2j條分支 ,但是在 j=N≥ 3時(shí) ,樹狀圖的節(jié)點(diǎn)自上而下開始重復(fù)出現(xiàn)這 4種狀態(tài) 。 第 4章 信道編碼技術(shù) 2. 從卷積碼的樹狀圖中可以看到 ,樹狀圖的節(jié)點(diǎn)自上而下會(huì)出現(xiàn)重復(fù)特性 ,為此 ,我們可以得到一種更為緊湊的圖形表示方法 ,即網(wǎng)格圖法 ,具體情況見圖 412。 在網(wǎng)格圖中 ,把碼樹中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起 ,碼樹中的上分支 （ 對(duì)應(yīng)輸入 0） 用實(shí)線表示 ,下分支 （ 對(duì)應(yīng)輸入 1） 用虛線表示 。 網(wǎng)格圖中分支上標(biāo)注的碼元為對(duì)應(yīng)的輸出 ,自上而下 4行節(jié)點(diǎn)分別表示 a、 b、 c、 d四種狀態(tài) 。 一般情況下應(yīng)有 2N1種狀態(tài) ,從第 N節(jié)開始 ,網(wǎng)格圖圖形開始重復(fù)而完全相同 。 第 4章 信道編碼技術(shù) 圖 412 （ 2, 1, 3）卷積碼的網(wǎng)絡(luò)圖表示 00 00 00 00 00111111111110狀態(tài)a ＝ 00b ＝ 01c ＝ 10d ＝ 1110 10 10010101010101 010000001011 11 1110 10第 4章 信道編碼技術(shù) 3. 由圖 411可以看到 ,對(duì)于每一個(gè)節(jié)點(diǎn)當(dāng)前狀態(tài) a、 b、 c、 d,根據(jù)不同的輸入將進(jìn)入不同的狀態(tài) ,基于這一原理 ,我們可以構(gòu)造出當(dāng)前狀態(tài)與下一狀態(tài)之間的狀態(tài)轉(zhuǎn)換圖 ,也可以稱之為卷積碼的狀態(tài)圖 。 在圖 413中實(shí)線表示信息位為 0的路徑 ,虛線表示信息位為 1的路徑 ,并在路徑上寫 出相應(yīng)的輸出碼元 。 當(dāng)然 ,如果將狀態(tài)圖在時(shí)間上展開 ,便可以得到前面講到的網(wǎng)格圖 。 第 4章 信道編碼技術(shù) 圖 413 （ 2,1,3）卷積碼的狀態(tài)圖 a dcb1000 00 1011 0111 01狀態(tài)a ＝ 00b ＝ 01c ＝ 10d ＝ 11第 4章 信道編碼技術(shù) 假如利用圖 410所示的卷積碼編碼器對(duì)輸入序列110111001000進(jìn)行編碼 ,我們就可以用上述 3種方法當(dāng)中的任意一種來分析編碼器的輸出序列和狀態(tài)變化路徑 。 在這里使用卷積碼的網(wǎng)格圖表示法進(jìn)行分析 。 若起始狀態(tài)為 a,則可以得到圖 414所示的結(jié)論。 第 4章 信道編碼技術(shù) 圖 414 （ 2,1,3）卷積碼的編碼過程及路徑 a輸出 碼狀態(tài)輸入 碼111b11011d010c001b011d101d010c110a111b100c110a000a0001010001100111 111011第 4章 信道編碼技術(shù) 通過上述分析以及對(duì)具體實(shí)例的研究 ,我們可以得到 (n,k,N) （ 1） 對(duì)于每組 k位的輸入 ,利用卷積碼編碼后將得到 n位的輸出； （ 2） 樹狀圖中每個(gè)節(jié)點(diǎn)可引出 2k條分支； （ 3） 網(wǎng)格圖和狀態(tài)圖都有 2k(N1) 種可能的狀態(tài) ,每個(gè)狀態(tài)可以引出 2k條分支 ,同時(shí)也有 2k條分支從其他狀態(tài)或本狀態(tài)引入； （ 4） 在任何情況下 ,只要卷積碼編碼器一確定 ,相應(yīng)的樹狀圖 、 網(wǎng)格圖和狀態(tài)圖都將確定 ,與輸入的碼序列無關(guān) 。 第 4章 信道編碼技術(shù) 我們知道 , (Hamming 距 )與糾錯(cuò)能力有密切關(guān)系 ,生成一種分組碼時(shí)應(yīng)使碼組之間的距離盡可能大 。 常以最大的最小碼距作為糾錯(cuò)能力的度量 。 卷積碼中也同樣存在碼距的概念 ,通常使用的碼距有兩種： 最小碼距 dmin和自由碼距 dfree。 卷積碼中長(zhǎng)度為 nN(假設(shè)約束長(zhǎng)度為 7)的編碼后序列之間的最小漢明距離被稱為最小碼距 dmin,任意長(zhǎng)編碼后序列之間的最小漢明距離被稱為自由碼距 dfree。 由于卷積碼并不劃分碼組 ,因而以自由碼距作為糾錯(cuò)能力的度量更為合適 。 更加確切地說 ,采用哪一種碼距作為糾錯(cuò)能力的度量標(biāo)準(zhǔn) ,與譯碼算法有關(guān) 。 第 4章 信道編碼技術(shù) 但當(dāng)譯碼算法僅限于處理長(zhǎng)度為 nN的接收序列時(shí) ,最小碼距 dmin是一個(gè)重要的參量 ,門限譯碼就是一個(gè)例子 。 當(dāng)采用維特比譯碼或序列譯碼算法 ,且譯碼所考察的編碼后序列長(zhǎng)度大于 nN時(shí) ,自由碼距 dfree就是一個(gè)重要參量 。 這兩種譯碼算法 ,特別是維特比譯碼 ,是目前使用最為廣泛且譯碼效果最好的卷積碼譯碼算法 。 計(jì)算自由碼距的一種解析方法是利用卷積碼的生成函數(shù) 。 生成函數(shù)可以看成是卷積碼編碼器的傳遞函數(shù) ,它可以利用信號(hào)流圖方法來計(jì)算 。 第 4章 信道編碼技術(shù) 用狀態(tài)圖求生成函數(shù)可以得到卷積碼的距離特性 ,特別是自由距 。 但在給定 n,k和 N時(shí) ,無法得到自由距與卷積碼生成多項(xiàng)式之間的計(jì)算公式 ,必須逐個(gè)計(jì)算不同卷積碼的生成函數(shù) ,才能得到具有最大自由距的最好碼 。 隨著 k和 N增大 ,狀態(tài)圖中的狀態(tài)數(shù)指數(shù)增加 ,因而生成函數(shù)的計(jì)算變得愈來愈復(fù)雜 ,甚至不可能 。 因此 ,卷積碼中的好碼大都是用計(jì)算機(jī)搜索得到的 。 第 4章 信道編碼技術(shù) 卷積碼的最佳譯碼 —— 1. 利用最大似然序列估計(jì)器 ,使似然函數(shù)最大的一個(gè)參數(shù)作為估計(jì)值 ,鑒于似然函數(shù)的性質(zhì) ,我們通常選擇似然函數(shù)的對(duì)數(shù)最大 ,而不是似然函數(shù)本身最大 ,現(xiàn)在我們就根據(jù)卷積碼編譯碼系統(tǒng)的特點(diǎn)構(gòu)造似然函數(shù) 。 漢明距 e最小相當(dāng)于對(duì)數(shù)似然函數(shù)最大 。 求最大似然函數(shù)的對(duì)數(shù) ,就相當(dāng)于求 X和 Y之間的漢明距最小 。 最大似然譯碼的任務(wù)就是在樹狀圖或網(wǎng)格圖中選擇一條路徑 ,使相應(yīng)的譯碼結(jié)果和輸入碼之間歐氏距離或漢明距離最小 。 第 4章 信道編碼技術(shù) 對(duì)于長(zhǎng)度為 L的二進(jìn)制序列的最佳譯碼 ,需要對(duì)可能發(fā)送的 2L個(gè)不同的序列的 2L條路徑似然函數(shù)累加值 (即路徑量度 )進(jìn)行比較 ,選取其中最大 (即最小量度 )的一條 。 顯然 ,譯碼過程的計(jì)算量隨 L增加而呈指數(shù)增長(zhǎng) ,這在實(shí)際中難以實(shí)現(xiàn) ,因此只能采用次最佳的譯碼方法 。 用網(wǎng)格圖描述時(shí) ,由于路徑的匯聚消除了樹狀圖中的冗余度 ,譯碼過程中只需考慮整個(gè)路徑集合中那些能使似然函數(shù)最大的路徑 。 如果在某一節(jié)點(diǎn)上發(fā)現(xiàn)某條路徑已不可能獲得最大對(duì)數(shù)似然函數(shù) ,那么就放棄這條路徑 。 然后在剩下的 “ 幸存 ” 路徑中重新選擇譯碼路徑 ,這樣一直進(jìn)行到最后第 L級(jí) 。 由于這種方法較早地丟棄了那些不可能的路徑 ,從而減輕了譯碼的工作量 ,維特比譯碼正是基于這種想法 。 第 4章 信道編碼技術(shù) 2. 卷積碼的網(wǎng)格圖中共有 2k(N1) 種狀態(tài) ,每個(gè)節(jié)點(diǎn)(即每個(gè)狀態(tài) )有 2k條分支引入 , 也有 2k條分支引出 。 為簡(jiǎn)便起見 ,我們討論 k＝ 1的情形 ,從全 0狀態(tài)起始點(diǎn)開始討論 。 由網(wǎng)格圖的前 N1條連續(xù)分支構(gòu)成的路徑互不相交 ,即最初的 2 (N1) 條路徑各不相同 ,當(dāng)接收到第 N條分支時(shí) ,每條路徑都有兩條分支延伸到第 N級(jí)上 ,而第 N級(jí)上的每?jī)蓷l分支又都匯聚在一個(gè)節(jié)點(diǎn)上 。 第 4章 信道編碼技術(shù) 在維特比譯碼算法中 ,把匯聚在每個(gè)節(jié)點(diǎn)上的兩條路徑的對(duì)數(shù)似然函數(shù)累加值進(jìn)行比較 ,然后把具有較大對(duì)數(shù)似然函數(shù)累加值的路徑保存下來 ,而丟棄另一條路徑 ,經(jīng)挑選后第 N級(jí)只留下 2 (N1) 條幸存路徑 ,選出的路徑連同它們的對(duì)數(shù)似然函數(shù)累加值一起被存儲(chǔ)起來 。 由于每個(gè)節(jié)點(diǎn)引出兩條分支 ,因此以后各級(jí)中路徑的延伸都增大一倍 ,但比較它們的似然函數(shù)累加值后 ,丟棄一半 ,結(jié)果留存下來的路徑總數(shù)保持常數(shù) 。 由此可見 ,上述譯碼過程中的基本操作是 “ 加 — 比 — 選 ” ,即每級(jí)求出對(duì)數(shù)似然函數(shù)累加值 ,然后兩兩比較并作出選擇 。 有時(shí)會(huì)出現(xiàn)兩條路徑的對(duì)數(shù)似然函數(shù)累加值相 等的情形 ,在這種情況下可以任意選擇其中一條作為 “ 幸存 ” 路徑 。