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

1、信道編碼理論信道編碼理論邢莉娟、李卓，西安電子科技大學(xué)邢莉娟、李卓，西安電子科技大學(xué)1Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論2狀態(tài)轉(zhuǎn)移圖和網(wǎng)格圖狀態(tài)轉(zhuǎn)移圖和網(wǎng)格圖Viterbi譯碼算法譯碼算法修正的修正的Viterbi譯碼算法譯碼算法Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論3右圖為右圖為(2,1,2)卷積編碼示意圖，其生成多項(xiàng)式矩陣和生卷積編碼示意圖，其生成多項(xiàng)式矩陣和生成矩陣分別為成矩陣分別為22( )1, 1DDDDG11 101111 101111 1011GLecture 7 Le

2、cture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論4(2, 1, 2)碼的狀態(tài)圖如右圖所示碼的狀態(tài)圖如右圖所示卷積碼的自由距離等于編碼卷積碼的自由距離等于編碼 器從器從s0出發(fā)，又回到該狀態(tài)出發(fā)，又回到該狀態(tài) 時(shí)，所有可能非全零路徑重時(shí)，所有可能非全零路徑重 量的最小值量的最小值重量最小的路徑：重量最小的路徑： s0s1s2s0； 相應(yīng)的輸出碼字序列為：相應(yīng)的輸出碼字序列為： 111011 因此，因此，df =5Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論5s0s1s2s3s0s1s2s3狀態(tài)圖狀態(tài)圖網(wǎng)格圖網(wǎng)格圖Lecture

