一、實(shí)驗(yàn)?zāi)康?br /> 1.了解維特比譯碼的原理
2.了解維特比譯碼的算法

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

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

度量值的更改包括：
（1） 分支度量計(jì)算；
（2） 對(duì)每個(gè)新?tīng)顟B(tài)，將分支度量值與舊狀態(tài)的度量值相加，得到新?tīng)顟B(tài)的度量值；
（3） 選擇并保存最小度量值；
（4） 保存幸存路徑；
（5) 每收到一個(gè)符號(hào)就進(jìn)行狀態(tài)轉(zhuǎn)移，Viterbi譯碼算法必須計(jì)算前一個(gè)狀態(tài)到各個(gè)新?tīng)顟B(tài)的分支度量值。當(dāng)采用硬判決輸入時(shí)，分支度量值可用漢明距表示；若用軟判決輸入時(shí)，用歐氏距離表示，對(duì)于編碼速率為R=1/C的卷積碼來(lái)說(shuō)，其歐氏距離為
      

其中sdn表示接收序列，Gn(J)為網(wǎng)格圖上每個(gè)路徑狀態(tài)的期望輸入值，J是路徑指示值，C為編碼速率的倒數(shù)。將上式展開(kāi)得
   

在進(jìn)行路徑度量值比較時(shí)，可以不加以考慮。這樣省去表達(dá)式前面的負(fù)號(hào)，則在分支度量值比較時(shí)應(yīng)取大值。對(duì)于編碼速率為1/2的卷積碼，
     

圖6-2 （2,1,3）卷積碼蝶型結(jié)構(gòu)

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



圖6-3 用單片機(jī)AT89C2051進(jìn)行維特比譯碼電路圖

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

四、實(shí)驗(yàn)報(bào)告要求
1. 掌握差錯(cuò)控制編碼的基本概念
2. 掌握維特比譯碼的原理和算法
3. 畫(huà)出各點(diǎn)波形，并做簡(jiǎn)要的說(shuō)明