維特比譯碼介紹

1、1The Viterbi Algorithm劉超杭州電子科技大學(xué)通信學(xué)院網(wǎng)絡(luò)通信教研室杭州電子科技大學(xué)通信學(xué)院劉超2教學(xué)內(nèi)容：卷積碼的簡(jiǎn)要介紹維特比譯碼的基本原理維特比譯碼的基本過程教學(xué)目標(biāo)掌握維特比譯碼的基本原理熟悉用柵格描述維特比譯碼的過程教學(xué)內(nèi)容與目標(biāo)杭州電子科技大學(xué)通信學(xué)院劉超3卷積碼編碼器卷積碼編碼器結(jié)構(gòu)框圖k=2輸出輸出1234編碼器相關(guān)術(shù)語(yǔ)(m,k,n)碼，約束長(zhǎng)度m，每次移位的比特k，碼速率Rc=k/n 狀態(tài)S=(4 3 2 1)，共2km種狀態(tài)m=2輸入輸入123n=3杭州電子科技大學(xué)通信學(xué)院劉超4例例1 (2,1,2)碼的狀態(tài)向量為碼的狀態(tài)向量為S=(21)，共有，共有4種

2、狀態(tài)種狀態(tài)S0=(0,0),S1=(0,1),S2=(1,0),S3=(1,1)，如圖所示。，如圖所示。卷積碼的狀態(tài)轉(zhuǎn)移圖與數(shù)學(xué)方程杭州電子科技大學(xué)通信學(xué)院劉超5該碼的狀態(tài)轉(zhuǎn)移方程和輸出方程分別為該碼的狀態(tài)轉(zhuǎn)移方程和輸出方程分別為 1=U U 2=1 V V1=UU +1+2 V V2=UU +2 卷積碼的相關(guān)數(shù)學(xué)方程杭州電子科技大學(xué)通信學(xué)院劉超6卷積碼的狀態(tài)轉(zhuǎn)移圖編碼器及其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移圖如下編碼器及其對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移圖如下杭州電子科技大學(xué)通信學(xué)院劉超7卷積碼的狀態(tài)轉(zhuǎn)移圖杭州電子科技大學(xué)通信學(xué)院劉超8卷積碼的柵格圖卷積碼的柵格圖(籬笆圖籬笆圖)狀態(tài)圖不能反映出狀態(tài)轉(zhuǎn)移與時(shí)間的關(guān)系狀態(tài)圖不能反映

3、出狀態(tài)轉(zhuǎn)移與時(shí)間的關(guān)系柵格圖柵格圖/籬笆圖：籬笆圖：將開放型的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序?qū)㈤_放型的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序級(jí)聯(lián)形成一個(gè)柵格圖。級(jí)聯(lián)形成一個(gè)柵格圖。編碼路徑：編碼路徑：狀態(tài)序列狀態(tài)序列在柵格圖中形成的一條有向路在柵格圖中形成的一條有向路徑。徑。當(dāng)有向路徑始于全當(dāng)有向路徑始于全“0”狀態(tài)狀態(tài)S0，又終于，又終于S0時(shí)，表明此時(shí)，表明此時(shí)編碼器又回到全時(shí)編碼器又回到全“0”狀態(tài)，狀態(tài)，卷積碼的狀態(tài)轉(zhuǎn)移圖與柵格描述杭州電子科技大學(xué)通信學(xué)院劉超9紅實(shí)線紅實(shí)線表示表示UU=0時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支;黃虛線黃虛線表示表示UU=1時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支;轉(zhuǎn)移分支上數(shù)字

4、表示輸出的編碼比特轉(zhuǎn)移分支上數(shù)字表示輸出的編碼比特V V1和和V V2。卷積碼的狀態(tài)轉(zhuǎn)移的柵格描述杭州電子科技大學(xué)通信學(xué)院劉超10卷積碼的柵格描述杭州電子科技大學(xué)通信學(xué)院劉超11最大似然譯碼最大似然譯碼/最小距離譯碼最小距離譯碼待編碼的信息序列待編碼的信息序列MM：MM=MM0, MM1, MML1；編碼器輸入序列的總長(zhǎng)度：編碼器輸入序列的總長(zhǎng)度：k(L+m)；編碼器輸出的碼序列編碼器輸出的碼序列C C：C C=C C0, C C1,C CL1，其中，其中每個(gè)子碼每個(gè)子碼C Ci含有含有n個(gè)比特；個(gè)比特；經(jīng)離散無(wú)記憶信道經(jīng)離散無(wú)記憶信道(DMC)傳輸后，傳輸后，譯碼器接收的序列譯碼器接收的序列

