第九講——卷積碼維特比譯碼和卷積碼性能分析

1、第九講卷積碼的維特比譯碼及卷積碼性能分析1回顧卷積碼的編碼：有記憶的信道編碼卷積碼的概率譯碼序列譯碼：費(fèi)諾算法和堆棧算法最大似然譯碼：維特比算法2維特比譯碼的描述從第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ǔ)上加上分支度量，得到M*2k條路徑對(duì)所得到的t+1時(shí)刻到達(dá)每一個(gè)狀態(tài)的2k條路徑進(jìn)行比較，找到一個(gè)度量最大的作為殘留路徑直到碼的終點(diǎn)，如果確定終點(diǎn)是一個(gè)確定狀態(tài)，則最終保留的路徑就是譯碼結(jié)果3圖解維特比譯碼4維

2、特比譯碼收尾最大似然序列譯碼要求序列有限，因此對(duì)卷積碼來(lái)說(shuō)，要求能收尾。收尾的原則：在信息序列輸入完成后，利用輸入一些特定的比特，使M個(gè)狀態(tài)的各殘留路徑可以到達(dá)某一已知狀態(tài)（一般是全零狀態(tài)）。這樣就變成只有一條殘留路徑，這就是最大似然序列。5卷積碼收尾的實(shí)現(xiàn)非遞歸卷積碼：約束長(zhǎng)度為m+1的卷積碼，只要在信息序列輸入完成后連續(xù)送入m個(gè)0，即可使任一路徑都到達(dá)最終的狀態(tài)0。遞歸卷積碼：也可通過(guò)將輸入值置成反饋值的負(fù)值，而使m個(gè)時(shí)鐘后的狀態(tài)到達(dá)0。6卷積碼收尾非系統(tǒng)非遞歸碼 遞歸系統(tǒng)碼7維特比譯碼的復(fù)雜度對(duì)信息序列長(zhǎng)度為L(zhǎng)，信息符號(hào)取自GF(p)，R=k/n，約束長(zhǎng)度為m+1的卷積碼。狀態(tài)數(shù)為pkm

3、，因此對(duì)每個(gè)時(shí)刻要做pkm次加比選得到pkm個(gè)狀態(tài)的殘留路徑，每次加比選包括pk次加法和pk-1次比較。因此總運(yùn)算量約為L(zhǎng)pkm次加比選。同時(shí)要能保存pkm條殘留路徑，因此需要Lpkm個(gè)存貯單元。8維特比譯碼的特點(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)系9吞吐量與存儲(chǔ)量運(yùn)算量與碼長(zhǎng)呈線性關(guān)系意味著平均吞吐量與碼長(zhǎng)無(wú)關(guān)存貯量與碼長(zhǎng)呈線性關(guān)系意味著對(duì)無(wú)限碼長(zhǎng)（流的情況）要求有無(wú)限的存貯量。10滑動(dòng)窗維特比譯碼算法基本思想：當(dāng)狀態(tài)數(shù)有限時(shí)，給定時(shí)刻的各狀態(tài)殘留路徑在

4、一定時(shí)間（L）之前來(lái)自于同一狀態(tài)的可能性隨L的增加而迅速趨近于1。因此當(dāng)前時(shí)刻各殘留路徑很可能來(lái)自于L時(shí)刻前的同一路徑。11滑動(dòng)窗維特比譯碼算法實(shí)現(xiàn)在第k時(shí)刻，可以將t-L時(shí)刻前的路徑結(jié)果直接輸出，而在存貯空間中不再保存t-L時(shí)刻前的內(nèi)容。因此存貯量控制在Lpkm。這里的L就被稱做譯碼深度。不再隨碼長(zhǎng)的增加而增加。因而特別適合信息流的卷積碼編譯碼。在這種情況下甚至不需要對(duì)流分段加尾比特。這里的L就被稱做譯碼深度。顯然，滑動(dòng)窗算法是一種準(zhǔn)最優(yōu)算法。但通常譯碼深度只要有編碼約束長(zhǎng)度的5到10倍，其性能損失就可以忽略不計(jì)了。12狀態(tài)數(shù)對(duì)維特比譯碼的影響由于運(yùn)算量與k和m呈指數(shù)關(guān)系，因此維特比譯碼算法

