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