Viterbi譯碼器原理
1、馬爾科夫過程
該過程下一時刻的狀态隻與上一時刻的狀态有關，與其他時刻的狀态無關。
2、卷積編碼器譯碼系統原理
圖2.1 卷積碼編碼譯碼系統框圖
卷積碼編碼器的狀态Xk随着送入的信源比特Vk改變，剛好是一個有限狀态的離散馬爾科夫過程。圖2.1所示為卷積碼編碼譯碼總體框圖，信源Vk通過一個移位寄存器Xk及線性邏輯電路後，産生編碼碼元，記為Yk，經過有噪聲信道傳播後，接收信号為Zk。Viterbi譯碼器所做的工作便是利用譯碼算法，從Zk判斷出Vk，恢複出信源資訊。
設卷積碼移位狀态寄存器共有N位，那麼Xk的狀态将有2的N次方種。每當一個信源碼進入編碼器，移位狀态寄存器的狀态将改變一次，且輸出一個與該狀态唯一對應的編碼值。所謂的“後驗”，是指根據接收到的編碼，推測出其所對應的移位狀态寄存器的狀态。而Viterbi譯碼是在标記所有可能的狀态轉換的路徑中選擇最有可能的一條，是以稱之為最大後驗機率方法，且這條路徑所對應的信源碼就是譯碼結果。
首先，要知道如何挑選最重要的路徑，即機率最大的路徑。定義路徑長度為-lnP(X,Z)，其中X為與該路徑所對應的狀态序列，Z為接收序列。之是以如此定義路徑長度，是因為最終是以最大化後驗機率P(X|Z)為目标去尋找路徑的，且P(X,Z)=P(X|Z)P(Z)，故等價于尋找P(X,Z)的最大化。由于-lnP(X,Z)是關于P(X,Z)的單調函數，是以隻要找到使其最小的路徑，便實作了目的。
P(X,Z)又可分解為：
定義路徑分支的長度為：
其中，
表示從Xk到Xk+1的狀态轉換。那麼總體的路徑長度可以表示為
即路徑分支的長度和。是以，任一時刻的最短路徑就是各分支路徑長度和最小的路徑，稱之為幸存路勁。且對于每一個時刻k而言，網格圖裡均存在2的N次方調幸存路徑，每條路徑到達一個k+1時刻的狀态Xk。
為了便于說明Viterbi算法的操作過程，一般将随時間推移發生的狀态轉變用路徑連接配接，形成一張網格圖。
圖2.2 一個（2，1，2）卷積編碼器
圖2.3 （2，1，2）卷積編碼器網格圖
圖2.2給出了一個簡單的（2，1，2）卷積編碼器，圖2.3所示是其對應的網格圖。在圖2.3中，S0-S3表示卷積碼移位器的4中可能狀态，一般編碼器初始狀态為S0，故譯碼器起始也從S0開始。從時間點0T到7T，每個狀态都有兩個分支，指向由新進入編碼器的信源碼Vk（0或1）所帶來的狀态改變，例如當狀态是S0，若輸入Vk=0，則下一時刻狀态仍為S0，輸出編碼Yk=00。反之，如輸入為1，狀态改變成S1，輸出編碼Yk=11。将分支路徑的輸出編碼和接收到的編碼比較，把兩個碼之間的漢明距離d(Yk,Zk)賦給這一段分支路徑作為路徑長度。這裡使用漢明距離來代替機率計算，如d(00,01)=d(00,10)=d(10,11)=d(01,11)=1,d(00,11)=d(10,01)=2.d越小，相似度越大，辨別機率越高，則路徑長度越短。
根據這種準則來選擇通過每個狀态的兩條路徑之一。當譯碼結束，隻有兩條路徑到達終點狀态S0，選擇較短的一條便可。
基于圖2.3的網格圖，我們在圖2.4中給出利用Viterbi算法計算路徑長度，選擇幸存路徑的過程。假設接收到編碼序列Z=｛00，01，10，00，00，00，00，00｝，要從圖2.4中選出一條最短路徑。路徑旁邊的數字代表漢明距離d(Yk,Zk)，圓圈裡的數字辨別到達改狀态的最短路徑的長度和。假設0T時刻譯碼器開始工作，從S0發出兩條分支，一條通往S1，一條指向S0自身，前者對應的編碼是11，則d(11,Z0=00)=2，後者對應編碼00，d(00,Z0=00)=0。接着從1T時刻的兩個狀态S0、S1各自發出兩條分支，其計算方式同前。從2T時刻起，四個狀态均有路徑達到，這實際上是譯碼的一般情況，因為0-1T隻是起始狀态。而從3T時刻起，每個狀态均能通過兩條路徑到達，必須選擇其中較短的一條。用實線表示幸存路徑，虛線表示淘汰路徑。若兩條路徑長度相同，則任意保留一條。如此進行下去，直到5T時刻，開始進入回歸階段，即假定編碼器隻能輸入0，故6T時刻能到達的狀态隻有S0和S2。最後7T時刻，抉擇出最短路徑為S0-S0-S0-S0-S0-S0-S0(途中加粗的路徑)，即發送序列是全零序列｛0，0，0，0，0，0，0｝。
圖2.4 Viterbi譯碼算法示意