糾錯碼Lecture8-卷積碼(III)

Lecture8

卷積碼(III)2內(nèi)容大數(shù)邏輯譯碼Fano譯碼算法ST譯碼算法3大數(shù)邏輯譯碼例子：設(shè)（2,1,6）系統(tǒng)卷積碼，子生成元：

對應(yīng)校驗矩陣為：

4大數(shù)邏輯譯碼設(shè)錯誤圖樣伴隨式為式中5大數(shù)邏輯譯碼由以上7個方程知，在s01，s21，s51和s61四個方程中，除e01外，其他碼元位至多出現(xiàn)一次，從而組成4個對e01碼元位正交的一致校驗和式。所以e01位上的錯誤完全可以由s01，s21，s51和s61確定，而它們的值由H中的第0、2、5、6行的校驗關(guān)系決定。定義：任一個（n0，k0，m）系統(tǒng)卷積碼，若能由H矩陣中的Ji行直接組成對e01（i=1,2，…k0,若為非系統(tǒng)碼i=1,2，…n0

）正交的Ji正交校驗和式，則稱此碼為自正交系統(tǒng)卷積碼，若碼的最小距離dFD=J+1，則稱為完備自正交碼。6大數(shù)邏輯譯碼例子：構(gòu)造（3,1,2）和（3,2,2,）碼的子正交系統(tǒng)卷積碼大數(shù)邏輯譯碼器。

(3,1,2)碼有兩個校驗元，子生成元式：

(3,1,2)碼有兩個信息元，子生成元式：

7大數(shù)邏輯譯碼故，對（3,1,2）碼對（3,1,2）碼

顯然它們是對偶碼8大數(shù)邏輯譯碼

由H(D)容易求出（3,1,2）和其對偶碼（3,2,2）的校驗矩陣H9大數(shù)邏輯譯碼由H1可組成（3,1,2）碼的以下4個對e01正交的校驗和式：由H2可得到對e01和e02正交的校驗和式：10大數(shù)邏輯譯碼由此可知，該碼能糾正連續(xù)9個碼元的錯誤，兩個碼的大數(shù)邏輯譯碼器圖為：11大數(shù)邏輯譯碼12大數(shù)邏輯譯碼譯碼過程：把接收到的R(D)中的每一段信息元送入編碼器中求出校驗元，與其后面的校驗元模2加，若兩者一致，則輸出的伴隨式分量si為0，否則為1；把加得的值送入伴隨式寄存器中寄存；當(dāng)接收完3個碼段以后就開始對第0碼段糾錯，若此時大數(shù)邏輯門的輸出為1，則說明第0碼段的信息元有錯，此時正好第0子組的信息元移至編碼器的輸出端，從而把它們糾正。13大數(shù)邏輯譯碼同時，糾錯信號也反饋至伴隨式寄存器修正伴隨式，以消除此錯誤的影響。如果大數(shù)判決門沒有輸出，則說明第0子組的信息元沒有錯誤，這時從編碼器中直接將信息元輸出。譯碼器每接收一個碼段就對此時前m個時刻輸入的碼段譯碼，故該類譯碼器的譯碼約束度等于編碼約束度為m+1。由于伴隨式寄存器中一半以上為1時，大數(shù)邏輯門才有信號輸出，所以每次對伴隨式修正總能使伴隨式重量減輕，從而不會引起誤差傳播。14序列譯碼Viterbi譯碼算法存在的問題對m值很大的情況不適用——誤碼率很難做的很低譯每一個分支的計算量不變Viterbi譯碼中路徑度量計算方法不適用于比較不同長度的路徑，如

R=(10,10,00,01,11,01,00)

C5=(11,10,00,01,10,01)

