糾錯碼Lecture7-卷積碼(II)

Lecture7

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

s0s1s2s0；相應(yīng)的輸出碼字序列為：

111011

因此，df

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