通過采用FPGA器件設(shè)計一個Viterbi譯碼器

卷積碼是廣泛應(yīng)用于衛(wèi)星通信、無線通信等各種通信系統(tǒng)的信道編碼方式。Viterbi算法是一種最大似然譯碼算法。在碼的約束度較小時，它比其它概率譯碼算法效率更高、速度更快，譯碼器的硬件結(jié)構(gòu)比較簡單。隨著可編程邏輯技術(shù)的不斷發(fā)展，其高密度、低功耗、使用靈活、設(shè)計快速、成本低廉、現(xiàn)場可編程和反復(fù)可編程等特性，使FPGA逐步成為Viterbi譯碼器設(shè)計的最佳方法。項(xiàng)目目的是用FPGA實(shí)現(xiàn)一個Viterbi譯碼器。

一、譯碼器功能分析

譯碼器是一種具有“翻譯”功能的邏輯電路，這種電路能將輸入二進(jìn)制代碼的各種狀態(tài)，按照其原意翻譯成對應(yīng)的輸出信號。Viterbi譯碼器是以Viterbi算法為基礎(chǔ)設(shè)計的一種譯碼器，譯碼器主要由五部分組成：分支度量單元（Branch Metric Unit）、加比選單元（Add-Compare-Select Unit）、幸存路徑管理單元（Survivor Management Unit）、判輸出單元（Decide-Output Unit）和控制單元（Control Unit）。其整體結(jié)構(gòu)如圖1。

圖1 譯碼器結(jié)構(gòu)框圖

各單元之間的相互關(guān)系如下：接收到的輸入數(shù)據(jù)首先被送入各分支度量單元中計算出相應(yīng)的分支路徑距離;加比選單元將舊的狀態(tài)路徑度量與相應(yīng)的新產(chǎn)生的分支路徑距離相加，通過比較后選擇到達(dá)同一狀態(tài)的兩個路徑度量值中較小的分支來更新路徑度量;溢出處理防止加比選單元中的路徑度量累加值發(fā)生溢出;幸存路徑管理單元將加比選單元生成的路徑信息進(jìn)行存儲管理;判決輸出單元根據(jù)加比選單元選擇的路徑度量，從中選擇一個最小值，并輸出該最小值對應(yīng)的幸存路徑。所有這些單元都在控制單元的協(xié)調(diào)下工作。

1 分支度量單元

分支度量表征該分支接收到的碼元與期望碼元之間的差別。對于硬判決，這種差別指不同碼元的個數(shù)。硬判決分支度量值可以表示為：

（式1）

其中，y為接收碼字，c為本地卷積碼輸出碼字。對于碼率為1/2硬判決譯碼方式，編碼器輸出信號可能為00、01、10、11，其路徑度量取值（漢明距離）只有0、1、2三種可能，因此需要用一個2bit的寄存器來存儲分支度量值。

在本文中，采用了4個ACS單元（每個ACS單元有兩個累加器）并行計算，因此需要8個分支度量單元并行計算8個條支路的度量值，并將度量值送至ACS中的累加器。

2 加比選單元

ACS單元用來累加路徑度量值并比較和選擇進(jìn)入某一狀態(tài)的兩條分支。本文中采用4個ACS單元并行計算，每16個狀態(tài)復(fù)用一個ACS結(jié)構(gòu)，同時兼顧了面積和速度。

圖 2 （2，1，7）卷積碼的狀態(tài)圖

譯碼器的核心部分是ACS單元，傳統(tǒng)的譯碼器結(jié)構(gòu)每產(chǎn)生一位譯碼需要進(jìn)行2（n-1）次加比選運(yùn)算，即2×2（n-1）=2n次加法運(yùn)算和2（n-1）次比較選擇運(yùn)算。對于（2，1，7）卷積碼來說，需要進(jìn)行128加法運(yùn)算和64次比較選擇運(yùn)算，這將占用很多的資源并產(chǎn)生很大的功耗，因此，如果能夠通過改進(jìn)ACS單元的結(jié)構(gòu)來降低其規(guī)模和功耗，將會使整個譯碼器的硬件規(guī)模和功耗大大降低。

