糾錯(cuò)碼Lecture7-卷積碼(II)

Lecture7

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

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

111011

因此，df

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