5、 R R：R R=R R0, R R1,R RL1；對(duì)于對(duì)于DMC信道：信道：碼序列碼序列 C C 的的路徑度量路徑度量 MM(R R/C C)：計(jì)算第：計(jì)算第 l 時(shí)刻到達(dá)狀態(tài)時(shí)刻到達(dá)狀態(tài) i 的最的最大似然路徑的相似度大似然路徑的相似度log p(R R/C C)；子碼子碼 C Ci 度量度量MM(R Ri/C Ci) ：計(jì)算第：計(jì)算第 l 時(shí)刻接收子碼時(shí)刻接收子碼 R Ri 相對(duì)于各碼相對(duì)于各碼字的相似度字的相似度 log p(R Ri/C Ci)，也稱為，也稱為分支度量分支度量。1log(R /C)log(R /C )L miiipp杭州電子科技大學(xué)通信學(xué)院劉超12最大似然譯碼最大似然

6、譯碼/最小距離譯碼最小距離譯碼譯碼器接收到譯碼器接收到 R R 序列后，按最大似然法序列后，按最大似然法則力圖尋找編碼器在籬笆圖上原來走過的則力圖尋找編碼器在籬笆圖上原來走過的路徑，也就是尋找具有最大度量的路徑；路徑，也就是尋找具有最大度量的路徑；對(duì)對(duì)BSC信道，就是尋找與信道，就是尋找與 R R 有最小漢明有最小漢明距離的路徑，即計(jì)算和尋找距離的路徑，即計(jì)算和尋找 mind(R R, C Cj)，j=1,2,2Lk 。注：二進(jìn)制對(duì)稱信道注：二進(jìn)制對(duì)稱信道BSC（Binary Symmetry Channel）杭州電子科技大學(xué)通信學(xué)院劉超13最大似然譯碼最大似然譯碼/最小距離譯碼最小距離譯碼最

7、大似然譯碼方法只是提供了一個(gè)譯碼準(zhǔn)則，最大似然譯碼方法只是提供了一個(gè)譯碼準(zhǔn)則，實(shí)現(xiàn)起來尚有一定困難。因?yàn)樗强紤]了長(zhǎng)實(shí)現(xiàn)起來尚有一定困難。因?yàn)樗强紤]了長(zhǎng)度為度為 (L+m)n 的接收序列來譯碼的，這樣的的接收序列來譯碼的，這樣的序列可能有序列可能有 2Lk 條；條；若實(shí)際接收序列中，若實(shí)際接收序列中，L=50，k=2，則可能的，則可能的路徑有路徑有 2100 條。譯碼器每接收一個(gè)序列條。譯碼器每接收一個(gè)序列 R R，就要計(jì)算就要計(jì)算 1030 個(gè)似然函數(shù)才能做出譯碼判決。個(gè)似然函數(shù)才能做出譯碼判決。若若 kL 再大一些，譯碼器按最大似然譯碼準(zhǔn)再大一些，譯碼器按最大似然譯碼準(zhǔn)則譯碼將是很困難的

8、。則譯碼將是很困難的。杭州電子科技大學(xué)通信學(xué)院劉超14維特比譯碼工作原理維特比譯碼工作原理維特比提出了一種算法：維特比提出了一種算法：譯碼器不是在籬笆圖上一次就計(jì)算和比譯碼器不是在籬笆圖上一次就計(jì)算和比較較 2Lk 條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想：維特比譯碼的基本思想：將接收序列將接收序列 R R 與籬笆圖上的路徑逐分與籬笆圖上的路徑逐分支地比較，比較的長(zhǎng)度一般取支地比較，比較的長(zhǎng)度一般取 (56)mn，然后留下與，然后留下與 R

9、 R 距離最小的距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長(zhǎng)并存儲(chǔ)起來。逐分支地延長(zhǎng)并存儲(chǔ)起來。幸存路徑的數(shù)目等于狀態(tài)數(shù)：幸存路徑的數(shù)目等于狀態(tài)數(shù)：2km 以以 (2,1,2) 卷積碼為例說明維特比譯碼的一般卷積碼為例說明維特比譯碼的一般過程：過程：設(shè)發(fā)送序列設(shè)發(fā)送序列 C C 為全為全0；接收序列接收序列 R R=10,00,01,00,00,00,00, 維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超15假設(shè)譯碼器的初始狀態(tài)為全假設(shè)譯碼器的初始狀態(tài)為全0；第第0個(gè)時(shí)刻：個(gè)時(shí)刻：接收序列的第接收序