5、一般只適合于k和m較小的場(chǎng)合。大多數(shù)情況下k=1，m10。對(duì)狀態(tài)數(shù)很大的卷積碼，維特比算法要經(jīng)一定的修正后才可能實(shí)用，常用的算法是縮減狀態(tài)的維特比譯碼，即在每一時(shí)刻，只處理部分的狀態(tài)。13序列譯碼與維特比譯碼的比較信道質(zhì)量對(duì)前者運(yùn)算量影響較大，而對(duì)后者運(yùn)算量沒(méi)有影響前者是次優(yōu)的，后者是最優(yōu)的前者運(yùn)算量與約束長(zhǎng)度無(wú)關(guān)，而后者運(yùn)算量與約束長(zhǎng)度呈指數(shù)關(guān)系前者會(huì)有譯碼失敗，而后者只有譯碼錯(cuò)誤在不同場(chǎng)合有不同用途14卷積碼的性能分析誤碼分析重量或距離譜首次差錯(cuò)率15兩個(gè)序列間差異的擴(kuò)大對(duì)于有限狀態(tài)的流編碼傳輸而言，如果兩個(gè)序列不起始于同一狀態(tài)且終于同一狀態(tài)，則可以通過(guò)網(wǎng)格圖的繼續(xù)延伸而呈現(xiàn)出更大的差別。

6、而只有有限的差別才有可能造成誤判。因此對(duì)卷積碼而言，我們關(guān)心的是某一時(shí)刻兩條路徑分離，而在有限時(shí)間內(nèi)又再次合并的情形。這就是流編碼中的一次錯(cuò)誤事件。16首次錯(cuò)誤事件顯然，兩條路徑分離后一般并不會(huì)立即合并，而是要經(jīng)過(guò)一段時(shí)間后才可能合并，這段時(shí)間可長(zhǎng)可短，是隨機(jī)的。因此卷積碼中出現(xiàn)的誤碼一般也有較強(qiáng)的突發(fā)性，一般突發(fā)長(zhǎng)度不小于約束長(zhǎng)度。對(duì)半無(wú)限的卷積碼而言，總是開(kāi)始于狀態(tài)0，我們要研究的就是什么時(shí)候會(huì)發(fā)生第一次錯(cuò)誤事件？這一次錯(cuò)誤事件的長(zhǎng)度是多少？它引起了多少比特錯(cuò)誤？錯(cuò)誤概率如何？等等。17對(duì)于線性卷積碼對(duì)線性卷積碼而言，輸入全0時(shí)輸出也是全0，構(gòu)成一條全0序列，這是一個(gè)合法的編碼序列。因此研

7、究誤碼可以假設(shè)發(fā)的是全0序列，而研究譯成非0序列的概率。為此我們要研究卷積碼的距離譜或重量譜。18線性卷積碼的首次錯(cuò)誤事件在研究首次錯(cuò)誤事件概率時(shí)，要研究的是第一次與全0序列分離并再次回到全0序列的事件。它等價(jià)于在網(wǎng)格圖上第一次離開(kāi)狀態(tài)0并再次回到狀態(tài)0的路徑。由于這些事件要離開(kāi)狀態(tài)0，而再次回到狀態(tài)0后就不允許離開(kāi)狀態(tài)0，因此狀態(tài)0要分解成兩個(gè)狀態(tài)：0和0，其中0為注入態(tài)，而0為吸收態(tài)。我們要研究的就是從注入到吸收所有可能的路徑，及它們的各種特性，如長(zhǎng)度、輸入重量、輸出重量等等。19重量表示由于路徑每走一步，長(zhǎng)度、輸入重量、輸出重量等參數(shù)都要隨各自的分支而進(jìn)行累加，因此如果將這些參數(shù)在每個(gè)分支上的值用指數(shù)標(biāo)注，則可以用乘積的方式表示一條路徑的各項(xiàng)值。例如，一條路徑的乘積項(xiàng)為NiSjDk，表示該路徑長(zhǎng)度是i個(gè)時(shí)刻，輸入重量為j，輸出重量為k。當(dāng)將所有可能路徑的乘積項(xiàng)加起來(lái)，合并同類項(xiàng)，就可以得到下面的式子：F(N,S,D)=i,j,kA(i,j,k) NiSjDk20F(N,S,D)的含義它表示，在所有可能路徑中，長(zhǎng)度是i個(gè)時(shí)刻，輸入重量為j，輸出重量為k的路徑共有A(i,j,k)條。這個(gè)式子包含了有關(guān)卷積碼性能的大量信息，可以從