從圖2所示的（2，1，7）卷積碼的狀態(tài)圖中可以看出：在T（i+1）時刻到達(dá)狀態(tài)S0和S1的是T（i）時刻的狀態(tài)S0和S32，……，在T（i+1）時刻到達(dá)狀態(tài)S62和S63的是T（i）時刻的狀態(tài)S31和S63。也就是說，T（i）時刻的狀態(tài)Sj和Sj+32會達(dá)到T（i+1）時刻的相鄰的兩個狀態(tài)，并且這兩個狀態(tài)是S2j和S2j+1（31≥j≥0）。這也就是圖形單（ButterfllyUnit）。

圖3 基二蝶形單元

在圖3中，T（i）時刻的狀態(tài)Sj和Sj+32都是在輸入0的時候轉(zhuǎn)移到T（i+1）時刻的狀態(tài)S2j，在輸入1的時候轉(zhuǎn)移到T（i+1）時刻的狀態(tài)S2j+1。這也就意味著ACS單元中的比較器所比較的兩個路徑度量值（BM）來自數(shù)值上相差32的兩個狀態(tài)。路徑度量的計算就是分支度量加上與這條分支相連的前一時刻的狀態(tài)選擇的路徑度量，所以，新狀態(tài)的路徑度量為：

（式2）

（式3）

從以上的分析中我們可以得出一個很重要的結(jié)論：從T（i）時刻的狀態(tài)Sj（2（n-1）≥j≥0）生成的兩條支路，唯一不同的信息就是該時刻狀態(tài)Sj的輸入數(shù)據(jù)，Sj的上支路輸入的是0，下支路輸入的是1。因此，一個狀態(tài)可以只生成一條支路（上支路），另一條支路（下支路）的信息已經(jīng)包括在這條支路中，要恢復(fù)出下支路只需要將上支路的輸入數(shù)據(jù)取反即可。圖4.2所示的ACS單元結(jié)構(gòu)中的累加器可以減少一半的工作量，對于本文中的（2，1，7）卷積碼的譯碼器，即由每產(chǎn)生一位譯碼工作16個時鐘周期減少為8個時鐘周期（可將時鐘頻率降為原來的1/2），減少了復(fù)用次數(shù)，降低了ACS單元的復(fù)雜度和功耗。同時，由于ACS單元結(jié)構(gòu)的優(yōu)化，每個狀態(tài)只需要生成一條路徑，存儲的幸存路徑數(shù)也由原來的128條減少為64條，也同樣使結(jié)構(gòu)變得簡單，功耗有所降低。

本文引用地址：http://www.eepw.com.cn/article/265114.htm

由式（2）和式（3）可知，輸入數(shù)據(jù)（datain）不同，卷積碼的輸出C0和C1也不同，因此，同一狀態(tài)上支路的輸出與下支路不同，上下支路狀態(tài)輸出及譯碼器的輸入數(shù)據(jù)之間的關(guān)系如表1所示：

利用上下支路分支度量值的關(guān)系就可以從上支路路徑度量累加值中計算出下支路路徑度量累加值，用Verilog HDL語言描述為：

case（up_branch_metric）

2‘b00： down_path_add_metric 《= up_path_add_metric + 2’b10;

2‘b01： down_path_add_metric 《= up_path_add_metric;

2’b10： down_path_add_metric 《= up_path_add_metric-2‘b10;

default： down_path_add_metric 《= 7’bxxx_xxxx;

endcase