3、7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論6若編碼信息序列為若編碼信息序列為 1011100，則編碼過程即為在，則編碼過程即為在Trellis圖上尋找一條路徑圖上尋找一條路徑Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論7譯碼過程即為在譯碼過程即為在Trellis圖上尋找一條路徑，該路圖上尋找一條路徑，該路徑對(duì)應(yīng)的編碼序列徑對(duì)應(yīng)的編碼序列與接收序列之間有最大概率度與接收序列之間有最大概率度量量0max(|( )maxlog(|( ) 1,2,2k LjjjjPPjR CSR CSLecture 7 Lecture

4、7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論8從第從第1時(shí)刻的全零狀態(tài)開始（零狀態(tài)初始度量為時(shí)刻的全零狀態(tài)開始（零狀態(tài)初始度量為0，其它狀，其它狀態(tài)初始度量為態(tài)初始度量為負(fù)無窮負(fù)無窮）在任一時(shí)刻在任一時(shí)刻t，對(duì)每一個(gè)狀態(tài)只記錄到達(dá)路徑中度量最大，對(duì)每一個(gè)狀態(tài)只記錄到達(dá)路徑中度量最大的一個(gè)（殘留路徑，的一個(gè)（殘留路徑，硬判決為漢明距離，軟判決為歐氏距硬判決為漢明距離，軟判決為歐氏距離離）及其度量（狀態(tài)度量）及其度量（狀態(tài)度量）在向在向t+1時(shí)刻前進(jìn)過程中，對(duì)時(shí)刻前進(jìn)過程中，對(duì)t時(shí)刻的每個(gè)狀態(tài)作延伸，即時(shí)刻的每個(gè)狀態(tài)作延伸，即在狀態(tài)度量基礎(chǔ)上加上分支度量，得到在狀態(tài)度量基礎(chǔ)上加上分支度

5、量，得到|S|2k條路徑條路徑對(duì)所得到的對(duì)所得到的t+1時(shí)刻到達(dá)每一個(gè)狀態(tài)的時(shí)刻到達(dá)每一個(gè)狀態(tài)的2k條路徑進(jìn)行比較，條路徑進(jìn)行比較，找到一個(gè)度量最大的作為殘留路徑找到一個(gè)度量最大的作為殘留路徑直到碼的終點(diǎn)，如果確定終點(diǎn)是一個(gè)確定狀態(tài)，則最終保直到碼的終點(diǎn)，如果確定終點(diǎn)是一個(gè)確定狀態(tài)，則最終保留的路徑就是譯碼結(jié)果留的路徑就是譯碼結(jié)果Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論9在在BSC和和BIQO-DMC上，最大概率度量分別等效為最小上，最大概率度量分別等效為最小Hamming距離度量和最小歐氏距離度量距離度量和最小歐氏距離度量 距離度量更新公式

6、距離度量更新公式 Theorem：在：在Viterbi譯碼算法中，留選路徑是有最大似然譯碼算法中，留選路徑是有最大似然函數(shù)的路徑。函數(shù)的路徑。111111111 min(, ()min(, (), min min(, (), tttttttttttttttttttsddd rc ssdd rc ssSSSRC SRC SRC SttttSSSS max(|( )maxlog(|( ) min, ( )PPdR C SR C SR C SLecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論10第1個(gè)時(shí)刻接收子碼10漢明距離d11第2個(gè)時(shí)刻接收子碼10漢明距

7、離dExample: M=(1011100)，初始狀態(tài)為全0的編碼器輸出序列為C=(11, 10, 00, 01, 10, 01, 11), 通過有噪信道后，接收序列為R=(10, 10, 00, 01, 11, 01, 11)11Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論11第3個(gè)時(shí)刻接收子碼00漢明距離d2132Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論12第4個(gè)時(shí)刻接收子碼01漢明距離d3,43,43,31,5漢明距離d33312133Lecture 7 Lecture 7 卷積碼卷積碼(

8、II)(II)信道編碼理論信道編碼理論13第5個(gè)時(shí)刻接收子碼11漢明距離d3,53,52,42,4漢明距離d33223313Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論14第6個(gè)時(shí)刻接收子碼01漢明距離d3,42,5漢明距離d3233223,43,433Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論15第7個(gè)時(shí)刻接收子碼11漢明距離d2,5323301/000/101/110/110/011/14,44,43,4Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理

9、論16保存的保存的幸存路徑幸存路徑為為：譯碼結(jié)果為：譯碼結(jié)果為：1011100Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論17最大似然序列譯碼要求序列有限，因此對(duì)卷積碼來說，要最大似然序列譯碼要求序列有限，因此對(duì)卷積碼來說，要求能收尾。求能收尾。收尾的原則收尾的原則 在信息序列輸入完成后，利用輸入一些特定的比特，使在信息序列輸入完成后，利用輸入一些特定的比特，使|S|個(gè)狀態(tài)個(gè)狀態(tài)的各殘留路徑可以到達(dá)某一已知狀態(tài)（一般是全零狀態(tài)）。這樣的各殘留路徑可以到達(dá)某一已知狀態(tài)（一般是全零狀態(tài)）。這樣就變成就變成只有一條殘留路徑只有一條殘留路徑，這就是最大似

10、然序列。，這就是最大似然序列。非遞歸卷積碼非遞歸卷積碼 約束長度為約束長度為m+1的卷積碼，只要在信息序列輸入完成后的卷積碼，只要在信息序列輸入完成后連續(xù)送入連續(xù)送入m個(gè)個(gè)0，即可使任一路徑都到達(dá)最終的狀態(tài)，即可使任一路徑都到達(dá)最終的狀態(tài)0。遞歸卷積碼遞歸卷積碼 可通過將輸入值置成反饋值的負(fù)值，而使可通過將輸入值置成反饋值的負(fù)值，而使m個(gè)時(shí)鐘后的狀態(tài)到達(dá)個(gè)時(shí)鐘后的狀態(tài)到達(dá)0。Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論18DD非系統(tǒng)非遞非系統(tǒng)非遞歸碼歸碼遞歸系統(tǒng)碼遞歸系統(tǒng)碼Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編

11、碼理論信道編碼理論19第6個(gè)時(shí)刻接收子碼01漢明距離d3,42,5漢明距離d323322Example (cont.): M=(10111); M=(1011100)Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論20第7個(gè)時(shí)刻接收子碼11漢明距離d2,5Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論21保存的保存的幸存路徑幸存路徑為為：譯碼結(jié)果為：譯碼結(jié)果為：1011100Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論22基本思想基本思想為了充分利用信道輸出

12、符號(hào)的信息，提高譯碼可靠性，為了充分利用信道輸出符號(hào)的信息，提高譯碼可靠性，把信道輸出的信號(hào)進(jìn)行把信道輸出的信號(hào)進(jìn)行Q電平量化，然后在輸入電平量化，然后在輸入Viterbi譯碼器。能適應(yīng)這種譯碼器。能適應(yīng)這種Q進(jìn)制輸入的進(jìn)制輸入的Viterbi譯碼器稱為譯碼器稱為軟軟判決判決Viterbi譯碼器譯碼器。例子：例子：Q=4電平量化的信道比特度量電平量化的信道比特度量00102112111085005810Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論23對(duì)信息序列長度為對(duì)信息序列長度為L，信息符號(hào)取自，信息符號(hào)取自GF(p)，R=k/n，約束長度為，

13、約束長度為m+1的卷積碼。狀態(tài)數(shù)為的卷積碼。狀態(tài)數(shù)為pkm因此對(duì)每個(gè)時(shí)刻要做因此對(duì)每個(gè)時(shí)刻要做pkm次次加比選加比選得到得到pkm個(gè)狀態(tài)的殘留個(gè)狀態(tài)的殘留路徑路徑每次加比選包括每次加比選包括pk次加法和次加法和pk-1次比較次比較。因此總運(yùn)算量。因此總運(yùn)算量約為約為Lpkm次加比選次加比選同時(shí)要能保存同時(shí)要能保存pkm條殘留路徑，因此需要條殘留路徑，因此需要Lpkm個(gè)存貯單個(gè)存貯單元。元。Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論24維特比算法是最大似然的序列譯碼算法維特比算法是最大似然的序列譯碼算法譯碼復(fù)雜度與信道質(zhì)量無關(guān)譯碼復(fù)雜度與信道質(zhì)量

14、無關(guān)運(yùn)算量與碼長呈線性關(guān)系運(yùn)算量與碼長呈線性關(guān)系存貯量與碼長呈線性關(guān)系存貯量與碼長呈線性關(guān)系運(yùn)算量和存貯量都與狀態(tài)數(shù)呈線性關(guān)系運(yùn)算量和存貯量都與狀態(tài)數(shù)呈線性關(guān)系狀態(tài)數(shù)隨分組大小狀態(tài)數(shù)隨分組大小k及編碼存貯及編碼存貯m呈呈指數(shù)指數(shù)關(guān)系關(guān)系Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論25基本思想基本思想當(dāng)狀態(tài)數(shù)有限時(shí)，給定時(shí)刻的各狀態(tài)殘留路徑在一定當(dāng)狀態(tài)數(shù)有限時(shí)，給定時(shí)刻的各狀態(tài)殘留路徑在一定時(shí)間（時(shí)間（L）之前來自于同一狀態(tài)的可能性隨）之前來自于同一狀態(tài)的可能性隨L的增加而的增加而迅速趨近于迅速趨近于1。因此當(dāng)前時(shí)刻各殘留路徑很可能來自于。因此當(dāng)前

15、時(shí)刻各殘留路徑很可能來自于L時(shí)刻前的同一路徑。時(shí)刻前的同一路徑。Lecture 7 Lecture 7 卷積碼卷積碼(II)(II)信道編碼理論信道編碼理論26在第在第k時(shí)刻，可以將時(shí)刻，可以將t-L時(shí)刻前的路徑結(jié)果直接輸出，而在時(shí)刻前的路徑結(jié)果直接輸出，而在存貯空間中不再保存存貯空間中不再保存t-L時(shí)刻前的內(nèi)容。因此存貯量控制時(shí)刻前的內(nèi)容。因此存貯量控制在在Lpkm。這里的。這里的L就被稱做就被稱做譯碼深度譯碼深度，不再隨碼長的增加，不再隨碼長的增加而增加。因而特別適合信息流的卷積碼編譯碼。在這種情而增加。因而特別適合信息流的卷積碼編譯碼。在這種情況下甚至況下甚至不需要對(duì)流分段加尾比特不需要對(duì)流分段加尾比特。顯然，滑動(dòng)窗算法是一種準(zhǔn)最優(yōu)算法。但通常譯碼深度只顯然，滑動(dòng)窗算法是一種準(zhǔn)最優(yōu)算法。但通常譯碼深度只要有編碼約束長度的要有編碼約束長度的5到到10倍，其性能損失就可以忽略不倍，其性能損失就可以忽略不計(jì)了。計(jì)了。Lecture 7 Lecture 7 卷積碼