維特比譯碼介紹

1,TheViterbiAlgorithm,劉超liuchao杭州電子科技大學(xué)通信學(xué)院網(wǎng)絡(luò)通信教研室,2020/5/6,2,教學(xué)內(nèi)容：卷積碼的簡(jiǎn)要介紹維特比譯碼的基本原理維特比譯碼的基本過(guò)程教學(xué)目標(biāo)掌握維特比譯碼的基本原理熟悉用柵格描述維特比譯碼的過(guò)程,教學(xué)內(nèi)容與目標(biāo),2020/5/6,3,卷積碼編碼器,卷積碼編碼器結(jié)構(gòu)框圖,k=2,輸出,1,2,3,4,編碼器相關(guān)術(shù)語(yǔ)(m,k,n)碼，約束長(zhǎng)度m，每次移位的比特k，碼速率Rc=k/n狀態(tài)S=(4321)，共2km種狀態(tài),m=2,輸入,1,2,3,n=3,2020/5/6,4,例1(2,1,2)碼的狀態(tài)向量為S=(21)，共有4種狀態(tài)S0=(0,0),S1=(0,1),S2=(1,0),S3=(1,1)，如圖所示。,卷積碼的狀態(tài)轉(zhuǎn)移圖與數(shù)學(xué)方程,2020/5/6,5,該碼的狀態(tài)轉(zhuǎn)移方程和輸出方程分別為1=U2=1V1=U+1+2V2=U+2,卷積碼的相關(guān)數(shù)學(xué)方程,2020/5/6,6,卷積碼的狀態(tài)轉(zhuǎn)移圖,編碼器及其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移圖如下,2020/5/6,7,卷積碼的狀態(tài)轉(zhuǎn)移圖,2020/5/6,8,卷積碼的柵格圖(籬笆圖)狀態(tài)圖不能反映出狀態(tài)轉(zhuǎn)移與時(shí)間的關(guān)系柵格圖/籬笆圖：將開放型的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序級(jí)聯(lián)形成一個(gè)柵格圖。編碼路徑：狀態(tài)序列在柵格圖中形成的一條有向路徑。當(dāng)有向路徑始于全“0”狀態(tài)S0，又終于S0時(shí)，表明此時(shí)編碼器又回到全“0”狀態(tài)，,卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述,2020/5/6,9,紅實(shí)線表示U=0時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支;黃虛線表示U=1時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支;轉(zhuǎn)移分支上數(shù)字表示輸出的編碼比特V1和V2。,卷積碼的狀態(tài)轉(zhuǎn)移的柵格描述,2020/5/6,10,卷積碼的柵格描述,2020/5/6,11,最大似然譯碼/最小距離譯碼,待編碼的信息序列M：M=M0,M1,ML1；編碼器輸入序列的總長(zhǎng)度：k(L+m)；編碼器輸出的碼序列C：C=C0,C1,CL1，其中每個(gè)子碼Ci含有n個(gè)比特；經(jīng)離散無(wú)記憶信道(DMC)傳輸后，譯碼器接收的序列R：R=R0,R1,RL1；對(duì)于DMC信道：碼序列C的路徑度量M(R/C)：計(jì)算第l時(shí)刻到達(dá)狀態(tài)i的最大似然路徑的相似度logp(R/C)；子碼Ci度量M(Ri/Ci)：計(jì)算第l時(shí)刻接收子碼Ri相對(duì)于各碼字的相似度logp(Ri/Ci)，也稱為分支度量。,2020/5/6,12,最大似然譯碼/最小距離譯碼,譯碼器接收到R序列后，按最大似然法則力圖尋找編碼器在籬笆圖上原來(lái)走過(guò)的路徑，也就是尋找具有最大度量的路徑；對(duì)BSC信道，就是尋找與R有最小漢明距離的路徑，即計(jì)算和尋找mind(R,Cj)，j=1,2,2Lk。注：二進(jìn)制對(duì)稱信道BSC（BinarySymmetryChannel）,2020/5/6,13,最大似然譯碼/最小距離譯碼,最大似然譯碼方法只是提供了一個(gè)譯碼準(zhǔn)則，實(shí)現(xiàn)起來(lái)尚有一定困難。因?yàn)樗强紤]了長(zhǎng)度為(L+m)n的接收序列來(lái)譯碼的，這樣的序列可能有2Lk條；若實(shí)際接收序列中，L=50，k=2，則可能的路徑有2100條。譯碼器每接收一個(gè)序列R，就要計(jì)算1030個(gè)似然函數(shù)才能做出譯碼判決。若kL再大一些，譯碼器按最大似然譯碼準(zhǔn)則譯碼將是很困難的。,2020/5/6,14,維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計(jì)算和比較2Lk條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想：將接收序列R與籬笆圖上的路徑逐分支地比較，比較的長(zhǎng)度一般取(56)mn，然后留下與R距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長(zhǎng)并存儲(chǔ)起來(lái)。幸存路徑的數(shù)目等于狀態(tài)數(shù)：2km以(2,1,2)卷積碼為例說(shuō)明維特比譯碼的一般過(guò)程：設(shè)發(fā)送序列C為全0；接收序列R=10,00,01,00,00,00,00,維特比譯碼的基本原理,2020/5/6,15,假設(shè)譯碼器的初始狀態(tài)為全0；第0個(gè)時(shí)刻：接收序列的第0個(gè)分支R0=10進(jìn)入譯碼器。從S0狀態(tài)有兩個(gè)分支，它們是00和11，R0與這兩個(gè)分支比較，比較的結(jié)果和到達(dá)的狀態(tài)如表1所示：每個(gè)狀態(tài)/節(jié)點(diǎn)都有兩個(gè)存儲(chǔ)器：路徑存儲(chǔ)器：存儲(chǔ)該狀態(tài)的部分路徑；路徑值存儲(chǔ)器：存儲(chǔ)達(dá)到該狀態(tài)的部分路徑值(累加距離)。,維特比譯碼的基本原理,接收序列R=10,00,01,00,00,00,00,2020/5/6,16,第一個(gè)時(shí)刻：進(jìn)入譯碼器的接收碼組R1=00和此時(shí)刻出發(fā)的四條分支比較，比較結(jié)果和達(dá)到狀態(tài)如表2所示：從第一個(gè)時(shí)刻到第二個(gè)時(shí)刻：共有四條路徑，到達(dá)S0,S1,S2和S3。在第二個(gè)時(shí)刻以前譯碼器不做任何選擇和判決。每個(gè)狀態(tài)的路徑存儲(chǔ)器存儲(chǔ)下此時(shí)刻的幸存路徑：0000,0011,1110,1101；每個(gè)狀態(tài)的路徑值存儲(chǔ)器存儲(chǔ)了此時(shí)刻到達(dá)該狀態(tài)的幸存路徑累加值(累加距離)。,維特比譯碼的基本原理,接收序列R=10,00,01,00,00,00,00,2020/5/6,17,維特比譯碼的基本原理,2020/5/6,18,從第二個(gè)時(shí)刻起：第二個(gè)接收碼組R2=01進(jìn)入譯碼器，從籬笆圖上可見，從第二個(gè)時(shí)刻到第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的分支有兩個(gè)（或者說(shuō)在第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的路徑有兩條）。譯碼器將接收碼組R2與進(jìn)入每個(gè)狀態(tài)的兩個(gè)分支進(jìn)行比較和判決，選擇一個(gè)累加距離（部分路徑值）最小的路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條，比較和判決的過(guò)程如下：,維特比譯碼的基本原理,接收序列R=10,00,01,00,00,00,00,2020/5/6,19,經(jīng)過(guò)比較后選擇：部分路徑000000為到達(dá)S0狀態(tài)的幸存路徑；部分路徑000011為到達(dá)S1狀態(tài)的幸存路徑；部分路徑110101為到達(dá)S2狀態(tài)的幸存路徑；部分路徑001101為到達(dá)S3狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個(gè)時(shí)刻進(jìn)入一個(gè)碼組，沿著籬笆圖對(duì)每個(gè)狀態(tài)按部分路徑值（累加距離）的大小，選擇一條幸存路徑。在每個(gè)狀態(tài)上進(jìn)行判決時(shí)，可能出現(xiàn)進(jìn)入這一狀態(tài)的兩條路徑的距離值相同，這時(shí)可以任選其一，因?yàn)閷?duì)以后的判決而言，無(wú)論選擇那一條路徑，累加距離是相同的。,維特比譯碼的基本原理,2020/5/6,20,對(duì)本例而言，按上述算法進(jìn)行到第十一個(gè)分支后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達(dá)到較低的錯(cuò)誤概率。一般，約為(56)mn，所以，維特比譯碼的延時(shí)可達(dá)(56)m個(gè)單位時(shí)刻（每個(gè)單位時(shí)刻為n個(gè)碼元長(zhǎng)度）就可以對(duì)第0個(gè)接收碼組的信息元進(jìn)行判決。依此類推，對(duì)接收序列中的諸碼組進(jìn)行譯碼。維特比譯碼的一次運(yùn)算：計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑?；h笆圖中共有2km個(gè)狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存儲(chǔ)m成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷積碼，其m不能選的太大。,維特比譯碼的基本原理,2020/5/6,21,維特比譯碼的基本原理,2020/5/6,22,維特比譯碼的基本原理,2020/5/6,23,維特比譯碼的基本原理,2020/5/6,24,維特比譯碼的基本原理,2020/5/6,25,維特比譯碼的基本原理,2020/5/6,26,總結(jié)維特比算法的步驟在第j(j=m)個(gè)時(shí)刻以前，譯碼器計(jì)算所有的長(zhǎng)為m個(gè)分支的部分路徑值，對(duì)進(jìn)入2km個(gè)狀態(tài)的每一條部分路徑都保留。第m個(gè)時(shí)刻開始，對(duì)進(jìn)入每一個(gè)狀態(tài)的部分路徑進(jìn)行計(jì)算，這樣的路徑有2k條，挑選具有最大部分路徑值的部分路徑為幸存路徑，刪去進(jìn)入該狀態(tài)的其它路徑，然后，幸存路徑向前延長(zhǎng)一個(gè)分支。重復(fù)第二步的計(jì)算、比較和判決過(guò)程。若輸入接收序列長(zhǎng)為(L+m)k，其中，后m段是人為加入的全0段，則譯碼一直進(jìn)行到(L+m)個(gè)時(shí)刻為止。若進(jìn)入某個(gè)狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可任選其一作為幸存路徑。,維特比譯碼的基本原理,2020/5/6,27,硬判決譯碼器：以最小距離為度量的譯碼器。它適用于BSC信道。軟判決譯碼器：把信道解調(diào)器輸出的信號(hào)進(jìn)行Q電平量化，其中Q2，然后再輸入到維特比譯碼器進(jìn)行譯碼。充分利用了信道輸出信號(hào)的有關(guān)信息，提高譯碼的可靠性。它適用于DMC信道。軟判決譯碼器比硬判決譯碼器可以改進(jìn)碼的性能。在一