10、列的第0個(gè)分支個(gè)分支 R R0=10 進(jìn)入譯碼器。進(jìn)入譯碼器。從從 S0 狀態(tài)有兩個(gè)分支，它們是狀態(tài)有兩個(gè)分支，它們是 00 和和 11，R R0與這兩個(gè)分支與這兩個(gè)分支比較，比較的結(jié)果和到達(dá)的狀態(tài)如表比較，比較的結(jié)果和到達(dá)的狀態(tài)如表1 所示：所示：每個(gè)狀態(tài)每個(gè)狀態(tài)/節(jié)點(diǎn)都有兩個(gè)存儲(chǔ)器：節(jié)點(diǎn)都有兩個(gè)存儲(chǔ)器：路徑存儲(chǔ)器：存儲(chǔ)該狀態(tài)的部分路徑；路徑存儲(chǔ)器：存儲(chǔ)該狀態(tài)的部分路徑；路徑值存儲(chǔ)器：存儲(chǔ)達(dá)到該狀態(tài)的部分路徑值路徑值存儲(chǔ)器：存儲(chǔ)達(dá)到該狀態(tài)的部分路徑值 (累加距累加距離離)。 維特比譯碼的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州電子科技大學(xué)通信學(xué)院劉超16第

11、一個(gè)時(shí)刻：第一個(gè)時(shí)刻：進(jìn)入譯碼器的接收碼組進(jìn)入譯碼器的接收碼組 R R1=00 和此時(shí)刻和此時(shí)刻出發(fā)出發(fā)的的四條分支四條分支比較，比較結(jié)果和達(dá)到狀態(tài)如表比較，比較結(jié)果和達(dá)到狀態(tài)如表2所示：所示：從第一個(gè)時(shí)刻到第二個(gè)時(shí)刻：從第一個(gè)時(shí)刻到第二個(gè)時(shí)刻：共有四條路徑，到達(dá)共有四條路徑，到達(dá)S0, S1, S2和和S3。在第二個(gè)時(shí)刻以前譯碼器不做任何選擇和判決。在第二個(gè)時(shí)刻以前譯碼器不做任何選擇和判決。每個(gè)狀態(tài)的路徑存儲(chǔ)器每個(gè)狀態(tài)的路徑存儲(chǔ)器存儲(chǔ)下此時(shí)刻的幸存路徑：存儲(chǔ)下此時(shí)刻的幸存路徑：0000,0011,1110,1101；每個(gè)狀態(tài)的路徑值存儲(chǔ)器每個(gè)狀態(tài)的路徑值存儲(chǔ)器存儲(chǔ)了此時(shí)刻到達(dá)該狀態(tài)的幸存存儲(chǔ)

12、了此時(shí)刻到達(dá)該狀態(tài)的幸存路徑累加值路徑累加值 (累加距離累加距離)。維特比譯碼的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州電子科技大學(xué)通信學(xué)院劉超17維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超18從第二個(gè)時(shí)刻起：從第二個(gè)時(shí)刻起：第二個(gè)接收碼組第二個(gè)接收碼組 R R2=01 進(jìn)入譯碼器，從進(jìn)入譯碼器，從籬笆圖籬笆圖上可見，從第二個(gè)時(shí)刻到第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)上可見，從第二個(gè)時(shí)刻到第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的分支有兩個(gè)（或者說在第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的路徑的分支有兩個(gè)（或者說在第三個(gè)時(shí)刻，進(jìn)入每個(gè)狀態(tài)的路徑有兩條）。譯碼器將接收碼組有兩條）。譯碼器將接收碼

13、組 R R2 與進(jìn)入每個(gè)狀態(tài)的兩個(gè)分支與進(jìn)入每個(gè)狀態(tài)的兩個(gè)分支進(jìn)行比較和判決，選擇一個(gè)累加距離（部分路徑值）最小的進(jìn)行比較和判決，選擇一個(gè)累加距離（部分路徑值）最小的路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑路徑作為進(jìn)入該狀態(tài)的幸存路徑。這樣的幸存路徑共四條共四條，比較和判決的過程如下：比較和判決的過程如下： 維特比譯碼的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州電子科技大學(xué)通信學(xué)院劉超19經(jīng)過比較后選擇：經(jīng)過比較后選擇：部分路徑部分路徑 000000為到達(dá)為到達(dá) S0 狀態(tài)的幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 000011為到達(dá)為到達(dá) S1 狀態(tài)的

