Lecture7

卷積碼(II)1內容狀態轉移圖和網格圖Viterbi譯碼算法修正的Viterbi譯碼算法2卷積碼的網格圖表示右圖為(2,1,2)卷積編碼示意圖，其生成多項式矩陣和生成矩陣分別為3卷積碼的狀態圖表示(2,1,2)碼的狀態圖如右圖所示卷積碼的自由距離等于編碼器從s0出發，又回到該狀態時，所有可能非全零路徑重量的最小值重量最小的路徑：

s0s1s2s0；相應的輸出碼字序列為：

111011

因此，df

=54卷積碼的網格圖表示s0s1s2s3s0s1s2s3狀態圖網格圖5Viterbi譯碼若編碼信息序列為1011100，則編碼過程即為在Trellis圖上尋找一條路徑6Viterbi譯碼譯碼過程即為在Trellis圖上尋找一條路徑，該路徑對應的編碼序列與接收序列之間有最大概率度量7Viterbi譯碼從第1時刻的全零狀態開始（零狀態初始度量為0，其它狀態初始度量為負無窮）在任一時刻t，對每一個狀態只記錄到達路徑中度量最大的一個（殘留路徑，硬判決為漢明距離，軟判決為歐氏距離）及其度量（狀態度量）在向t+1時刻前進過程中，對t時刻的每個狀態作延伸，即在狀態度量基礎上加上分支度量，得到|S|×2k條路徑對所得到的t+1時刻到達每一個狀態的2k條路徑進行比較，找到一個度量最大的作為殘留路徑直到碼的終點，如果確定終點是一個確定狀態，則最終保留的路徑就是譯碼結果8Viterbi譯碼在BSC和BIQO-DMC上，最大概率度量分別等效為最小Hamming距離度量和最小歐氏距離度量距離度量更新公式Theorem：在Viterbi譯碼算法中，留選路徑是有最大似然函數的路徑。9Viterbi譯碼第1個時刻接收子碼10漢明距離d11第2個時刻接收子碼10漢明距離dExample:M=(1011100)，初始狀態為全0的編碼器輸出序列為C=(11,10,00,01,10,01,11),通過有噪信道后，接收序列為R=(10,10,00,01,11,01,11)1110Viterbi譯碼第3個時刻接收子碼00漢明距離d213211Viterbi譯碼第4個時刻接收子碼01漢明距離d3,43,43,31,5漢明距離d3331213312Viterbi譯碼第5個時刻接收子碼11漢明距離d3,53,52,42,4漢明距離d3322331313Viterbi譯碼第6個時刻接收子碼01漢明距離d3,42,5漢明距離d3233223,43,43314Viterbi譯碼第7個時刻接收子碼11漢明距離d2,5323301/000/101/110/110/011/14,44,43,415Viterbi譯碼保存的幸存路徑為：譯碼結果為：101110016Viterbi譯碼——收尾最大似然序列譯碼要求序列有限，因此對卷積碼來說，要求能收尾。收尾的原則在信息序列輸入完成后，利用輸入一些特定的比特，使|S|個狀態的各殘留路徑可以到達某一已知狀態（一般是全零狀態）。這樣就變成只有一條殘留路徑，這就是最大似然序列。非遞歸卷積碼約束長度為m+1的卷積碼，只要在信息序列輸入完成后連續送入m個0，即可使任一路徑都到達最終的狀態0。遞歸卷積碼可通過將輸入值置成反饋值的負值，而使m個時鐘后的狀態到達0。17Viterbi譯碼——收尾非系統非遞歸碼遞歸系統碼18Viterbi譯碼第6個時刻接收子碼01漢明距離d3,42,5漢明距離d323322Example(cont.):M=(10111);M’=(1011100)19Viterbi譯碼第7個時刻接收子碼11漢明距離d2,520Viterbi譯碼保存的幸存路徑為：譯碼結果為：101110021軟判決Viterbi譯碼基本思想為了充分利用信道輸出符號的信息，提高譯碼可靠性，把信道輸出的信號進行Q電平量化，然后在輸入Viterbi譯碼器。能適應這種Q進制輸入的Viterbi譯碼器稱為軟判決Viterbi譯碼器。例子：Q=4電平量化的信道比特度量0010211211108500581022Viterbi譯碼的復雜度對信息序列長度為L，信息符號取自GF(p)，R=k/n，約束長度為m+1的卷積碼。狀態數為pkm因此對每個時刻要做pkm次加比選得到pkm個狀態的殘留路徑每次加比選包括pk次加法和pk-1次比較。因此總運算量約為Lpkm次加比選同時要能保存pkm條殘留路徑，因此需要Lpkm個存貯單元。23Viterbi譯碼的特點維特比算法是最大似然的序列譯碼算法譯碼復雜度與信道質量無關運算量與碼長呈線性關系存貯量與碼長呈線性關系運算量和存貯量都與狀態數呈線性關系狀態數隨分組大小k及編碼存貯m呈指數關系24修正的Viterbi譯碼算法基本思想當狀態數有限時，給定時刻的各狀態殘留路徑在一定時間（L）之前來自于同一狀態的可能性隨L的增加而迅速趨近于1。因此當前時刻各殘留路徑很可能來自于L時刻前的同一路徑。25修正的Viterbi算法實現在第k時刻，可以將t-L時刻前的路徑結果直接輸出，而在存貯空間中不再保存t-L時刻前的內容。因此存貯量控制在Lpkm。這里的L就被稱做譯碼深度，不再隨碼長的增加而增加。因而特別適合信息流的卷積碼編譯碼。在這種情況下甚至不需要對流分段加尾比特。顯然，滑動窗算法是一種準最優算法。但通常譯碼深度只要有編碼約束長度的5到10倍，其性能損失就可以忽略不計了。26修正的Vite