最大似然和維特比 Viterbi 譯碼

維特比譯碼是最成功的最大似然譯碼思想的實現(xiàn). 這個算法中,在每個時刻點逐步系統(tǒng)地縮窄可能譯碼出來的序列范圍. 使用的基本準則有:

1.???? 錯誤的發(fā)生不是很頻繁,即錯誤概率比較小

2.???? 兩個連續(xù)的錯誤概率遠小于單個錯誤的概率,即錯誤的分布是比較均勻的

?

維特比譯碼對給定長度的整個接收序列按照整體來評估. 譯碼器為每條路徑計算度量,基于度量做決策. 跟蹤所有的路徑,除非有兩個路徑都轉移到同一個狀態(tài)節(jié)點上,具有高度量的路徑將被保留,低度量路徑將被舍棄. 留下來的路徑稱為幸存者.

?

N個比特的序列,則所有可能接收到的序列有 ?種可能, 其中只有 ?種是合法的. 維特比算法使用最大似然概率的準則, 僅僅比對個幸存路徑而不是檢查所有的 2^N 種可能.

?

最常用的度量是漢明距度量( Hamming Distance Metric), 剛好是接收到的比特序列和正確序列的點積. 還可以用其他度量,后面我們再討論.

(英文原文中，此處確實是用 dot product，譯者認為這里應該理解為如果相同的話，就加1，如果不同的話，就加 0 ，取相同的比特的個數(shù)相加）

?

?

沿著路徑,這些度量被累加起來, 有最高度量值的路徑將是最后的勝利者.

?

這些描述聽起來不是那么容易理解,我們看一個具體的譯碼例子就很清楚了.

?

我們用維特比譯碼算法來譯碼接收到的序列 01 11 01 11 01 01 11.

?

1.???? 在 t=0, 我們收到比特01. 譯碼器從狀態(tài)000開始. 有兩個路徑可以走, 雖然兩個路徑的輸出都沒有完全匹配接收到的01.譯碼器對兩個路徑分別計算度量, 然后兩個路徑都繼續(xù)往下走,不像順序譯碼算法中在每個時刻點都要做決策. 現(xiàn)在,這兩個路徑的度量都是1, 意味這只有一個比特與正確的碼字相匹配.

?

2.???? 在t=1,譯碼器從兩個狀態(tài)都繼續(xù)延展. 路徑度量都各自分別計算,用正確的碼字與接收到的比特11做比對. 新的度量信息被顯示在柵格圖的右邊一列.

3.???? 在 t=2, 四個狀態(tài)繼續(xù)延展出8個狀態(tài),至此所有可能路徑都被延展出來. 路徑度量也被計算和更新出來,用正確的碼字與接收到的比特01做比對,把新計算出來的漢明距加上從 t=1 時刻來的度量,得到新的度量.

?

在t=3,柵格圖已經延展出所有的路徑了.每個節(jié)點都有一個路徑進來. 度量值顯示在上圖的右側.

在t=4,所有路徑繼續(xù)延展,現(xiàn)在開始有多個路徑集中到一個節(jié)點上.每個節(jié)點有兩個路徑進來,兩個度量值都分別計算出來.根據(jù)最大似然準則,在每個節(jié)點,我們舍棄地度量值的路徑,因為其發(fā)生的可能性更低. 在每個節(jié)點舍棄路徑,有助于減少我們需要檢查的路徑的數(shù)量, 這也是維特比譯碼的優(yōu)點.

?

現(xiàn)在,有一個或者多個路徑來到同一個節(jié)點. 路徑度量在右側列出.在每個節(jié)點,我們只保留最高度量的路徑, 舍棄其他的(圖中紅色路徑被舍棄). 經過舍棄后的結果如下圖, 留下的路徑的度量被列在右側.

?

在t=5,經過舍棄后,如下圖所示,我們繼續(xù)向前延展,計算新的度量.在下一個節(jié)點,又有路徑集中在一個節(jié)點,然后舍棄低度量的路徑.

?

在t=6,接收到的比特11. 對所有路徑計算度量,舍棄所有小的度量.

?

接下來的一步就是最后一步,如下圖.我們選擇最高度量的路徑作為勝利者. 沿著這個路徑回溯,得到正向順序的各個狀態(tài):000,100,010,101,110,011,001,000, 對應輸入的比特為 1011 000.

?

?

柵格的長度是 4 + m 比特.理想情況下,應該等于發(fā)送消息的長度.但是,使用截斷操作, 存儲容量的需求可以降低,因為譯碼不用等到所有傳輸?shù)男蛄卸际胀瓴砰_始. 典型的截斷長度是128比特,或者是5到7倍的約束長度.

?

維特比譯碼是非常重要的,因為也被用于分組碼的譯碼. 這種柵格譯碼也被用于Trellis-Coded? Modulation(TCM).

?