另外，ACS單元中的累加器可以用超前進(jìn)位加法器實(shí)現(xiàn)，這將使累加器不會成為速度的瓶頸。由于累加器使用固定長度的寄存器（本文中采用7bit的寄存器），因此在不斷累加過程中可能會發(fā)生溢出，影響譯碼結(jié)果。解決溢出常用的方法是到達(dá)譯碼深度時從所有狀態(tài)的路徑度量值中減去最小度量值。

3 幸存路徑管理單元

幸存路徑管理單元用來完成對幸存路徑的記錄，處理ACSU輸出的信息，為輸出判決作準(zhǔn)備。SMU的實(shí)現(xiàn)主要有Register Exchange （寄存器交換）和Trace Back（回溯）兩種算法。由于寄存器交換算法比回溯有更小的譯碼延時，RE法中幸存路徑寄存器記錄了幸存路徑所對應(yīng)的解碼信息，也就是譯碼輸出。采用這種方法消除了根據(jù)當(dāng)前狀態(tài)往前追蹤的必要，因此寄存器交換提供了一種速度很高的譯碼操作。

4 判決輸出單元

判決輸出單元（DOU）由兩部分組成：最小值選擇單元（MNSU:Minimum Number Select Unit）和譯碼輸出單元（DOU:Decode Output Unit）。最小值選擇單元是用來選出本文中前面4個ACS單元輸?shù)穆窂蕉攘恐抵芯哂凶钚《攘恐档墓?jié)點(diǎn)， 讀取該結(jié)點(diǎn)保存的幸存路徑，供譯碼輸出單元輸出譯碼值。判決輸出單元的結(jié)構(gòu)如圖4所示：

圖4 判決輸出單元結(jié)構(gòu)圖

5 控制單元

控制單元（CU）產(chǎn)生控制各模塊的時鐘信號，是所有模塊的有序運(yùn)行的基礎(chǔ)。各時鐘信號功能如下：clk_load用于讀取前一時刻各狀態(tài)寄存器的內(nèi)容，并產(chǎn)生各狀態(tài)上支路的狀態(tài)輸出值;clk_BM用于計算各狀態(tài)上支路的分支度量值并讀取前一時刻各狀態(tài)的路徑度量值;clk_Add用于計算各狀態(tài)上支路的路徑度量值;clk_restore用于暫存各狀態(tài)上支路度量值并恢復(fù)相應(yīng)狀態(tài)下支路的路徑度量值;clk_C_S用于比較并選擇達(dá)到同一狀態(tài)的兩支路的路徑度量值的較小者，并存儲各狀態(tài)選擇的幸存路徑;clk_MNS用于選擇各狀態(tài)存儲的路徑度量值中的最小值，并保存該最小值對應(yīng)的狀態(tài);min_sel_1和min_sel_2分兩步選擇4個MNSU選擇結(jié)果的最小值，并選出最終的最小值對應(yīng)的狀態(tài);Decode_Output用于讀取該最小值對應(yīng)狀態(tài)存儲的幸存路徑，并輸出譯碼結(jié)果。

二、項(xiàng)目實(shí)施方案

Viterbi譯碼器大致可以分為四個部分：支路度量模塊（BMU）、加比選模塊（ACS）、幸存路徑管理模塊（SMU）和輸出產(chǎn)生模塊。其 中支路度量模塊用于完成譯碼器輸入信號與網(wǎng)格圖上的可能路徑信號的分支度量計算;加比選模塊主要把前一個狀態(tài)的路徑度量與當(dāng)前輸入信號的分支度量相加，以得到該分支的路徑度量，然后比較不同分支路徑度量的大小，同時找出最小的度量值，并更新該狀態(tài)的度量值，最后輸出狀態(tài)轉(zhuǎn)移信息;路徑管理模塊可對加比選單 元輸出的狀態(tài)轉(zhuǎn)移信息進(jìn)行處理，以便為輸出判決做準(zhǔn)備。輸出模塊可根據(jù)幸存路徑管理單元的輸出進(jìn)行輸出判決，最后輸出譯碼信息。Viterbi譯碼器基本原理框圖如下所示。