一、實驗目的
1.了解維特比譯碼的原理
2.了解維特比譯碼的算法

二、實驗原理
卷積碼的譯碼方式有3種：維特比譯碼，序列譯碼和門限譯碼。維特比譯碼具有最佳性能，但硬件實現復雜：門限譯碼性能最差，但硬件簡單；序列譯碼在性能和硬件方面介于維特比譯碼和門限譯碼之間。維特比譯碼和序列譯碼都是建立在最大似然譯碼原理的基礎上。下面介紹卷積碼的維特比譯碼的原理。
卷積碼網絡圖中共有 種狀態，每個節點（即每個狀態）有 支路引出。為簡便起見，討論K=1的情形，從全0狀態起始點開始討論。
由網絡圖的前N-1條連續支路構成的路徑互不相交，即最初的 條路徑各不相同，當接收到第N條支路時，每條路徑都有2條支路延伸到第N級上，而第N級上的每兩條支路又都匯聚在節點上。在維特比譯碼算法中，把匯聚在每個節點上的兩條路徑的對數似然函數累加值進行比較，然后把具有較大對數似然函數累加值的路徑保存下來，而丟棄另一條路徑。經挑選后第N級只留下 條幸存路徑，選出的路徑連同它們的對數似然函數累加值一起被存儲起來。由于每個節點引出兩條支路，因此以后各級中路徑的延伸都增大一倍，但比較它們的似然函數累加值后，丟棄一半，結果留存下來的路徑總數保持常數。
由此可見，上述譯碼過程中的基本操作是“加－比－選”，每級求出對數似然函數累加值，然后兩兩比較，并做出選擇。有時會出現兩條對數似然函數累加值相等的情況，在這種情況下可以任意選擇其中一條作為“幸存”路徑。
在每一級中都有 條幸存路徑，當序列發送完畢后，為了判斷其最后結果，就要在網格圖的終結處加上N-1個已知信息（即N-1條已知支路）作為結束信息。在結束信息到來時，由于每一狀態中只有與已知發送信息相符那條支路被延伸，因而在每級比較后，幸存路徑減少一半。因此，在接收到N-1個已知信息后，在整個網格圖中就只有唯一的一條幸存路徑保存下來。這就是譯碼所得的路徑。即在已知接收到的序列的情況下，這條譯碼路徑和發送序列是最相似的。
維特比譯碼整個過程并不復雜，譯碼器的運行是前向的，無反饋的。由于在每級中的每個狀態上要進行“加－比－選”運算，譯一個L比特的序列，譯碼操作的總次數為 ，因此譯碼器的復雜性與狀態數成正比，也是隨約束長度N的增加而呈指數增長的。因此目前只限于應用在 的卷積碼中。
上述作為結束信息的已知信息實際上就是不發生錯誤的一段信息。因此，只要差錯模式不超出卷積碼的糾錯能力，從一個節點開始分叉產生的各條幸存路徑經過一段間隔后，總能正確地又合并成一條路徑。但需要經過多長時間間隔，在何處合并，都是不確定的，與差錯模式有關。而在實際實現時，不可能建立這種隨機的譯碼深度，只能建立一個固定的譯碼深度。
Viterbi譯碼算法
Viterbi（維特比）算法根據可能的狀態轉移進行譯碼，狀態轉移可用網格圖表示，圖中狀態表示編碼器狀態，路徑狀態表示編碼器輸出符號。
Viterbi譯碼譯碼過程就是根據接收到的數據符號，按最大似然譯碼準則找出編碼器在網格圖上所走過的路徑。Viterbi譯碼算法的處理過程如圖6-1所示。

    
圖6-1 通用Viterbi譯碼算法處理流程

度量值的更改包括：
（1） 分支度量計算；
（2） 對每個新狀態，將分支度量值與舊狀態的度量值相加，得到新狀態的度量值；
（3） 選擇并保存最小度量值；
（4） 保存幸存路徑；
（5) 每收到一個符號就進行狀態轉移，Viterbi譯碼算法必須計算前一個狀態到各個新狀態的分支度量值。當采用硬判決輸入時，分支度量值可用漢明距表示；若用軟判決輸入時，用歐氏距離表示，對于編碼速率為R=1/C的卷積碼來說，其歐氏距離為
      

