信道編碼理論

信道編碼理論第一頁，共五十二頁，2022年，8月28日卷積碼的Trellis圖表示右圖為(2,1,2)卷積編碼示意圖，其生成多項式矩陣和生成矩陣分別為:2第二頁，共五十二頁，2022年，8月28日卷積碼的Trellis圖表示s0s1s2s3s0s1s2s3狀態(tài)圖Trellis圖3第三頁，共五十二頁，2022年，8月28日Viterbi譯碼若編碼信息序列為1011100，則編碼過程即為在Trellis圖上尋找一條路徑。4第四頁，共五十二頁，2022年，8月28日Viterbi譯碼譯碼過程即為在Trellis圖上尋找一條路徑，該路徑對應(yīng)的編碼序列與接收序列之間有最大概率度量：5第五頁，共五十二頁，2022年，8月28日Viterbi譯碼從第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é)果。6第六頁，共五十二頁，2022年，8月28日Viterbi譯碼在BSC和BIQO-DMC上，最大概率度量分別等效為最小Hamming距離度量和最小歐氏距離度量。距離度量更新公式：Theorem：在Viterbi譯碼算法中，留選路徑是有最大似然函數(shù)的路徑。7第七頁，共五十二頁，2022年，8月28日Viterbi譯碼第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)118第八頁，共五十二頁，2022年，8月28日Viterbi譯碼第3個時刻接收子碼00漢明距離d21329第九頁，共五十二頁，2022年，8月28日Viterbi譯碼第4個時刻接收子碼01漢明距離d3,43,43,31,5漢明距離d3331213310第十頁，共五十二頁，2022年，8月28日Viterbi譯碼第5個時刻接收子碼11漢明距離d3,53,52,42,4漢明距離d3322331311第十一頁，共五十二頁，2022年，8月28日Viterbi譯碼第6個時刻接收子碼01漢明距離d3,42,5漢明距離d3233223,43,43312第十二頁，共五十二頁，2022年，8月28日Viterbi譯碼第7個時刻接收子碼11漢明距離d2,5323301/000/101/110/110/011/14,44,43,413第十三頁，共五十二頁，2022年，8月28日Viterbi譯碼保存的幸存路徑為：譯碼結(jié)果為：101110014第十四頁，共五十二頁，2022年，8月28日Viterbi譯碼——收尾最大似然序列譯碼要求序列有限，因此對卷積碼來說，要求能收尾。收尾的原則在信息序列輸入完成后，利用輸入一些特定的比特，使|S|個狀態(tài)的各殘留路徑可以到達某一已知狀態(tài)（一般是全零狀態(tài)）。這樣就變成只有一條殘留路徑，這就是最大似然序列。非遞歸卷積碼約束長度為m+1的卷積碼，只要在信息序列輸入完成后連續(xù)送入m個0，即可使任一路徑都到達最終的狀態(tài)0。遞歸卷積碼可通過將輸入值置成反饋值的負值，而使m個時鐘后的狀態(tài)到達0。15第十五頁，共五十二頁，2022年，8月28日Viterbi譯碼——收尾非系統(tǒng)非遞歸碼遞歸系統(tǒng)碼16第十六頁，共五十二頁，2022年，8月28日Viterbi譯碼第6個時刻接收子碼01漢明距離d3,42,5漢明距離d323322Example(cont.):M=(10111);M’=(1011100)17第十七頁，共五十二頁，2022年，8月28日Viterbi譯碼第7個時刻接收子碼11漢明距離d2,518第十八頁，共五十二頁，2022年，8月28日Viterbi譯碼保存的幸存路徑為：譯碼結(jié)果為：101110019第十九頁，共五十二頁，2022年，8月28日軟判決Viterbi譯碼基本思想：為了充分利用信道輸出符號的信息，提高譯碼可靠性，把信道輸出的信號進行Q電平量化，然后在輸入Viterbi譯碼器。能適應(yīng)這種Q進制輸入的Viterbi譯碼器稱為軟判決Viterbi譯碼器。例子：Q=4電平量化的信道比特度量：001021121120第二十頁，共五十二頁，2022年，8月28日Viterbi譯碼的復(fù)雜度對信息序列長度為L，信息符號取自GF(p)，R=k/n，約束長度為m+1的卷積碼。狀態(tài)數(shù)為pkm因此對每個時刻要做pkm次加比選得到pkm個狀態(tài)的殘留路徑；每次加比選包括pk次加法和pk-1次比較。因此總運算量約為Lpkm次加比選；同時要能保存pkm條殘留路徑，因此需要Lpkm個存貯單元。21第二十一頁，共五十二頁，2022年，8月28日Viterbi譯碼的特點維特比算法是最大似然的序列譯碼算法；譯碼復(fù)雜度與信道質(zhì)量無關(guān)；運算量與碼長呈線性關(guān)系；存貯量與碼長呈線性關(guān)系；運算量和存貯量都與狀態(tài)數(shù)呈線性關(guān)系；狀態(tài)數(shù)隨分組大小k及編碼存貯m呈指數(shù)關(guān)系。22第二十二頁，共五十二頁，2022年，8月28日滑窗Viterbi譯碼算法基本思想：當狀態(tài)數(shù)有限時，給定時刻的各狀態(tài)殘留路徑在一定時間（L）之前來自于同一狀態(tài)的可能性隨L的增加而迅速趨近于1。因此當前時刻各殘留路徑很可能來自于L時刻前的同一路徑。23第二十三頁，共五十二頁，2022年，8月28日滑窗Viterbi算法實現(xiàn)在第t時刻，可以將t-L時刻前的路徑結(jié)果直接輸出，而在存貯空間中不再保存t-L時刻前的內(nèi)容。因此存貯量控制在Lpkm。這里的L就被稱做譯碼深度，不再隨碼長的增加而增加。因而特別適合信息流的卷積碼編譯碼。在這種情況下甚至不需要對流分段加尾比特。顯然，滑動窗算法是一種準最優(yōu)算法。但通常譯碼深度只要有編碼約束長度的5到10倍，其性能損失就可以忽略不計了。24第二十四頁，共五十二頁，2022年，8月28日縮減狀態(tài)的Viterbi譯碼由于運算量與k和m呈指數(shù)關(guān)系，因此維特比譯碼算法一般只適合于k和m較小的場合。大多數(shù)情況下k=1，m<10。對狀態(tài)數(shù)很大的卷積碼，維特比算法要經(jīng)一定的修正后才可能實用，常用的算法是縮減狀態(tài)的維特比譯碼，即在每一時刻，只處理部分的狀態(tài)。25第二十五頁，共五十二頁，2022年，8月28日第十二章卷積碼的概率譯碼（II）序列譯碼Fano譯碼算法ST譯碼算法調(diào)制與編碼的結(jié)合(TCM技術(shù))26第二十六頁，共五十二頁，2022年，8月28日序列譯碼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要求誤碼率很低，且譯碼器計算量可隨信道情況變化時，需采用序列譯碼:一個簡單的譯碼算法：逐分支譯碼。27第二十七頁，共五十二頁，2022年，8月28日逐分支譯碼舉例編碼符號為1時發(fā)+1，編碼符號為0時發(fā)-1。當接收符號為：0.8,0.7,-0.2,-0.3,0.5,-0.3時，盡管第二次分支為兩個負數(shù)，但更象分支“1”，因此判信息序列為110。第二次分支：110:d=|1-(-0.2)|+|-1-(-0.3)|=1.9001:d=|-1-(-0.2)|+|1-(-0.3)|=2.128第二十八頁，共五十二頁，2022年，8月28日逐分支譯碼的局限沒有利用卷積碼的記憶性；例：當接收符號為：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因此不是最大似然序列譯碼。29第二十九頁，共五十二頁，2022年，8月28日譯碼特性一個好的譯碼算法，必須滿足以下幾點：能以很大概率發(fā)現(xiàn)當前走在錯誤路徑上；能以很大概率回到正確路徑；運算量和存貯量要適中。當在碼樹中沿正確路徑行進時，R與C的l段長碼序列之間總的Hamming距離的趨勢與l呈線性變化。大數(shù)定律,pe為BSC的轉(zhuǎn)移概率。當在碼樹中沿完全錯誤（隨機）路徑行進時，Hamming距離的整體趨勢也呈線性變化，但斜率要高于正確路徑，約為n0/2。R與C完全不相關(guān)。30第三十頁，共五十二頁，2022年，8月28日譯碼特性正確路徑、隨機路徑以及判決準則:31第三十一頁，共五十二頁，2022年，8月28日譯碼特性斜距離:由于信道干擾的原因，錯誤路徑并不總是比正確路徑的度量低，但一般情況下沿錯誤路徑走下去總會導致度量的下降。32第三十二頁，共五十二頁，2022年，8月28日局部錯誤不過由于卷積碼的記憶有限，可能會出現(xiàn)一條錯誤路徑最終與正確路徑會合的情況，這樣就會出現(xiàn)一段局部錯誤。誤碼兩條路徑在此有相同狀態(tài)33第三十三頁，共五十二頁，2022年，8月28日錯誤事件當由于度量的起伏造成將局部錯誤的路徑看成正確路徑時，就發(fā)生誤碼。對卷積碼來說，一般比較容易出現(xiàn)的錯誤都是較小的碼距，而較小碼距的差錯圖案一般都是集中在一些序列段中，即由一些局部錯誤組成。序列譯碼就是要盡早發(fā)現(xiàn)這些局部錯誤，因為過了這些局部錯誤之后兩個序列的內(nèi)容就相同了，因此后面的斜率也是相同的。局部錯誤在路徑度量變化中的體現(xiàn)應(yīng)是一段下垂后繼續(xù)按正確斜率上升。因此要隨時調(diào)整判斷門限。34第三十四頁，共五十二頁，2022年，8月28日Fano度量最大似然譯碼：接收序列：碼字序列：ML判決序列：對離散無記憶信道：35第三十五頁，共五十二頁，2022年，8月28日Fano度量Bayesian公式：若發(fā)送序列先驗等概，即另外，則有36第三十六頁，共五十二頁，2022年，8月28日Fano度量對數(shù)似然值：Fano度量：Fano譯碼：用Fano度量代替斜距離：37第三十七頁，共五十二頁，2022年，8月28日Fano度量例子：R=(10,10,00,01,11,01,00),C5=(11,10,00,01,10,01),C0=(11)，信道轉(zhuǎn)移概率為p=0.1，求和38第三十八頁，共五十二頁，2022年，8月28日Fano算法在向前試探時，如果發(fā)現(xiàn)度量值大于當前門限，則向前移動到所試探的節(jié)點；如果這次試探是第一次，則可將門限作一定的提高；如果不是第一次，說明曾因門限太高而倒退過，因此不提高門限，以便后面的比較。39第三十九頁，共五十二頁，2022年，8月28日Fano算法向前試探時，如果發(fā)現(xiàn)度量小于當前門限，說明比試探節(jié)點還要壞的節(jié)點度量更不可能超過門限，因此在此節(jié)點上不必再向前試探下去，而應(yīng)考慮向回作反向試探。如果反向試探結(jié)果是也小于門限，說明當前門限太高需要降低門限，再作向前試探；如果反向試探結(jié)果大于門限，說明反向試探節(jié)點度量>門限>前向試探節(jié)點，因此應(yīng)考慮從反向試探節(jié)點另一個方向衍生一個試探節(jié)點，因此要回到反向試探節(jié)點，以便向前觀察下一個最佳節(jié)點。40第四十頁，共五十二頁，2022年，8月28日Fano算法先找一個最佳節(jié)點，大于門限，則前進并提高門限；再向前找一個最佳節(jié)點，大于門限，則前進并提高門限，再向前找一個最佳節(jié)點，小于門限。41第四十一頁，共五十二頁，2022年，8月28日

