1、第八講卷積碼的譯碼1回顧卷積碼是對信息流進行編碼的一種有記憶分組的編碼方法記憶有很多種，典型的為線性有限記憶和線性無限記憶當記憶為線性時，等效于輸入信息流與沖激響應之間的卷積可分別用FIR和IIR濾波器來描述矩陣描述、樹圖描述和網格圖表示2卷積碼的概率譯碼概率譯碼：結合信道符號統計特性的譯碼方法一種簡單的譯碼方法：逐分支譯碼在碼樹圖中每向前走一步，在決定走哪一個分支時根據該分支子碼與該時刻接收子碼之間的相似程度來判斷3逐分支譯碼舉例編碼符號為1時發+1，編碼符號為0時發-1當接收符號為：0.8, 0.7, -0.2, -0.3, 0.5, -0.3時，盡管第二次分支為兩個負數，但更象分支“1”

2、，因此判信息序列為1104逐分支譯碼的局限沒有利用卷積碼的記憶性例：當接收符號為：0.8, 0.7, -0.2, 0.1, 0.5, -0.3時，判信息序列為101但從整體序列來看，更像110因此不是最大似然序列譯碼5譯碼準則：對數似然度量log P(R|C)=logiP(ri|ci)=ilog(p(ri|ci)當在碼樹中沿正確路徑行進時，對數度量的整體趨勢呈線性變化。當在碼樹中沿完全錯誤（隨機）路徑行進時，對數度量的整體趨勢也呈線性變化，但斜率要低于正確路徑。6對數似然度量圖示正確路徑與隨機路徑7正確路徑與錯誤路徑由于信道干擾的原因，錯誤路徑并不總是比正確路徑的度量低，但一般情況下沿錯誤路徑

3、走下去總會導致度量的下降8局部錯誤不過由于卷積碼的記憶有限，可能會出現一條錯誤路徑最終與正確路徑會合的情況，這樣就會出現一段局部錯誤9譯碼錯誤當由于度量的起伏造成將局部錯誤的路徑看成正確路徑時，就發生誤碼。10對譯碼算法的要求能以很大概率發現當前走在錯誤路徑上能以很大概率回到正確路徑運算量和存貯量要適中11費諾度量為便于譯碼，要求正確路徑的度量變化斜率大于0，而錯誤路徑的度量變化斜率要小于0，因此要對分支度量加以調整同樣也是為了不同長度的路徑能進行比較費諾度量：二進制輸入的DMC信道：log2(p(ri|ci)/p(ri)-Rc 12局部錯誤與判斷門限對卷積碼來說，一般比較容易出現的錯誤都是較

4、小的碼距，而較小碼距的差錯圖案一般都是集中在一些序列段中，即由一些局部錯誤組成。序列譯碼就是要盡早發現這些局部錯誤，因為過了這些局部錯誤之后兩個序列的內容就相同了，因此后面的斜率也是相同的。局部錯誤在路徑度量變化中的體現應是一段下垂后繼續按正確斜率上升。因此要隨時調整判斷門限。13費諾算法14費諾算法的幾種情形在向前試探時，如果發現度量值大于當前門限，則向前移動到所試探的節點；如果這次試探是第一次，則可將門限作一定的提高；如果不是第一次，說明曾因門限太高而倒退過，因此不提高門限，以便后面的比較15費諾算法的另一些情形向前試探時，如果發現度量小于當前門限，說明比試探節點還要壞的節點度量更不可能超

5、過門限，因此在此節點上不必再向前試探下去，而應考慮向回作反向試探。如果反向試探結果是也小于門限，說明當前門限太高需要降低門限，再作向前試探；如果反向試探結果大于門限，說明反向試探節點度量門限前向試探節點，因此應考慮從反向試探節點另一個方向衍生一個試探節點，因此要回到反向試探節點，以便向前觀察下一個最佳節點。16堆棧算法核心：存貯一組可能的路徑，但每次只對當時認為的最佳路徑進行延伸，然后再重新排序。從碼樹圖起始節點開始將堆棧第一行中路徑向各分支延伸，計算新度量刪去第一行原存貯內容將延伸后的各路徑在堆棧中重新排序，找出度量量大的路徑放在第一行若第一行中的路徑已達碼樹終點，則結束，否則回到步驟217

6、堆棧算法的本質存貯一組可能路徑每次只有最可能的（度量最大的）路徑可以繁衍，同時刪去父路徑繁衍出的子路徑與其它未繁衍的路徑一起排序堆棧滿時最壞路徑被丟棄18序列譯碼的特點運算量與信道質量有關需要輸入緩沖器，其長度也與信道質量有關，有溢出現象計算量與約束長度無關19維特比譯碼卷積碼的網格圖描述：將狀態轉移圖按時間展開，用于描述從第k時刻的編碼器狀態到第k+1時刻的編碼狀態的轉移情況，以及在轉移過程中的輸出情況。20有限狀態編碼的最大似然譯碼當編碼器的狀態數有限時，不同編碼路徑必然會有會合的情況。例：一個信息長度為L的編碼，所有可能路徑數為2L個，而對于一個4狀態碼而言，任一時刻路徑只能經過4個狀態，因此大量的路徑（當用狀態轉移來描述時）是有重合的。由于碼的馬氏特性，從某一時刻開始的后續編碼只與該時刻的狀態有關，而與之前如何到達該狀態無關。21分段譯碼與殘留路徑一個長度為L的碼，在時刻k分為兩段，之前的稱為A，之后的稱為B。最大似然序列必存在于從k時刻的M個狀態出發（或在時刻k經過M個狀態的）的M*2L-k條路徑之中。而第k時刻到達每個狀態都有2k/M條A路徑，顯然，從第k時刻狀態S出發的最佳路徑的前半段必然是到達該狀態的2k/M條A路徑中的最佳A路徑。稱此最佳A路徑為第k時刻狀態S的殘留路徑。22推廣到每時刻一段因此在任