1 Viterbi譯碼算法

Viterbi 譯碼算法由維特比在1967年提出。Viterbi譯碼算法實(shí)質(zhì)上是最大似然譯碼，他巧妙利用編碼網(wǎng)格圖的特殊結(jié)構(gòu)，從而降低計算的復(fù)雜性。例如圖1即為 (2，1，2)卷積碼的網(wǎng)格圖。這里(n，k，m)分別指碼組寬度n，信息元個數(shù)k和編碼存儲度m，稱m+1=N為編碼約束度。




        該算法思想是：計算網(wǎng)格圖上在時刻L到達(dá)各個狀態(tài)的路徑和接收序列之間的相似度；在形成的多條路徑中，去除不可能成為最大似然選擇對象的網(wǎng)格圖上的路徑， 即，如果有兩條路徑到達(dá)同一狀態(tài)，則具有最佳量度的路徑被選中，稱為幸存路徑。對所有狀態(tài)都將進(jìn)行這樣的路徑選擇操作，譯碼器不斷在網(wǎng)格圖上深入，通過去 除可能性最小的路徑實(shí)現(xiàn)判決。

Viterbi譯碼算法步驟如下：

(1)用數(shù)組p(i，j)，c(i，j)描述網(wǎng)格圖結(jié)構(gòu)。p(i，j)表示到達(dá)狀態(tài)i的第j個前狀態(tài)，其對應(yīng)的碼字是(i，j)。

(2)計算第L時刻接收碼RL相對于各碼字睜相似度，亦稱作分支量度BM(Branch Metric)。



(3)計算第L時刻到達(dá)狀態(tài)i的最大似然路徑之相似度，也即路徑量度PM(Path Metric)。

(4)譯碼輸出并更新第L時刻、狀態(tài)i對應(yīng)的幸存路徑。具體步驟是：

①將到達(dá)狀態(tài)i的最大似然路徑的前狀態(tài)j所對應(yīng)幸存路徑作為本時刻狀態(tài)i的幸存路徑，即SL(i)=SL-1(j)；
②選擇具有最小(最似然)PM那個狀態(tài)對應(yīng)的幸存路徑最舊的碼字作為譯碼輸出；
③將各狀態(tài)幸存路徑最舊的碼字從各移存器移出，再將到達(dá)各狀態(tài)的最大似然路徑在時刻L所對應(yīng)的碼字從移位寄存器的輸入端移入幸存路徑SL(i)。
2 FPGA編譯碼器
       編碼器結(jié)構(gòu)比較簡單，其所選用的系列器件可選性較大，這里選用Altera公司MAX7000器件系列，他的制造工藝是E2PROM，集成度(邏輯門數(shù))為600～10000，管腳延時為6 ns，工作頻率可以達(dá)到151.5 MHz。譯碼器的整體結(jié)構(gòu)相對要復(fù)雜一些，因此所選用的系列器件要求較高，本文選用Altera公司FLEX10K器件系列，他的制造工藝是SRAM，集成度(邏輯門數(shù))為1萬～25萬。

下面以(2，1，2)卷積碼為例進(jìn)行設(shè)計，如圖2所示。



          采用VHDL語言進(jìn)行編程設(shè)計，經(jīng)Max+PlusⅡ編譯、仿真，結(jié)果如圖3所示。圖3(a)中D為原始比特信息，Z為編碼輸出；圖3(b)中A為接收碼，Y為糾錯譯碼，D為譯碼輸出。對比知該譯碼器實(shí)現(xiàn)了正確譯碼。

3譯碼器性能分析
        對于(n，k，m)卷積碼，其編碼存儲度(移位寄存器單元的數(shù)量)為m，幸存路徑有2m條。每條幸存路徑(或信息序列)存儲器單元數(shù)是n*D，其中，n是 卷積碼碼組寬度，D是需要存儲的碼組的個數(shù)。D的取值一般考慮取m的整倍數(shù)，稱D為幸存路徑長度。編碼存儲度和幸存路徑長度的取值問題關(guān)系到芯片規(guī)格、傳 輸時延等問題。若D很大，則譯碼器的存儲量太大而難以實(shí)用。一般情況下，當(dāng)譯碼進(jìn)行到第5級(每級包括m個時刻)以后，每個狀態(tài)幸存路徑的前幾個分支已基 本重合在一起，這就是說每個路徑存儲器不必存儲D個很大的碼序列。譯碼時，當(dāng)譯碼器接收并處理完第D個碼組后，譯碼器中的幸存路徑存儲器已全部存滿，當(dāng)譯 碼器開始處理第D+1個碼組時，他就對幸存路徑存儲器中的最頂端的碼組做出判決并輸出。
按照上述Viterbi譯碼步驟，采用Matlab仿真，在AWGN信道下，當(dāng)D取m的2～9倍時，即D=N*m，N=2，3，…，9，得(2，1，2)卷積碼的傳輸性能如圖4所示。

      當(dāng)編碼存儲度增加時，卷積碼譯碼性能也有所提高。依照上述編譯碼過程，得出(2，1，3)卷積碼的傳輸性能如圖5所示。


        對比仿真結(jié)果圖4與圖5，可得出如下結(jié)論：
(1)適當(dāng)增加幸存路徑的長度可以提高譯碼器的糾錯能力。圖4中N值由2遞增到9的過程中，其誤比特率逐漸降低。

(2)幸存路徑的長度在增加到一定值時，譯碼器糾錯能力趨于穩(wěn)定。當(dāng)N值增加到6以上，誤比特率降低幅度大為減小，曲線有合二為一的趨勢。因此，可以認(rèn)為幸存路徑長度D取編碼存儲度的6倍以上就可以取得比較好的譯碼性能。

(3) 增加寄存器數(shù)目(即編碼存儲度m)可以適當(dāng)提高譯碼性能。圖3(a)與圖3(b)中寄存器數(shù)目分別為2和3，對比兩圖可知，在N值和信噪比取值相同的情況 下，后者的誤比特率較低。需要說明的一點(diǎn)是，編碼存儲度m取值不宜過大，在Viterbi譯碼過程中，他將分別對應(yīng)2m個狀態(tài)、路徑量度和2m條幸薦路 徑，譯碼器存儲單元與計算量將隨m成指數(shù)地增加。Odenwalder給出的常用卷積碼的短編碼存儲度為2～7。

4 結(jié)語

       本文探討了廣泛用于遠(yuǎn)距離實(shí)時通信的卷積碼Viterbi譯碼器的實(shí)現(xiàn)及其傳輸性能。采用硬件描述語言VHDL和Altera公司高FPGA芯片使方案設(shè) 計具有較強(qiáng)的靈活性。本文對譯碼算法中幸存路徑長度和編碼存儲度參數(shù)的取值問題給出了比較合理的結(jié)果，在卷積碼編譯碼設(shè)計中具有較好的指導(dǎo)性和實(shí)用性。