《信道編碼理論》PPT課件.ppt

《《信道編碼理論》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《信道編碼理論》PPT課件.ppt（52頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第十二章 卷積碼的概率譯碼 （I）,卷積碼的網(wǎng)格圖表示 卷積碼的概率譯碼：Viterbi譯碼算法 修正的Viterbi譯碼算法 滑窗 狀態(tài)縮減,2,卷積碼的Trellis圖表示,右圖為(2,1,2)卷積編碼示意圖，其生成多項(xiàng)式矩陣和生成矩陣分別為:,,,,3,卷積碼的Trellis圖表示,,,,s0,s1,s2,s3,s0,s1,s2,s3,狀態(tài)圖Trellis圖,4,Viterbi譯碼,若編碼信息序列為 1011100，則編碼過(guò)程即為在Trellis圖上尋找一條路徑。,,,,5,Viterbi譯碼,譯碼過(guò)程即為在Trellis圖上尋找一條路徑，該路徑對(duì)應(yīng)的編碼序列與接收序列之間有最大概率

2、度量：,6,Viterbi譯碼,從第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é)果。,7,Viterbi譯碼,在BSC和BIQO-DMC上，最大概率度量分別等效為最小Hammin

3、g距離度量和最小歐氏距離度量 。 距離度量更新公式 ： Theorem：在Viterbi譯碼算法中，留選路徑是有最大似然函數(shù)的路徑。,,,8,Viterbi譯碼,第1個(gè)時(shí)刻接收子碼10,漢明距離d,1,1,第2個(gè)時(shí)刻接收子碼10,漢明距離d,Example: M=(1011100)，初始狀態(tài)為全0的編碼器輸出序列為C=(11, 10, 00, 01, 10, 01, 11), 通過(guò)有噪信道后，接收序列為R=(10, 10, 00, 01, 11, 01, 11),,,1,1,9,Viterbi譯碼,第3個(gè)時(shí)刻接收子碼00,漢明距離d,,,2,1,3,2,10,Viterbi譯碼,第4個(gè)時(shí)刻接

4、收子碼01,漢明距離d,3,4,3,4,3,3,1,5,漢明距離d,3,3,3,1,,2,1,3,3,11,Viterbi譯碼,第5個(gè)時(shí)刻接收子碼11,漢明距離d,3,5,3,5,2,4,2,4,漢明距離d,3,3,2,2,,,3,3,1,3,12,Viterbi譯碼,第6個(gè)時(shí)刻接收子碼01,漢明距離d,3,4,2,5,漢明距離d,3,2,,,3,3,2,2,3,4,3,4,,,3,3,13,Viterbi譯碼,第7個(gè)時(shí)刻接收子碼11,漢明距離d,2,5,,,3,2,3,3,,,,,,,01/0,00/1,01/1,10/1,10/0,11/1,4,4,4,4,3,4,14,Viterbi譯碼

5、,保存的幸存路徑為：,譯碼結(jié)果為：1011100,,15,Viterbi譯碼收尾,最大似然序列譯碼要求序列有限，因此對(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。,16,Viterbi譯碼收尾,非系統(tǒng)非遞歸碼,遞歸系統(tǒng)碼,17,Viterbi譯碼,第6個(gè)時(shí)

6、刻接收子碼01,漢明距離d,3,4,2,5,漢明距離d,3,2,,3,3,2,2,Example (cont.): M=(10111); M=(1011100),18,Viterbi譯碼,第7個(gè)時(shí)刻接收子碼11,漢明距離d,2,5,19,Viterbi譯碼,保存的幸存路徑為：,譯碼結(jié)果為：1011100,,20,軟判決Viterbi譯碼,基本思想： 為了充分利用信道輸出符號(hào)的信息，提高譯碼可靠性，把信道輸出的信號(hào)進(jìn)行Q電平量化，然后在輸入Viterbi譯碼器。能適應(yīng)這種Q進(jìn)制輸入的Viterbi譯碼器稱為軟判決Viterbi譯碼器。 例子：Q=4電平量化的信道比特度量：,,,,,,,,,,,,

7、,,,0,01,02,1,12,11,21,Viterbi譯碼的復(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è)存貯單元。,22,Viterbi譯碼的特點(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)系。

8、,23,滑窗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í)刻前的同一路徑。,24,滑窗Viterbi算法實(shí)現(xiàn),在第t時(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ì)了。,