C0=(11)d(R0…R5,C5)=2d(R0,C0)=1要求誤碼率很低，且譯碼器計算量可隨信道情況變化時，需采用序列譯碼一個簡單的譯碼算法：逐分支譯碼15卷積碼的樹圖表示右圖為(2,1,2)卷積編碼示意圖，其生成多項式矩陣和生成矩陣分別為若輸入的信息序列M=(11011…)則編碼器的輸出為16卷積碼的樹圖表示其樹圖表示為正確路徑a/b:a表示由n0個碼元構(gòu)成的子碼，b表示k0個信息元初始截段碼∞11/100/000/011/111/110/001/100/010/011/000/101/101/010/117卷積碼的樹圖表示編碼過程的實質(zhì)在輸入序列的控制下，編碼器沿碼樹通過某一特定路徑的過程譯碼過程的實質(zhì)根據(jù)接收序列以及信道干擾的統(tǒng)計特性，譯碼器在原碼樹上尋找正確路徑的過程碼樹中子集的劃分18卷積碼的距離度量最小漢明距離不同初始截段碼字子集之間的最小漢明距離，用于衡量代數(shù)譯碼的性能第0子組為非零的初始截短碼字的最小重量如:(2,1,2)碼的最小距離為dmin=3自由距離在所有半無限長碼序列之間的最小漢明距離定義為卷積碼的自由距離，用于衡量概率譯碼的性能如:(2,1,2)碼的最小距離為df=5Remark不同于分組碼，在某些碼中，非系統(tǒng)碼的df比系統(tǒng)碼大19逐分支譯碼舉例編碼符號為1時發(fā)+1，編碼符號為0時發(fā)-1當(dāng)接收符號為：0.8,0.7,-0.2,-0.3,0.5,-0.3時，盡管第二次分支為兩個負(fù)數(shù)，但更象分支“1”，因此判信息序列為110第二次分支110:d=|1-(-0.2)|+|-1-(-0.3)|=1.9001:d=|-1-(-0.2)|+|1-(-0.3)|=2.120逐分支譯碼的局限沒有利用卷積碼的記憶性例：當(dāng)接收符號為：0.8,0.7,-0.2,0.1,0.5,-0.3時，判信息序列為101但從整體序列來看，更像110101110100:d=0.2+0.3+0.8+0.9+1.5+0.7=4.4110111010:d=0.2+0.3+1.2+1.1+0.5+0.7=4.0因此不是最大似然序列譯碼21譯碼特性一個好的譯碼算法，必須滿足以下幾點能以很大概率發(fā)現(xiàn)當(dāng)前走在錯誤路徑上能以很大概率回到正確路徑運算量和存貯量要適中當(dāng)在碼樹中沿正確路徑行進(jìn)時，R與C的l段長碼序列之間總的Hamming距離的趨勢與l呈線性變化。大數(shù)定律,pe為BSC的轉(zhuǎn)移概率當(dāng)在碼樹中沿完全錯誤（隨機(jī)）路徑行進(jìn)時，Hamming距離的整體趨勢也呈線性變化，但斜率要高于正確路徑，約為n/2。R與C完全不相關(guān)22譯碼特性正確路徑、隨機(jī)路徑以及判決準(zhǔn)則23譯碼特性斜距離由于信道干擾的原因，錯誤路徑并不總是比正確路徑的度量低，但一般情況下沿錯誤路徑走下去總會導(dǎo)致度量的下降24局部錯誤不過由于卷積碼的記憶有限，可能會出現(xiàn)一條錯誤路徑最終與正確路徑會合的情況，這樣就會出現(xiàn)一段局部錯誤誤碼兩條路徑在此有相同狀態(tài)25錯誤事件當(dāng)由于度量的起伏造成將局部錯誤的路徑看成正確路徑時，就發(fā)生誤碼。對卷積碼來說，一般比較容易出現(xiàn)的錯誤都是較小的碼距，而較小碼距的差錯圖案一般都是集中在一些序列段中，即由一些局部錯誤組成。序列譯碼就是要盡早發(fā)現(xiàn)這些局部錯誤，因為過了這些局部錯誤之后兩個序列的內(nèi)容就相同了，因此后面的斜率也是相同的。局部錯誤在路徑度量變化中的體現(xiàn)應(yīng)是一段下垂后繼續(xù)按正確斜率上升。因此要隨時調(diào)整判斷門限。26Fano度量最大似然譯碼：接收序列碼字序列ML判決序列對離散無記憶信道27Fano度量Bayesian公式：若發(fā)送序列先驗等概，即另外，則有28Fano度量對數(shù)似然值Fano度量Fano譯碼用Fano度量代替斜距離29Fano度量例子R=(10,10,00,01,11,01,00),C5=(11,10,00,01,10,01),C0=(11)，信道轉(zhuǎn)移概率為p=0.1，求和30Fano算法在向前試探時，如果發(fā)現(xiàn)度量值大于當(dāng)前門限，則向前移動到所試探的節(jié)點；如果這次試探是第一次，則可將門限作一定的提高；如果不是第一次，說明曾因門限太高而倒退過，因此不提高門限，以便后面的比較。31Fano算法向前試探時，如果發(fā)現(xiàn)度量小于當(dāng)前門限，說明比試探節(jié)點還要壞的節(jié)點度量更不可能超過門限，因此在此節(jié)點上不必再向前試探下去，而應(yīng)考慮向回作反向試探。如果反向試探結(jié)果是也小于門限，說明當(dāng)前門限太高需要降低門限，再作向前試探；如果反向試探結(jié)果大于門限，說明反向試探節(jié)點度量>門限>前向試探節(jié)點，因此應(yīng)考慮從反向試探節(jié)點另一個方向衍生一個試探節(jié)點，因此要回到反向試探節(jié)點，以便向前觀察下一個最佳節(jié)點。32Fano算法先找一個最佳節(jié)點，大于門限，則前進(jìn)并提高門限；再向前找一個最佳節(jié)點，大于門限，則前進(jìn)并提高門限，再向前找一個最佳節(jié)點，小于門限33Fano算法34Fano算法特點譯碼器每幀的計算次數(shù)，隨著信道干擾的大小而變化計算次數(shù)與每次的門限增量密切相關(guān)，門限增量小，則計算次數(shù)增加，反之則減少，但門限增量取值過大，譯碼器不易發(fā)現(xiàn)錯誤路徑，影響譯碼性能。譯碼器需要一個輸入緩沖器，以存儲輸入的接收序列。若信道干擾很大時，譯碼器搜索時間很長，可能引起緩存器溢出。35堆棧(ST)算法核心：存貯一組可能的路徑，但每次只對當(dāng)時認(rèn)為的最佳路徑進(jìn)行延伸，然后再重新排序。從碼樹圖起始節(jié)點開始將堆棧第一行中路徑向各分支延伸，計算新度量刪去第一行原存貯內(nèi)容將延伸后的各路徑在堆棧中重新排序，找出度量量大的路徑放在第一行若第一行中的路徑已達(dá)碼樹終點，則結(jié)束，否則回到步驟2譯碼完畢，將存儲器中第一行的內(nèi)容送給用戶。36堆棧(ST)算法堆棧(ST)算法流程圖：37ST算法的本質(zhì)存貯一組可能路徑每次只有最可能的（度量最大的）路徑可以繁衍，同時刪去父路徑繁衍出的子路徑與其它未繁衍的路徑一起排序堆棧滿時最壞路徑被丟棄38