1 Viterbi譯碼算法

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




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

Viterbi譯碼算法步驟如下：

(1)用數組p(i，j)，c(i，j)描述網格圖結構。p(i，j)表示到達狀態i的第j個前狀態，其對應的碼字是(i，j)。

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



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

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

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

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



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

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

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


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

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

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

4 結語

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