柵格圖 Trellis Diagram

柵格圖看起來似乎有點亂,但是總的來講,在表示編譯碼原理方面還是優(yōu)于樹狀圖和狀態(tài)圖,因為柵格圖能一直按照時間順序表示編譯碼的過程. X 軸表示時間, y 軸表示所有可能的狀態(tài). 隨著時間的增加,我們沿著柵格圖水平方向移動. 每次狀態(tài)轉(zhuǎn)移都表示有一個新的比特輸入進來.

畫柵格圖時,垂直方向畫所有可能的 $$2^L$$ 種狀態(tài). 然后,我們在允許的狀態(tài)轉(zhuǎn)移之間連線.每個狀態(tài)只有兩種狀態(tài)轉(zhuǎn)移路徑,轉(zhuǎn)移到哪個,由輸入比特是 0 還是 1 決定. 箭頭線上寫上輸入的比特和用括號括起來的輸出比特. 箭頭線向斜上方表示輸入的比特為0,向斜下方表示輸入的比特為1. 就像狀態(tài)圖和樹狀圖一樣,每個不同的編碼器都有唯一的一個柵格圖. 我們可以畫任意長度的柵格圖. 每次延展都是可能的狀態(tài)轉(zhuǎn)移.

?

通常我們從狀態(tài)000開始, 然后延展了 L 個輸入比特后，則所有的狀態(tài)就都被遍歷到了。然后，狀態(tài)轉(zhuǎn)移就開始重復了。

?

?

用柵格圖怎么實現(xiàn)編碼

圖10a 中，輸入比特顯示在最上面. 我們只能從狀態(tài)000開始。編碼過程很簡單. 輸入為0則向上走，輸入為1則向下走. 例如輸入為1011000時走的路線,在圖中用連線表示了出來. 我們可以看到,得到的結果與前面提到的其他三種方法(沖激響應,狀態(tài)圖,樹狀圖)都是一樣的.

?

?

?

譯碼

有幾種不同的方法來譯卷積碼. 這些方法被分為兩大類:

1.???? 順序譯碼 Sequential Decoding

????????????-????? Fano 算法

2.???? 最大似然譯碼 Maximum likely-hood decoding

????????????-????? 維特比譯碼 Viterbi Decoding

這些算法都是基于相同的譯碼思想推導出來的兩類方法.

?

譯碼的基本思想

假如通過1/2碼率的編碼器來編碼 3 個比特. 我們收到 6 個比特(忽略清空用的比特). 這 6 個比特可能有也可能沒有錯誤.從編碼的過程我們知道,這6個比特是唯一的. 但是,由于出錯,我們可能收到所有可能的6個比特. 那么輸入的3個比特有8種情況.然后每種情況都有唯一的一種6 比特輸出. 這些輸出就是所有可能的正確的輸出,譯碼的任務就是確定發(fā)送的是哪一種3比特.

?

?

?

我們收到的比特序列為111100,不是上面8 種情況中的任何一種,那么我們?nèi)绾巫g碼? 我們可以做兩件事情:

1.???? 用接收到的比特序列同所有可能的輸出序列做對比,選最小漢明距離的( 或者說是 比特不匹配的).

2.???? 做相關運算,取相關度最好的

?

第一種方法就是硬判決譯碼的方法.第二種方法是軟判決譯碼的方法. 比特的不匹配,也就是接收序列和碼字的點積,可能仍然得到模糊的答案,無法確定發(fā)送的比特是什么.

?

隨著比特數(shù)增加,這種粗暴的譯碼方法的計算量急劇增加,導致完全不再可行.我們需要找更有效率的方法,不用檢查所有可能的情況,并且能消除模糊性(有兩種可能的選擇,如果表 4 中粗體所示)

如果發(fā)送 s 個比特, 則有 ?種可能的碼字,那么接收到數(shù)據(jù)后, 我們?nèi)绾巫g碼才不需要檢查所有這些可能? 這是譯碼算法的基本出發(fā)點.

?

?

順序譯碼 Sequential Decoding

順序譯碼算法是最早被提出來用于譯碼卷積碼的算法. 最早由 Wozencraft 提出,后來 Fano 提出了一個更好的版本.

