糾錯(cuò)碼Lecture8-卷積碼(III)

Lecture8

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

對(duì)應(yīng)校驗(yàn)矩陣為：

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

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

(3,1,2)碼有兩個(gè)校驗(yàn)元，子生成元式：

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

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

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

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

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