通過Viterbi譯碼算法實現(xiàn)譯碼器優(yōu)化實現(xiàn)方案

1 引 言

由于卷積碼優(yōu)良的性能，被廣泛應用于深空通信、衛(wèi)星通信和2G、3G移動通信中。卷積碼有三種譯碼方法：門限譯碼、概率譯碼和Viterbi算法，其中Viterbi算法是一種基于網(wǎng)格圖的最大似然譯碼算法，是卷積碼的最佳譯碼方式，具有效率高、速度快等優(yōu)點。從工程應用角度看，對Viterbi譯碼器的性能*價指標主要有譯碼速度、處理時延和資源占用等。本文通過對Viterbi譯碼算法及卷積碼編碼網(wǎng)格圖特點的分析，提出一種在FPGA設計中，采用全并行結(jié)構(gòu)、判決信息比特與路徑信息向量同步存儲以及路徑度量最小量化的譯碼器優(yōu)化實現(xiàn)方案。測試和試驗結(jié)果表明，該方案與傳統(tǒng)的譯碼算法相比，具有更高的速度、更低的時延和更簡單的結(jié)構(gòu)。

2 卷積編碼網(wǎng)格圖特點

圖1所示為卷積編碼網(wǎng)格圖結(jié)構(gòu)，圖中每一狀態(tài)有兩條輸入支路和兩條輸出支路。

2.1 輸入支路的特點

任意一個狀態(tài)節(jié)點Si都有兩條輸入支路，且這兩條輸入支路對應的源節(jié)點分別為：

此外，i為偶數(shù)時，兩條輸入支路的輸入信息都為‘1’；i為奇數(shù)時，兩條輸入支路的輸入信息都為‘0’。

2.2 輸出支路的特點

任意一個狀態(tài)節(jié)點Si都有兩條輸出支路，且兩條輸出支路對應的目的節(jié)點分別為：

此外，目的節(jié)點是Sj1的輸出支路對應的輸入信息都為‘0’；目的節(jié)點是Sj2的輸出支路對應的輸入信息都為‘1’。

3 Viterbi譯碼器的優(yōu)化算法

3.1 判決信息比特與路徑信息向量同步存儲算法

由網(wǎng)格圖的輸入支路特點分析可知，產(chǎn)生任意一個狀態(tài)節(jié)點Si的輸入條件mi是確定的，即mi=‘1’，i為偶數(shù)；mi=‘0’，i為奇數(shù)。輸入條件mi表示譯碼器最終需要輸出的比特信息。此外，譯碼器所要找的留選路徑是不同狀態(tài)的組合。對于(2，1，6)卷積碼而言，具有2m=26=64(m為編碼存儲)個不同狀態(tài)，可以用6位比特向量來表示所有的狀態(tài)。將mi作為最高位加在狀態(tài)向量上，用7位比特向量同時表示每一狀態(tài)和對應的輸入支路的譯碼信息，這樣在譯碼器回溯時就可以直接輸出存儲向量的高位作為譯碼器的輸出。采用這種方法大大降低了回溯路徑和譯碼器判決的難度，由此降低了譯碼器結(jié)構(gòu)的復雜性。

3.2 全并行結(jié)構(gòu)設計

全并行結(jié)構(gòu)Viterbi譯碼器的特點是所有狀態(tài)的路徑度量計算或路徑存儲同時進行。其中，路徑度量包括兩條輸出支路和兩條輸入支路的度量，路徑存儲包括狀態(tài)向量存儲和譯碼比特信息存儲。因此，在(2，1，6)卷積碼的全并行譯碼器的FPGA設計中，一個時鐘周期內(nèi)需要實現(xiàn)2×n×2m=256次路徑度量運算和2m=64次7比特向量存儲操作。

全并行結(jié)構(gòu)對每一個狀態(tài)都具有獨立的處理單元，互不影響，同時工作，比起傳統(tǒng)的串行結(jié)構(gòu)，大大提高了譯碼速度。并且由于在FPGA中，有著海量的獨立邏輯單元(LCs)和豐富的分布式存儲資源(RAM)，全并行結(jié)構(gòu)設計正好可以發(fā)揮FPGA的這一優(yōu)勢。

3.3 路徑度量的最小量化算法

隨著網(wǎng)格圖的行進，每個狀態(tài)輸出支路的路徑度量會不斷增加，度量值所需量化位寬越來越大，導致存儲資源的增加。為了降低路徑度量存儲單元的大小，節(jié)約存儲資源，設計中采用了路徑度量的最小量化算法。在每次路徑度量運算時，將各狀態(tài)的度量值減去上一次各狀態(tài)留選路徑度量值的最小值。即需要保存的路徑度量值只是各狀態(tài)度量與最小度量的差值，從而達到減少度量值量化的位寬。

對于(2，1，m)卷積碼，每次計算出的路徑度量最大值與最小值之差不超過2×m，所以，路徑度量的量化寬度為log2(2m)。對于(2，1，6)卷積碼，存儲路徑度量的寄存器位寬為log2(2×6)=4。