?

我們可以對順序譯碼做一個比喻. 假如你要去某地,有人給了你一些指引標記. 但是,這些指引標記可能有錯誤,或者你不認識其中的一個標記, 最后導致你走到了一個錯誤的路徑上. 如果你看不到任何標記了,則表明你走了一個錯誤的路徑.你可能回到某個點,然后選擇一個不同路徑繼續(xù),按照這種方式,你可以到達目的地.但是,在這個過程中你可能需要回退很多次, 這依賴于給的指引是否清晰準確.

?

類似上面的比喻,順序譯碼算法在每一時刻只處理一條路徑. 你可以放棄一條路徑然后回退再走另外一條路徑, 但是重要的是,你在同一時刻只能處理一條路徑.

?

順序譯碼可以在柵格圖上可以前向或者后向移動. 譯碼器記錄每次決策的結果,每次都是對某一個狀態(tài)轉(zhuǎn)移做決定,然后在柵格圖上移動. 如果某種統(tǒng)計值超過了某個設定的閾值,則放棄這條路徑, 然后延當前路徑回退到上一個分叉,此處的分叉,其統(tǒng)計值低于設定的閾值.

?

我們來做一個實例. 編碼器是(2,1,4),同前面的例子中用的編碼器相同, 假設輸入比特序列為1011 000(記得:最后三個比特是清空用的比特,他們對應的輸出稱為 尾比特 tail bits).

?

如果沒有錯誤發(fā)生,我們將收到 ?11 11 01 11 01 01 11

假如我們收到的數(shù)據(jù)為 ????????01 11 01 11 01 01 11.? 有一個比特發(fā)生了錯誤. 第一個比特被錯誤接收為 0 .

?

用順序譯碼算法來譯碼

1.???? 決策點1,譯碼器審視接收到的前兩個比特 01. 現(xiàn)在看起來有一個錯誤發(fā)生,因為正確的輸出只有00或者11. 但是, 是哪種情況出錯了呢? 譯碼器隨機選擇 00 往下走. 對應00的輸入比特是 0. 我們把錯誤數(shù)記為 1. 現(xiàn)在到?jīng)Q策點2.

2.???? 在決策點2. 譯碼器審視接下來的兩個接收比特11. 在這里,可以正確決策出發(fā)送比特為1,因為其輸出恰好就是 11. 到?jīng)Q策點 3.

3.???? 在決策點3,收到的兩個比特是01. 但是,實際輸出要么是11,要么是00. 看起來有一個比特錯誤發(fā)生, 錯誤數(shù)增長到2. 但是由于錯誤數(shù)少于設定的閾值3(這個根據(jù)信道的統(tǒng)計特性設立的),譯碼器繼續(xù)往下走. 我們隨機選擇上面分支往下走,認為輸入的比特是0,到?jīng)Q策點4.

4.???? 決策點4,譯碼器檢測到又有一個錯誤發(fā)生,因為接收到的數(shù)據(jù)是11,而實際正確的輸出只有10或者01. 錯誤數(shù)增長到3, 達到閾值,譯碼器回退.

?

5.???? 譯碼器回退到?jīng)Q策點3, 此處的錯誤數(shù)小于3. 選擇另外一條路徑走,到?jīng)Q策點5. 又是碰到有一個錯誤發(fā)生的情況. 接收比特是11,但是正確的只有01或者10. 錯誤數(shù)又累積到3, 回退.

6.???? 從決策點3 出發(fā)的兩個路徑都已經(jīng)不能滿足條件. 所以,譯碼器必須繼續(xù)回退直到錯誤數(shù)小于3的地方,所以,譯碼器必須回到到?jīng)Q策點2,再回退到?jīng)Q策點1.

從決策點1開始,譯碼器將都是碰到完美匹配的情況,譯碼器成功譯碼出比特序列 1011000.

?

順序譯碼算法需要的內(nèi)存是可控的,這個方法適用于長約束長度的編碼器, S/N(信噪比?)比較低的情況. 甚至 NASA 的行星際間的通信,也利用了順序譯碼的優(yōu)點.