1 Viterbi譯碼算法

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




        該算法思想是：計(jì)算網(wǎng)格圖上在時(shí)刻L到達(dá)各個(gè)狀態(tài)的路徑和接收序列之間的相似度,；在形成的多條路徑中,，去除不可能成為最大似然選擇對(duì)象的網(wǎng)格圖上的路徑， 即,，如果有兩條路徑到達(dá)同一狀態(tài),，則具有最佳量度的路徑被選中，稱為幸存路徑,。對(duì)所有狀態(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個(gè)前狀態(tài),，其對(duì)應(yīng)的碼字是(i,，j)。

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



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

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

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

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



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

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

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


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

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

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

4 結(jié)語

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