4 FPGA實現(xiàn)及驗證

4.1 FPGA實現(xiàn)的整體框架

采用Altera公司的QuartusⅡ為開發(fā)工具，以EPlS25的FPGA為驗證平臺，用于設計和驗證本文提出的Viterbi優(yōu)化譯碼算法，譯碼器整體設計框架如圖2所示。譯碼器結(jié)構(gòu)主要包括時鐘單元、主控單元、全并行ACS單元、回溯單元及譯碼輸出單元。

(1)時鐘單元

用于把板級時鐘經(jīng)過鎖相環(huán)分頻獲得譯碼器所需的工作時鐘。

(2)主控單元

給出各種控制信號，控制其他各單元的工作時序，保證譯碼器各模塊協(xié)調(diào)工作。

(3)支路度量與全并行ACS單元

由64個具有相同結(jié)構(gòu)和功能的支路度量與全并行ACS構(gòu)成，用于計算和比較每條支路的度量，選出并保存度量值最小的路徑供回溯單元使用，存儲路徑包括表示狀態(tài)的6位信息向量和對應的譯碼信息比特mi。由于(2，1，6)卷積碼的譯碼深度D=5(m+1)=35，為保證存儲單元寫操作與回溯單元讀操作同步進行，將存儲單元分為兩個部分做流水線處理，因此存儲單元大小應有2×D×(m+1)×2m=31 360 b。

(4)回溯單元

用于在譯碼深度到達時刻，根據(jù)各狀態(tài)ACS單元選出的留選路徑，判斷度量最小的留選路徑，并從這條路徑對應的狀態(tài)開始向前尋找，直到找完前面所有狀態(tài)，同時把從存儲單元中讀出的譯碼信息比特mi送給譯碼輸出單元。

(5)譯碼輸出單元

將回溯單元送出的反序譯碼信息按正序輸出，用RAM實現(xiàn)。即先將比特信息按順序?qū)懭隦AM，待一段信息寫完后再按反序讀出。為了保證本段反序讀操作與下一段順序?qū)懖僮魍瑫r進行，將RAM分為兩部分做流水線處理。每段信息流的長度為譯碼深度，因此流水線RAM的大小為2×D=70 b。

4.2 設計驗證

為了驗證本文提出的Viterbi優(yōu)化譯碼算法，編寫了圖3所示的驗證框圖。包括一個信源產(chǎn)生模塊、一個卷積碼編碼模塊、一個偽隨機序列發(fā)生模塊以及誤碼統(tǒng)計模塊。在編碼器輸出中加上偽隨機序列模擬的噪聲構(gòu)成有擾譯碼輸入信息，用于驗證譯碼器的糾錯性能。

通過QuartusⅡ軟件內(nèi)嵌的signalTap及JTAG下載線在EPlS25的FPGA上的在線測試，得到時序圖如圖4所示。

圖中，信號量BER是誤碼統(tǒng)計模塊統(tǒng)計的誤碼數(shù)，在Viterbi譯碼能力范圍內(nèi)，其值始終為0，這就驗證了譯碼器的譯碼功能。通過測試與比較性能指標得到以下結(jié)果：

(1)譯碼器速度

通過在FPGA開發(fā)板中的實際運行，譯碼器輸出的比特速率可達90 Mb／s。這與QuartusⅡ提供的Viterbi譯碼器IP核的parallel結(jié)構(gòu)相當，而比其hybrid結(jié)構(gòu)的譯碼速度快十幾倍。

(2)譯碼器時延

本方案的譯碼器時延大小主要取決于譯碼深度D。(2，1，6)卷積碼的譯碼深度為D=35，回溯單元處理時間和D相同；同時，回溯前最小度量的判斷時間為(m-1)，所以從譯碼輸入到譯碼輸出的總延時為2×D+(m-1)=75，這比起采用QuartusⅡ提供的Viterbi譯碼器IP核(延時為170)縮短了一半以上。

(3)譯碼器資源

QuartusⅡ軟件的資源分析綜合報告如圖5所示，主要消耗的資源為LEs：2 339，占整個芯片邏輯資源的9％；RAM：31 430，占整個芯片RAM資源的2％。因此，本方案對資源的需求是很少的。這與QuartusⅡ提供的3.2版本的Viterbi譯碼器IP核相當，而比4.2版本的Viterbi節(jié)省1 000多個邏輯資源。

5 結(jié) 語

通過對Viterbi譯碼算法及卷積碼編碼網(wǎng)格圖特點的深入分析，提出一種采用全并行結(jié)構(gòu)、判決信息比特與路徑信息向量同步存儲以及路徑度量最小量化算法的譯碼器優(yōu)化實現(xiàn)方案。測試和試驗結(jié)果表明，在不降低譯碼器性能的前提下，能提高譯碼速度、降低譯碼器的資源消耗和時延、簡化譯碼器結(jié)構(gòu)。