維特比譯碼介紹

1、1The Viterbi Algorithm劉超杭州電子科技大學通信學院網(wǎng)絡通信教研室杭州電子科技大學通信學院劉超2教學內(nèi)容：卷積碼的簡要介紹維特比譯碼的基本原理維特比譯碼的基本過程教學目標掌握維特比譯碼的基本原理熟悉用柵格描述維特比譯碼的過程教學內(nèi)容與目標杭州電子科技大學通信學院劉超3卷積碼編碼器卷積碼編碼器結構框圖k=2輸出輸出1234編碼器相關術語(m,k,n)碼，約束長度m，每次移位的比特k，碼速率Rc=k/n 狀態(tài)S=(4 3 2 1)，共2km種狀態(tài)m=2輸入輸入123n=3杭州電子科技大學通信學院劉超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)轉移圖與數(shù)學方程杭州電子科技大學通信學院劉超5該碼的狀態(tài)轉移方程和輸出方程分別為該碼的狀態(tài)轉移方程和輸出方程分別為 1=U U 2=1 V V1=UU +1+2 V V2=UU +2 卷積碼的相關數(shù)學方程杭州電子科技大學通信學院劉超6卷積碼的狀態(tài)轉移圖編碼器及其對應的狀態(tài)轉移圖如下編碼器及其對應的狀態(tài)轉移圖如下杭州電子科技大學通信學院劉超7卷積碼的狀態(tài)轉移圖杭州電子科技大學通信學院劉超8卷積碼的柵格圖卷積碼的柵格圖(籬笆圖籬笆圖)狀態(tài)圖不能反映出狀態(tài)轉移與時間的關系狀態(tài)圖不能反映

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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