14、幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 110101為到達(dá)為到達(dá) S2 狀態(tài)的幸存路徑；狀態(tài)的幸存路徑；部分路徑部分路徑 001101為到達(dá)為到達(dá) S3 狀態(tài)的幸存路徑。狀態(tài)的幸存路徑。按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個(gè)時(shí)按照上述方法，接收序列的諸碼組依次進(jìn)入譯碼器，每個(gè)時(shí)刻進(jìn)入一個(gè)碼組，沿著籬笆圖對(duì)每個(gè)狀態(tài)按部分路徑值（累刻進(jìn)入一個(gè)碼組，沿著籬笆圖對(duì)每個(gè)狀態(tài)按部分路徑值（累加距離）的大小，選擇一條幸存路徑。在每個(gè)狀態(tài)上進(jìn)行判加距離）的大小，選擇一條幸存路徑。在每個(gè)狀態(tài)上進(jìn)行判決時(shí)，可能出現(xiàn)進(jìn)入這一狀態(tài)的兩條路徑的距離值相同，這決時(shí)，可能出現(xiàn)進(jìn)入這一狀態(tài)的兩條路徑的距離值相

15、同，這時(shí)可以任選其一，因?yàn)閷?duì)以后的判決而言，無(wú)論選擇那一條時(shí)可以任選其一，因?yàn)閷?duì)以后的判決而言，無(wú)論選擇那一條路徑，累加距離是相同的。路徑，累加距離是相同的。維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超20對(duì)本例而言，按上述算法進(jìn)行到對(duì)本例而言，按上述算法進(jìn)行到第十一個(gè)第十一個(gè)分支分支后，四條路徑后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達(dá)到較低的錯(cuò)誤概率。一般，約為達(dá)到較低的錯(cuò)誤概率。一般，約為 (56)mn，所以，維特比譯，所以，維特比譯碼的延時(shí)可達(dá)碼的延時(shí)可達(dá) (56)m 個(gè)單位時(shí)刻（每個(gè)單位時(shí)刻為個(gè)單位時(shí)刻（

16、每個(gè)單位時(shí)刻為 n 個(gè)碼元個(gè)碼元長(zhǎng)度）就可以對(duì)第長(zhǎng)度）就可以對(duì)第0個(gè)接收碼組的信息元進(jìn)行判決。依此類推，個(gè)接收碼組的信息元進(jìn)行判決。依此類推，對(duì)接收序列中的諸碼組進(jìn)行譯碼。對(duì)接收序列中的諸碼組進(jìn)行譯碼。維特比譯碼的一次運(yùn)算：維特比譯碼的一次運(yùn)算：計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑。比較各部分路徑的度量值，選擇一條作為幸存路徑?；h笆圖中共有籬笆圖中共有 2km 個(gè)狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存?zhèn)€狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存儲(chǔ)儲(chǔ) m 成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷

17、積碼，其成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷積碼，其 m 不能選的太大。不能選的太大。 維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超21 維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超22維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超23維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超24 維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超25維特比譯碼的基本原理杭州電子科技大學(xué)通信學(xué)院劉超26總結(jié)維特比算法的步驟總結(jié)維特比算法的步驟在第在第 j(j=m)個(gè)時(shí)刻以前，譯碼器計(jì)算所有的長(zhǎng)為個(gè)時(shí)刻以前，譯碼器計(jì)算所有的長(zhǎng)為 m 個(gè)分支的部分個(gè)分支的部分路徑值，對(duì)進(jìn)入路徑值，對(duì)進(jìn)入 2k

18、m 個(gè)狀態(tài)的每一條部分路徑都保留。個(gè)狀態(tài)的每一條部分路徑都保留。第第 m 個(gè)時(shí)刻開始，對(duì)進(jìn)入每一個(gè)狀態(tài)的部分路徑進(jìn)行計(jì)算，這樣個(gè)時(shí)刻開始，對(duì)進(jìn)入每一個(gè)狀態(tài)的部分路徑進(jìn)行計(jì)算，這樣的路徑有的路徑有 2k 條，挑選具有最大部分路徑值的部分路徑為幸存路徑，條，挑選具有最大部分路徑值的部分路徑為幸存路徑，刪去進(jìn)入該狀態(tài)的其它路徑，然后，幸存路徑向前延長(zhǎng)一個(gè)分支。刪去進(jìn)入該狀態(tài)的其它路徑，然后，幸存路徑向前延長(zhǎng)一個(gè)分支。重復(fù)第二步的計(jì)算、比較和判決過程。若輸入接收序列長(zhǎng)為重復(fù)第二步的計(jì)算、比較和判決過程。若輸入接收序列長(zhǎng)為 (L+m)k，其中，后，其中，后 m 段是人為加入的全段是人為加入的全0段，則譯碼一直進(jìn)行到段，則譯碼一直進(jìn)行到 (L+m) 個(gè)時(shí)刻為止。個(gè)時(shí)刻為止。若進(jìn)入某個(gè)狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可若進(jìn)入某個(gè)狀態(tài)的部分路徑中，有兩條的部分路徑值相等，則可