Fano算法42第四十二頁，共五十二頁，2022年，8月28日堆棧(ST)算法核心：存貯一組可能的路徑，但每次只對當時認為的最佳路徑進行延伸，然后再重新排序。從碼樹圖起始節(jié)點開始；將堆棧第一行中路徑向各分支延伸，計算新度量；刪去第一行原存貯內(nèi)容；將延伸后的各路徑在堆棧中重新排序，找出度量量大的路徑放在第一行；若第一行中的路徑已達碼樹終點，則結(jié)束，否則回到步驟2。43第四十三頁，共五十二頁，2022年，8月28日ST算法的本質(zhì)存貯一組可能路徑；每次只有最可能的（度量最大的）路徑可以繁衍，同時刪去父路徑；繁衍出的子路徑與其它未繁衍的路徑一起排序；堆棧滿時最壞路徑被丟棄。44第四十四頁，共五十二頁，2022年，8月28日序列譯碼的特點運算量與信道質(zhì)量有關(guān)；需要輸入緩沖器，其長度也與信道質(zhì)量有關(guān)，有溢出現(xiàn)象；計算量與約束長度無關(guān)。45第四十五頁，共五十二頁，2022年，8月28日TCMencoder46第四十六頁，共五十二頁，2022年，8月28日TCMForatrelliscodeC(oflengthn),theminimumsquaredEuclideandistancebetweentwodifferentsequencesofsignalpointsisreferredtoasitsfreesquaredEuclideandistance;i.e.,Theasymptoticcodinggain(includingshapinggain)isdefinedtobe

wheredenotetheminimumsquaredEuclideandistancebetweensignalpointsintheuncodedscheme,andEandE(u)denotetheaveragesignalenergiesofthecodedanduncodedschemes,respectively.

dB

47第四十七頁，共五十二頁，2022年，8月28日TCMexample

The4-stateTCMencoderfor8-PSK48第四十八頁，共五十二頁，2022年，8月28日Setpartitionof8PSK49第四十九頁，共五十二頁，2022年，8月28日Trellisdiagram