1、第九講,卷積碼的維特比譯碼及卷積碼性能分析,回顧,卷積碼的編碼：有記憶的信道編碼 卷積碼的概率譯碼 序列譯碼：費(fèi)諾算法和堆棧算法 最大似然譯碼：維特比算法,維特比譯碼的描述,從第1時(shí)刻的全零狀態(tài)開始（零狀態(tài)初始度量為0，其它狀態(tài)初始度量為負(fù)無窮） 在任一時(shí)刻t，對(duì)每一個(gè)狀態(tài)只記錄到達(dá)路徑中度量最大的一個(gè)（殘留路徑）及其度量（狀態(tài)度量） 在向t+1時(shí)刻前進(jìn)過程中，對(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é)果

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

3、為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è)存貯單元。,維特比譯碼的特點(diǎn),維特比算法是最大似然的序列譯碼算法 譯碼復(fù)雜度與信道質(zhì)量無關(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)系,吞吐量與存儲(chǔ)量,運(yùn)算量與碼長(zhǎng)呈線性關(guān)系意味著平均吞吐量與碼長(zhǎng)無關(guān) 存貯量與碼長(zhǎng)呈線性關(guān)系意味著對(duì)無限碼長(zhǎng)（流的情況）要求有無限的存貯量。,滑動(dòng)窗維特比譯碼算法,基本

4、思想：當(dāng)狀態(tài)數(shù)有限時(shí)，給定時(shí)刻的各狀態(tài)殘留路徑在一定時(shí)間（L）之前來自于同一狀態(tài)的可能性隨L的增加而迅速趨近于1。因此當(dāng)前時(shí)刻各殘留路徑很可能來自于L時(shí)刻前的同一路徑。,滑動(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ì)了。,狀態(tài)數(shù)對(duì)維特比譯碼的影響

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

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

7、全0時(shí)輸出也是全0，構(gòu)成一條全0序列，這是一個(gè)合法的編碼序列。因此研究誤碼可以假設(shè)發(fā)的是全0序列，而研究譯成非0序列的概率。為此我們要研究卷積碼的距離譜或重量譜。,線性卷積碼的首次錯(cuò)誤事件,在研究首次錯(cuò)誤事件概率時(shí)，要研究的是第一次與全0序列分離并再次回到全0序列的事件。它等價(jià)于在網(wǎng)格圖上第一次離開狀態(tài)0并再次回到狀態(tài)0的路徑。 由于這些事件要離開狀態(tài)0，而再次回到狀態(tài)0后就不允許離開狀態(tài)0，因此狀態(tài)0要分解成兩個(gè)狀態(tài)：0和0，其中0為注入態(tài)，而0為吸收態(tài)。我們要研究的就是從注入到吸收所有可能的路徑，及它們的各種特性，如長(zhǎng)度、輸入重量、輸出重量等等。,重量表示,由于路徑每走一步，長(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)加起來，合并同類項(xiàng)，就可以得到下面的式子： F(N,S,D)=i,j,kA(i,j,k) NiSjDk,F(N,S,D)的含義,它表示，在所有可能路徑中，長(zhǎng)度是i個(gè)時(shí)刻，輸入重量為j，輸出重量為k的路徑共有A(i,j,k)條。 這個(gè)式子包含了有關(guān)卷積碼性能的大量信息，可以從它得到誤比特率、誤事件率及誤幀率的性能界