其中sdn表示接收序列，Gn(J)為網格圖上每個路徑狀態的期望輸入值，J是路徑指示值，C為編碼速率的倒數。將上式展開得
   

在進行路徑度量值比較時，可以不加以考慮。這樣省去表達式前面的負號，則在分支度量值比較時應取大值。對于編碼速率為1/2的卷積碼，
     

圖6-2 （2,1,3）卷積碼蝶型結構

其分支度量值為：T=sd0×G0(J)＋sd1×G1(J)，其中sdn與Gn(J)均用雙極性表示，即0用＋1表示，而＋1用－1，在單片機編程的過程中，分別用T0到T1寄存器來表示，即T0＝＋sd0＋sd1，T1＝＋sd0－sd1。    
分支度量值的更新可用如圖6-2所示蝶型結構表示。該圖給出了從一個舊狀態到新狀態的所有可能的卷積編碼的轉移分支路徑。
用單片機AT89C2051（U402）對單片機AT89C2051（U401）輸出的卷積編碼序列進行譯碼，如圖6-3所示。卷積編碼序列DATA1（無誤碼）或DATA2（有一位誤碼）從U402的T1引腳串行輸入，由開關K401決定接收哪種編碼序列，信號波形見TP404，單片機U402對輸入的卷積編碼序列進行維特比譯碼后，從DATA4（RXD引腳，波形見TP405）串行輸出，并從P1口并行輸出，使發光二極管（D0－D7）顯示8位譯碼輸出序列。



圖6-3 用單片機AT89C2051進行維特比譯碼電路圖

三、實驗內容
1.設置撥線開關。
把撥線開關（SW401）的第1-8設置輸入序列為0DCH。設置撥線開關的第9位狀態為1（即開關撥上），不產生誤碼，因此DATA1（TP402）和DATA2（TP403）的信號是一樣的，用雙蹤示波器觀察。
2. 用發光二極管觀察譯碼輸出的結果
把跳線器插在K401的1、2兩端或2、3兩端，使譯碼器U402（見TP404）接收的是無誤碼的卷積編碼序列DATA1（波形見TP402，無誤碼）信號或DATA2（波形見TP403，插入誤碼）信號；觀察發光二極管（D0－D7）顯示的8位譯碼輸出序列是什么（燈亮為1，滅為0），與撥線開關（SW401）的第1-8設置的輸入序列是否一致，對比測量點TP401與TP405的波形。
當把撥線開關（SW401）的第1-8設置的輸入序列分別為
（1） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
讀出發光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關（SW401）設置的輸入序列是否一致。同時用雙蹤示波器觀察和記錄DATA1（波形見TP402）和DATA2（波形見TP403）的卷積編碼信號。
3. 用雙蹤示波器觀察譯碼輸出的結果
設置撥線開關的第9位狀態為1（即開關撥上），不產生誤碼，把跳線器插在K401的1、2兩端或2、3兩端，使U402接收的是無誤碼的卷積編碼序列DATA1信號或DATA2信號；當把撥線開關（SW401）的第1-8設置的輸入序列為
（2） 1EH；（2）37H；（3）56H；（4）78H；（5）9CH等
用雙蹤示波器的兩個探頭分別接在DATA3（TP401，原始數字序列輸入）和DATA4（TP405，譯碼還原數字序列輸出），觀察譯碼輸出序列與輸入序列是否一致。
4. 觀察對有誤碼的卷積編碼序列的維特比譯碼。
把撥線開關（SW401）的第1-8設置輸入序列為0DCH。設置撥線開關的第9位狀態為0（即開關撥下），產生誤碼。用雙蹤示波器觀察和記錄DATA1和DATA2的卷積編碼信號。
把跳線器插在K401的2、3兩端，使U402接收的是有誤碼的卷積編碼序列DATA2信號；讀出發光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關（SW401）設置的輸入序列是否一致。
當把撥線開關（SW401）的第1-8設置的輸入序列分別為
（3） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
讀出發光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關（SW401）設置的輸入序列是否一致。用雙蹤示波器的兩個探頭分別接在DATA3（TP401，原始數字序列輸入）和DATA4（TP405），譯碼還原數字序列輸出），觀察譯碼輸出序列與輸入序列是否一致。

四、實驗報告要求
1. 掌握差錯控制編碼的基本概念
2. 掌握維特比譯碼的原理和算法
3. 畫出各點波形，并做簡要的說明