9、25,縮減狀態(tài)的Viterbi譯碼,由于運(yùn)算量與k和m呈指數(shù)關(guān)系，因此維特比譯碼算法一般只適合于k和m較小的場(chǎng)合。大多數(shù)情況下k=1，m<10。 對(duì)狀態(tài)數(shù)很大的卷積碼，維特比算法要經(jīng)一定的修正后才可能實(shí)用，常用的算法是縮減狀態(tài)的維特比譯碼，即在每一時(shí)刻，只處理部分的狀態(tài)。,26,第十二章 卷積碼的概率譯碼 （II）,序列譯碼 Fano譯碼算法 ST譯碼算法 調(diào)制與編碼的結(jié)合(TCM技術(shù)),27,序列譯碼,Viterbi譯碼算法存在的問(wèn)題: 對(duì)m值很大的情況不適用誤碼率很難做的很低; 譯每一個(gè)分支的計(jì)算量不變; Viterbi譯碼中路徑度量計(jì)算方法不適用于比較不同長(zhǎng)度的路徑，如: R =(

10、10,10,00,01,11,01,00) C5=(11,10,00,01,10,01) C0=(11) d(R0R5, C5)=2 d(R0, C0)=1 要求誤碼率很低，且譯碼器計(jì)算量可隨信道情況變化時(shí)，需采用序列譯碼: 一個(gè)簡(jiǎn)單的譯碼算法：逐分支譯碼。,28,逐分支譯碼舉例,編碼符號(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.

11、9 001: d =|-1-(-0.2)|+|1-(-0.3)|=2.1,29,逐分支譯碼的局限,沒(méi)有利用卷積碼的記憶性； 例：當(dāng)接收符號(hào)為：0.8, 0.7, -0.2, 0.1, 0.5, -0.3時(shí)，判信息序列為101。 但從整體序列來(lái)看，更像110 101110100: d = 0.2+0.3+ 0.8+0.9+1.5+0.7=4.4 110111010: d = 0.2+0.3+ 1.2+1.1+0.5+0.7=4.0 因此不是最大似然序列譯碼。,30,譯碼特性,一個(gè)好的譯碼算法，必須滿足以下幾點(diǎn)： 能以很大概率發(fā)現(xiàn)當(dāng)前走在錯(cuò)誤路徑上； 能以很大概率回到正確路徑； 運(yùn)算量和存貯量要適

12、中。 當(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ì)也呈線性變化，但斜率要高于正確路徑，約為n0/2。 R與C完全不相關(guān)。,31,譯碼特性,正確路徑、隨機(jī)路徑以及判決準(zhǔn)則:,32,譯碼特性,,斜距離: 由于信道干擾的原因，錯(cuò)誤路徑并不總是比正確路徑的度量低，但一般情況下沿錯(cuò)誤路徑走下去總會(huì)導(dǎo)致度量的下降。,33,局部錯(cuò)誤,不過(guò)由于卷積碼的記憶有限，可能會(huì)出現(xiàn)一條錯(cuò)誤路徑最終與正確路徑會(huì)合的情況，這樣就會(huì)出現(xiàn)一段局部錯(cuò)誤。,,誤碼,兩條

13、路徑在此有相同狀態(tài),34,錯(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)整判斷門限。,35,Fano度量,最大似然譯碼： 接收序列： 碼字序列： ML判決序列： 對(duì)離散無(wú)記憶信道：,36,Fano度量,Bayesian公式： 若發(fā)送序列先驗(yàn)等概，即 另外

14、 ，則有,37,Fano度量,對(duì)數(shù)似然值： Fano度量： Fano譯碼： 用Fano度量代替斜距離：,,38,Fano度量,例子： R=(10,10,00,01,11,01,00), C5=(11,10,00,01,10,01), C0=(11)，信道轉(zhuǎn)移概率為p=0.1，求 和,39,Fano算法,在向前試探時(shí)，如果發(fā)現(xiàn)度量值大于當(dāng)前門限，則向前移動(dòng)到所試探的節(jié)點(diǎn)；如果這次試探是第一次，則可將門限作一定的提高；如果不是第一次，說(shuō)明曾因門限太高而倒退過(guò)，因此不提高門限，以便后面的比較。,40,Fano算法,向前試探時(shí)，如果發(fā)現(xiàn)度量小于當(dāng)前門限，說(shuō)明比試探節(jié)點(diǎn)還要壞的節(jié)點(diǎn)度量更不可能超

15、過(guò)門限，因此在此節(jié)點(diǎn)上不必再向前試探下去，而應(yīng)考慮向回作反向試探。如果反向試探結(jié)果是也小于門限，說(shuō)明當(dāng)前門限太高需要降低門限，再作向前試探；如果反向試探結(jié)果大于門限，說(shuō)明反向試探節(jié)點(diǎn)度量門限前向試探節(jié)點(diǎn)，因此應(yīng)考慮從反向試探節(jié)點(diǎn)另一個(gè)方向衍生一個(gè)試探節(jié)點(diǎn)，因此要回到反向試探節(jié)點(diǎn)，以便向前觀察下一個(gè)最佳節(jié)點(diǎn)。,41,Fano算法,,,,,,,,,,,,,,,,,,,,,,,,,,,先找一個(gè)最佳節(jié)點(diǎn)，大于門限，則前進(jìn)并提高門限；再向前找一個(gè)最佳節(jié)點(diǎn)，大于門限，則前進(jìn)并提高門限，再向前找一個(gè)最佳節(jié)點(diǎn)，小于門限。,42,Fano算法,43,堆棧(ST)算法,核心：存貯一組可能的路徑，但每次只對(duì)當(dāng)時(shí)認(rèn)為

16、的最佳路徑進(jìn)行延伸，然后再重新排序。 從碼樹(shù)圖起始節(jié)點(diǎn)開(kāi)始； 將堆棧第一行中路徑向各分支延伸，計(jì)算新度量； 刪去第一行原存貯內(nèi)容； 將延伸后的各路徑在堆棧中重新排序，找出度量量大的路徑放在第一行； 若第一行中的路徑已達(dá)碼樹(shù)終點(diǎn)，則結(jié)束，否則回到步驟2。,44,ST算法的本質(zhì),存貯一組可能路徑； 每次只有最可能的（度量最大的）路徑可以繁衍，同時(shí)刪去父路徑； 繁衍出的子路徑與其它未繁衍的路徑一起排序； 堆棧滿時(shí)最壞路徑被丟棄。,45,序列譯碼的特點(diǎn),運(yùn)算量與信道質(zhì)量有關(guān)； 需要輸入緩沖器，其長(zhǎng)度也與信道質(zhì)量有關(guān)，有溢出現(xiàn)象； 計(jì)算量與約束長(zhǎng)度無(wú)關(guān)。,46,TCM encoder,,47,TCM,F

17、or a trellis code C (of length n), the minimum squared Euclidean distance between two different sequences of signal points is referred to as its free squared Euclidean distance; i.e., The asymptotic coding gain (including shaping gain) is defined to be where denote the minimum squared Euclidean dis

18、tance between signal points in the uncoded scheme, and E and E(u) denote the average signal energies of the coded and uncoded schemes, respectively.,,,,dB,,,48,TCM example,The 4-state TCM encoder for 8-PSK,,49,Set partition of 8PSK,,50,Trellis diagram,,The error event corresponding to,51,Coding gain

19、,The intra-subset minimum squared Euclidean distance is given by In this example, the parallel transitions are associated with signals from one of the four subsets, C(00), C(01), C(10), C(11), with minimum squared Euclidean distance In this example, the minimum squared Euclidean distance between any

20、 two different sequences of subsets,,,,52,Coding gain,Thus, the free squared Euclidean distance of this TCM code is Compared with an uncoded QPSK scheme with the minimum squared Euclidean distance 2Es between signal points, this TCM scheme can provide an asymptotic coding gain of,,,,(dB),,,,,QPSK constellation,