第八講——卷積碼的譯碼

1、第八講卷積碼的譯碼1回顧卷積碼是對(duì)信息流進(jìn)行編碼的一種有記憶分組的編碼方法記憶有很多種，典型的為線性有限記憶和線性無(wú)限記憶當(dāng)記憶為線性時(shí)，等效于輸入信息流與沖激響應(yīng)之間的卷積可分別用FIR和IIR濾波器來(lái)描述矩陣描述、樹圖描述和網(wǎng)格圖表示2卷積碼的概率譯碼概率譯碼：結(jié)合信道符號(hào)統(tǒng)計(jì)特性的譯碼方法一種簡(jiǎn)單的譯碼方法：逐分支譯碼在碼樹圖中每向前走一步，在決定走哪一個(gè)分支時(shí)根據(jù)該分支子碼與該時(shí)刻接收子碼之間的相似程度來(lái)判斷3逐分支譯碼舉例編碼符號(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”

2、，因此判信息序列為1104逐分支譯碼的局限沒有利用卷積碼的記憶性例：當(dāng)接收符號(hào)為：0.8, 0.7, -0.2, 0.1, 0.5, -0.3時(shí)，判信息序列為101但從整體序列來(lái)看，更像110因此不是最大似然序列譯碼5譯碼準(zhǔn)則：對(duì)數(shù)似然度量log P(R|C)=logiP(ri|ci)=ilog(p(ri|ci)當(dāng)在碼樹中沿正確路徑行進(jìn)時(shí)，對(duì)數(shù)度量的整體趨勢(shì)呈線性變化。當(dāng)在碼樹中沿完全錯(cuò)誤（隨機(jī)）路徑行進(jìn)時(shí)，對(duì)數(shù)度量的整體趨勢(shì)也呈線性變化，但斜率要低于正確路徑。6對(duì)數(shù)似然度量圖示正確路徑與隨機(jī)路徑7正確路徑與錯(cuò)誤路徑由于信道干擾的原因，錯(cuò)誤路徑并不總是比正確路徑的度量低，但一般情況下沿錯(cuò)誤路徑

3、走下去總會(huì)導(dǎo)致度量的下降8局部錯(cuò)誤不過由于卷積碼的記憶有限，可能會(huì)出現(xiàn)一條錯(cuò)誤路徑最終與正確路徑會(huì)合的情況，這樣就會(huì)出現(xiàn)一段局部錯(cuò)誤9譯碼錯(cuò)誤當(dāng)由于度量的起伏造成將局部錯(cuò)誤的路徑看成正確路徑時(shí)，就發(fā)生誤碼。10對(duì)譯碼算法的要求能以很大概率發(fā)現(xiàn)當(dāng)前走在錯(cuò)誤路徑上能以很大概率回到正確路徑運(yùn)算量和存貯量要適中11費(fèi)諾度量為便于譯碼，要求正確路徑的度量變化斜率大于0，而錯(cuò)誤路徑的度量變化斜率要小于0，因此要對(duì)分支度量加以調(diào)整同樣也是為了不同長(zhǎng)度的路徑能進(jìn)行比較費(fèi)諾度量：二進(jìn)制輸入的DMC信道：log2(p(ri|ci)/p(ri)-Rc 12局部錯(cuò)誤與判斷門限對(duì)卷積碼來(lái)說(shuō)，一般比較容易出現(xiàn)的錯(cuò)誤都是較

4、小的碼距，而較小碼距的差錯(cuò)圖案一般都是集中在一些序列段中，即由一些局部錯(cuò)誤組成。序列譯碼就是要盡早發(fā)現(xiàn)這些局部錯(cuò)誤，因?yàn)檫^了這些局部錯(cuò)誤之后兩個(gè)序列的內(nèi)容就相同了，因此后面的斜率也是相同的。局部錯(cuò)誤在路徑度量變化中的體現(xiàn)應(yīng)是一段下垂后繼續(xù)按正確斜率上升。因此要隨時(shí)調(diào)整判斷門限。13費(fèi)諾算法14費(fèi)諾算法的幾種情形在向前試探時(shí)，如果發(fā)現(xiàn)度量值大于當(dāng)前門限，則向前移動(dòng)到所試探的節(jié)點(diǎn)；如果這次試探是第一次，則可將門限作一定的提高；如果不是第一次，說(shuō)明曾因門限太高而倒退過，因此不提高門限，以便后面的比較15費(fèi)諾算法的另一些情形向前試探時(shí)，如果發(fā)現(xiàn)度量小于當(dāng)前門限，說(shuō)明比試探節(jié)點(diǎn)還要壞的節(jié)點(diǎn)度量更不可能超

5、過門限，因此在此節(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)。16堆棧算法核心：存貯一組可能的路徑，但每次只對(duì)當(dāng)時(shí)認(rèn)為的最佳路徑進(jìn)行延伸，然后再重新排序。從碼樹圖起始節(jié)點(diǎn)開始將堆棧第一行中路徑向各分支延伸，計(jì)算新度量刪去第一行原存貯內(nèi)容將延伸后的各路徑在堆棧中重新排序，找出度量量大的路徑放在第一行若第一行中的路徑已達(dá)碼樹終點(diǎn)，則結(jié)束，否則回到步驟217

6、堆棧算法的本質(zhì)存貯一組可能路徑每次只有最可能的（度量最大的）路徑可以繁衍，同時(shí)刪去父路徑繁衍出的子路徑與其它未繁衍的路徑一起排序堆棧滿時(shí)最壞路徑被丟棄18序列譯碼的特點(diǎn)運(yùn)算量與信道質(zhì)量有關(guān)需要輸入緩沖器，其長(zhǎng)度也與信道質(zhì)量有關(guān)，有溢出現(xiàn)象計(jì)算量與約束長(zhǎng)度無(wú)關(guān)19維特比譯碼卷積碼的網(wǎng)格圖描述：將狀態(tài)轉(zhuǎn)移圖按時(shí)間展開，用于描述從第k時(shí)刻的編碼器狀態(tài)到第k+1時(shí)刻的編碼狀態(tài)的轉(zhuǎn)移情況，以及在轉(zhuǎn)移過程中的輸出情況。20有限狀態(tài)編碼的最大似然譯碼當(dāng)編碼器的狀態(tài)數(shù)有限時(shí)，不同編碼路徑必然會(huì)有會(huì)合的情況。例：一個(gè)信息長(zhǎng)度為L(zhǎng)的編碼，所有可能路徑數(shù)為2L個(gè)，而對(duì)于一個(gè)4狀態(tài)碼而言，任一時(shí)刻路徑只能經(jīng)過4個(gè)狀態(tài)，因此大量的路徑（當(dāng)用狀態(tài)轉(zhuǎn)移來(lái)描述時(shí)）是有重合的。由于碼的馬氏特性，從某一時(shí)刻開始的后續(xù)編碼只與該時(shí)刻的狀態(tài)有關(guān)，而與之前如何到達(dá)該狀態(tài)無(wú)關(guān)。21分段譯碼與殘留路徑一個(gè)長(zhǎng)度為L(zhǎng)的碼，在時(shí)刻k分為兩段，之前的稱為A，之后的稱為B。最大似然序列必存在于從k時(shí)刻的M個(gè)狀態(tài)出發(fā)（或在時(shí)刻k經(jīng)過M個(gè)狀態(tài)的）的M*2L-k條路徑之中。而第k時(shí)刻到達(dá)每個(gè)狀態(tài)都有2k/M條A路徑，顯然，從第k時(shí)刻狀態(tài)S出發(fā)的最佳路徑的前半段必然是到達(dá)該狀態(tài)的2k/M條A路徑中的最佳A路徑。稱此最佳A路徑為第k時(shí)刻狀態(tài)S的殘留路徑。22推廣到每時(shí)刻一段因此在任