數(shù)字通信原理實驗箱卷積碼的維特比譯碼
一、實驗目的1.了解維特比譯碼的原理
2.了解維特比譯碼的算法
二、實驗原理
卷積碼的譯碼方式有3種：維特比譯碼，序列譯碼和門限譯碼。維特比譯碼具有最佳性能，但硬件實現(xiàn)復雜：門限譯碼性能最差，但硬件簡單；序列譯碼在性能和硬件方面介于維特比譯碼和門限譯碼之間。維特比譯碼和序列譯碼都是建立在最大似然譯碼原理的基礎上。下面介紹卷積碼的維特比譯碼的原理。
卷積碼網(wǎng)絡圖中共有 種狀態(tài)，每個節(jié)點（即每個狀態(tài)）有 支路引出。為簡便起見，討論K=1的情形，從全0狀態(tài)起始點開始討論。
由網(wǎng)絡圖的前N-1條連續(xù)支路構(gòu)成的路徑互不相交，即最初的 條路徑各不相同，當接收到第N條支路時，每條路徑都有2條支路延伸到第N級上，而第N級上的每兩條支路又都匯聚在節(jié)點上。在維特比譯碼算法中，把匯聚在每個節(jié)點上的兩條路徑的對數(shù)似然函數(shù)累加值進行比較，然后把具有較大對數(shù)似然函數(shù)累加值的路徑保存下來，而丟棄另一條路徑。經(jīng)挑選后第N級只留下 條幸存路徑，選出的路徑連同它們的對數(shù)似然函數(shù)累加值一起被存儲起來。由于每個節(jié)點引出兩條支路，因此以后各級中路徑的延伸都增大一倍，但比較它們的似然函數(shù)累加值后，丟棄一半，結(jié)果留存下來的路徑總數(shù)保持常數(shù)。
由此可見，上述譯碼過程中的基本操作是“加－比－選”，每級求出對數(shù)似然函數(shù)累加值，然后兩兩比較，并做出選擇。有時會出現(xiàn)兩條對數(shù)似然函數(shù)累加值相等的情況，在這種情況下可以任意選擇其中一條作為“幸存”路徑。
在每一級中都有 條幸存路徑，當序列發(fā)送完畢后，為了判斷其最后結(jié)果，就要在網(wǎng)格圖的終結(jié)處加上N-1個已知信息（即N-1條已知支路）作為結(jié)束信息。在結(jié)束信息到來時，由于每一狀態(tài)中只有與已知發(fā)送信息相符那條支路被延伸，因而在每級比較后，幸存路徑減少一半。因此，在接收到N-1個已知信息后，在整個網(wǎng)格圖中就只有唯一的一條幸存路徑保存下來。這就是譯碼所得的路徑。即在已知接收到的序列的情況下，這條譯碼路徑和發(fā)送序列是最相似的。
維特比譯碼整個過程并不復雜，譯碼器的運行是前向的，無反饋的。由于在每級中的每個狀態(tài)上要進行“加－比－選”運算，譯一個L比特的序列，譯碼操作的總次數(shù)為 ，因此譯碼器的復雜性與狀態(tài)數(shù)成正比，也是隨約束長度N的增加而呈指數(shù)增長的。因此目前只限于應用在 的卷積碼中。
上述作為結(jié)束信息的已知信息實際上就是不發(fā)生錯誤的一段信息。因此，只要差錯模式不超出卷積碼的糾錯能力，從一個節(jié)點開始分叉產(chǎn)生的各條幸存路徑經(jīng)過一段間隔后，總能正確地又合并成一條路徑。但需要經(jīng)過多長時間間隔，在何處合并，都是不確定的，與差錯模式有關(guān)。而在實際實現(xiàn)時，不可能建立這種隨機的譯碼深度，只能建立一個固定的譯碼深度。
Viterbi譯碼算法
Viterbi（維特比）算法根據(jù)可能的狀態(tài)轉(zhuǎn)移進行譯碼，狀態(tài)轉(zhuǎn)移可用網(wǎng)格圖表示，圖中狀態(tài)表示編碼器狀態(tài)，路徑狀態(tài)表示編碼器輸出符號。
Viterbi譯碼譯碼過程就是根據(jù)接收到的數(shù)據(jù)符號，按最大似然譯碼準則找出編碼器在網(wǎng)格圖上所走過的路徑。Viterbi譯碼算法的處理過程如圖6-1所示。
圖6-1 通用Viterbi譯碼算法處理流程
度量值的更改包括：
（1） 分支度量計算；
（2） 對每個新狀態(tài)，將分支度量值與舊狀態(tài)的度量值相加，得到新狀態(tài)的度量值；
（3） 選擇并保存最小度量值；
（4） 保存幸存路徑；
（5) 每收到一個符號就進行狀態(tài)轉(zhuǎn)移，Viterbi譯碼算法必須計算前一個狀態(tài)到各個新狀態(tài)的分支度量值。當采用硬判決輸入時，分支度量值可用漢明距表示；若用軟判決輸入時，用歐氏距離表示，對于編碼速率為R=1/C的卷積碼來說，其歐氏距離為
其中sdn表示接收序列，Gn(J)為網(wǎng)格圖上每個路徑狀態(tài)的期望輸入值，J是路徑指示值，C為編碼速率的倒數(shù)。將上式展開得
在進行路徑度量值比較時，可以不加以考慮。這樣省去表達式前面的負號，則在分支度量值比較時應取大值。對于編碼速率為1/2的卷積碼，
圖6-2 （2,1,3）卷積碼蝶型結(jié)構(gòu)
其分支度量值為：T=sd0×G0(J)＋sd1×G1(J)，其中sdn與Gn(J)均用雙極性表示，即0用＋1表示，而＋1用－1，在單片機編程的過程中，分別用T0到T1寄存器來表示，即T0＝＋sd0＋sd1，T1＝＋sd0－sd1。
分支度量值的更新可用如圖6-2所示蝶型結(jié)構(gòu)表示。該圖給出了從一個舊狀態(tài)到新狀態(tài)的所有可能的卷積編碼的轉(zhuǎn)移分支路徑。
用單片機AT89C2051（U402）對單片機AT89C2051（U401）輸出的卷積編碼序列進行譯碼，如圖6-3所示。卷積編碼序列DATA1（無誤碼）或DATA2（有一位誤碼）從U402的T1引腳串行輸入，由開關(guān)K401決定接收哪種編碼序列，信號波形見TP404，單片機U402對輸入的卷積編碼序列進行維特比譯碼后，從DATA4（RXD引腳，波形見TP405）串行輸出，并從P1口并行輸出，使發(fā)光二極管（D0－D7）顯示8位譯碼輸出序列。
圖6-3 用單片機AT89C2051進行維特比譯碼電路圖
三、實驗內(nèi)容
1.設置撥線開關(guān)。
把撥線開關(guān)（SW401）的第1-8設置輸入序列為0DCH。設置撥線開關(guān)的第9位狀態(tài)為1（即開關(guān)撥上），不產(chǎn)生誤碼，因此DATA1（TP402）和DATA2（TP403）的信號是一樣的，用雙蹤示波器觀察。
2. 用發(fā)光二極管觀察譯碼輸出的結(jié)果
把跳線器插在K401的1、2兩端或2、3兩端，使譯碼器U402（見TP404）接收的是無誤碼的卷積編碼序列DATA1（波形見TP402，無誤碼）信號或DATA2（波形見TP403，插入誤碼）信號；觀察發(fā)光二極管（D0－D7）顯示的8位譯碼輸出序列是什么（燈亮為1，滅為0），與撥線開關(guān)（SW401）的第1-8設置的輸入序列是否一致，對比測量點TP401與TP405的波形。
當把撥線開關(guān)（SW401）的第1-8設置的輸入序列分別為
（1） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
讀出發(fā)光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關(guān)（SW401）設置的輸入序列是否一致。同時用雙蹤示波器觀察和記錄DATA1（波形見TP402）和DATA2（波形見TP403）的卷積編碼信號。
3. 用雙蹤示波器觀察譯碼輸出的結(jié)果
設置撥線開關(guān)的第9位狀態(tài)為1（即開關(guān)撥上），不產(chǎn)生誤碼，把跳線器插在K401的1、2兩端或2、3兩端，使U402接收的是無誤碼的卷積編碼序列DATA1信號或DATA2信號；當把撥線開關(guān)（SW401）的第1-8設置的輸入序列為
（2） 1EH；（2）37H；（3）56H；（4）78H；（5）9CH等
用雙蹤示波器的兩個探頭分別接在DATA3（TP401，原始數(shù)字序列輸入）和DATA4（TP405，譯碼還原數(shù)字序列輸出），觀察譯碼輸出序列與輸入序列是否一致。
4. 觀察對有誤碼的卷積編碼序列的維特比譯碼。
把撥線開關(guān)（SW401）的第1-8設置輸入序列為0DCH。設置撥線開關(guān)的第9位狀態(tài)為0（即開關(guān)撥下），產(chǎn)生誤碼。用雙蹤示波器觀察和記錄DATA1和DATA2的卷積編碼信號。
把跳線器插在K401的2、3兩端，使U402接收的是有誤碼的卷積編碼序列DATA2信號；讀出發(fā)光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關(guān)（SW401）設置的輸入序列是否一致。
當把撥線開關(guān)（SW401）的第1-8設置的輸入序列分別為
（3） 00H；（2）7FH；（3）80H；（4）4BH；（5）0FFH等
讀出發(fā)光二極管（D0－D7）顯示的8位譯碼輸出序列是什么，與撥線開關(guān)（SW401）設置的輸入序列是否一致。用雙蹤示波器的兩個探頭分別接在DATA3（TP401，原始數(shù)字序列輸入）和DATA4（TP405），譯碼還原數(shù)字序列輸出），觀察譯碼輸出序列與輸入序列是否一致。
四、實驗報告要求
1. 掌握差錯控制編碼的基本概念
2. 掌握維特比譯碼的原理和算法
3. 畫出各點波形，并做簡要的說明