基于FPGA的卷積編譯碼器的設計與實現

劉楊，章敏

（桂林電子科技大學 廣西 桂林 541004）

卷積碼是Elias在1955年最早提出的，稍后，Wozencraft在1957年提出了一種有效譯碼方法，即序列譯碼。Massey在1963年提出了一種性能稍差，但比較實用的門限譯碼方法，由于這一實用性進展使卷積碼從理論走向實用。而后Viterbi在1967年提出了最大似然譯碼法，該方法對存儲器級數較小卷積碼的譯碼很容易實現，并具有效率高、速度快、譯碼器簡單等特點，人們后來稱其為維特比算法或維特比譯碼，廣泛應用于現代通信中。本文主要論述了基于Xilinx公司的FPGA的卷積編碼器及相應的維特比譯碼器的研究，并在幸存路徑存儲與譯碼輸出判決方面提出了改進算法，從而使譯碼器結構得到簡化。

1 卷積碼的編碼原理與實現

卷積碼是一種重要的前向糾錯編碼 FEC，用（n，k，m）表示，分組碼不同，其監督元與本組的信息元和前若干組的信息元有關。這種編碼的糾錯能力強，不僅可糾正隨機差錯，而且可糾正突發差錯。卷積碼根據需要，有不同的結構及相應的糾錯能力，但都有類似的編碼規律。卷積碼的編碼器是一個具有k個輸入位（端）、n個輸出位（端），m級移位寄存器的有限狀態記憶系統，通常稱為時序網絡。其中R=k/n為編碼效率，m為約束長度。卷積碼編碼原理如圖1所示。

圖1卷積碼編碼器原理圖Fig.1 Principle diagram of convolutional encoder

卷積編碼充分利用各組信息元之間的相關性，在誤碼率和復雜度相同的情況下性能優于分組碼，并且最佳譯碼更易實現，因此在通信系統中得到廣泛應用。但是卷積碼沒有嚴格的代數結構，尚未找到嚴密的數學手段將糾錯性能與碼的構成有規律地聯系起來，目前大都采用計算機搜索好碼。通常是（2，1，3）卷積碼，本文以生成多項式 G=（111，101）的（2，1，3）卷積碼為例介紹設計和實現過程。

設初始狀態為S0編碼為00，根據生成矩陣分別帶入輸入0和輸入1時得到下一個狀態和相應輸出。依次代入，可得到如圖2所示的狀態圖。

圖2編碼器狀態圖Fig.2 State diagram of encoder

描述卷積碼的方法主要有兩類[1]：圖解表示和解析表示。上文提到的生成多項式G=（111，101）即是解析表示。卷積碼的圖解表示又可分為樹狀圖、網格圖和狀態圖3種。下面介紹常用的樹狀圖表示（網格圖表示將在譯碼部分介紹）。在圖2所示的卷積編碼樹狀圖中，假設移位寄存器的起始狀態全為0，當第1個輸入比特為0時，輸出比特為00；若輸入比特為1時，則輸出比特為11。隨著第2個比特輸入，第1個比特右移1位，此時輸出比特同時受當前輸入比特和第1個輸入比特的影響。第3個比特輸入時，第1、2比特分別右移1位，同時輸出2個由這3位移位寄存器存儲內容所共同決定的比特。當第4個比特輸入時，第1個比特移出移位寄存器而消失。移位過程可能產生的各種序列如圖3中的二叉樹。

圖3 （2，1，3）卷積碼的樹狀圖表示Fig.3 Tree diagram of（2,1,3）convolutional codes

2 Veterbi（維特比）譯碼器原理

卷積碼的譯碼方式有3種：Veterbi譯碼、門限譯碼和序列譯碼。其中維特比譯碼具有最佳譯碼性能，但硬件實現相對復雜。veterbi算法是檢測離散馬兒可夫過程有限狀態序列的優化算法[4]。在數字通信系統中，前向糾錯卷積碼編碼和維特比譯碼用來提高系統性能，應用廣泛。

維特比算法是一種最大似然譯碼算法。它不是在網格圖上一次比較所有可能的2條完整路徑，而是接收一段，計算比較一段，選擇一段最有可能的碼段，從而達到整個碼序列是一個有最大似然函數的序列。其基本原理是：以斷續的接收碼流為基礎，逐個計算它與其他所有可能出現的連續的格狀圖路徑的距離，選出其中概率最大的一條作為譯碼輸出。

維特比（Veterbi）譯碼算法是基于卷積碼的網格圖表示中路徑的計算，其核心思想就是通過計算路徑矢量進而尋找最短路徑從而最終得到譯碼序列并可以糾正傳輸過程中的錯誤碼字。 圖4中給出（2，1，3）卷積碼的網格圖表示[1-2]。

圖 4中的網格圖中共有 2k（N-1）種狀態，每個狀態（節點）有2k條支路進入，同時也有2k條支路引出。由于本文討論的是（2，1，3）卷積碼的情況，因此 k=1,假設起始狀態為全 0。

圖4 （2，1，3）卷積碼的網格圖表示Fig.4 Trellis of（2,1,3）convolutional codes

在不同時刻對于同一節點的所有8個狀態，分別計算以其為終點的2條分支路徑的對數似然函數累加值并進行比較，舍棄其中對數似然函數累加值小的路徑，保留對數似然函數累加值較大的路徑，并將此路徑稱為剩余路徑。由此可見，上述過程可以歸納為“加-比-選”算法，經過“加-比-選”電路以后，通過結束信息來確定最終得到的譯碼序列，其中每到來一個結束信息時，只將與已知發送信息相符的那條支路保留，以此類推，經過N-1個結束信息后，即可得到與發送序列最相似的譯碼路徑。

3 譯碼器設計與實現

維特比譯碼器包括4個子模塊，如圖5所示。

圖5維特比譯碼器的總體框架Fig.5 Overall framework of veterbi decoder

1）控制單元 向各個功能模塊提供控制信號，保證譯碼器的工作時序正確，協調各個功能模塊從而促使整個譯碼器的正常工作。

2）路徑度量和“加-比-選單元” 計算和比較每條支路的路徑度量，得到并保存剩余路徑提供給回溯單元。對于（2，1，3）卷積碼，譯碼深度 D=5（m+1）=20，為保證存儲單元和回溯單元同時并行工作，存儲單元為2D（m+1）2m=1 280 bit。

3）回溯單元 從前面“加-比-選”電路送來的剩余路徑中選擇量度最小的剩余路徑，從這條路徑對應的狀態開始向前尋找，直到找完前面所有狀態，并從存儲單元中讀出譯碼信息送給譯碼控制單元。

4）譯碼控制單元 將回溯單元送來的譯碼序列反轉順序輸出即為所要輸出的正確的接收序列。其中反轉順序的操作可由RAM實現，順序寫入倒序讀出。

4 譯碼器設計中改進和優化算法

本文采取狀態路徑和判決比特同時存儲，在表示狀態信息的比特前加上1位判決比特來表示相應狀態的輸入支路的譯碼信息，因此，譯碼器在回溯時就可直接輸出判決比特作為譯碼器的輸出，降低了譯碼器的判決難度，節省了存儲回溯路徑所需要的內存，從而降低了譯碼器結構復雜性。

本設計中譯碼器在計算所有狀態的路徑量度的同時進行路徑存儲，從而大大提高了譯碼速度。路徑量度是指每個狀態的2條輸入支路和2條輸出支路，路徑存儲指的是狀態存儲以及相應的譯碼判決比特存儲。該結構的譯碼器對每一個狀態都具有獨立的處理單元，彼此互補影響，并行工作，提高了譯碼速度。對于（2，1，3）卷積碼，一個時鐘需要進行 2×2×2m=32次路徑量度計算和2m=8次4比特存儲操作。充分發揮了FPGA擁有大量LCS和RAM的優勢。

在網格圖中，隨著狀態的改變，每個狀態的輸出支路的路徑量度逐漸增加，造成存儲資源壓力增大，設計中在每次進行路徑量度計算時，將該狀態的量度值與上次剩余路徑量度的最小值做差后進行保存，以達到減小存儲器空間的需求。對于編碼效率為1/2的卷積碼，以上差值最大不超過2m，因此，路徑量度的量化寬的為 lb（2m）。 對于（2，1，3）卷積碼，存儲路徑量度的寄存器位寬為 lb（2×3）=3。

5 驗證仿真

本設計采用Xilinx公司的ISE 9.2i為開發平臺，選用的是Xilinx Virtex 4 FPGA為開發芯片用于設計和驗證所提出的卷積編碼和維特比（Veterbi）譯碼算法。

5.1 卷積編碼器

如圖6所示，clk為時鐘信號，reset為復位信號，din為輸入信號，out_1,out_2為編碼后得到的并行碼字序列。可看出：輸入碼元為“101010111011 000100011011111111100……”經過編碼得到編碼結果為“110100010001001010100010 101100110111001110100101010101010101011”結果正確。

5.2 Verterbi譯碼器

Verterbi譯碼器仿真波形如圖7所示，rev[1:0]為輸入譯碼器的接收序列，clk為時鐘信號，rst為復位信號，enable為使能信號，h_out為譯碼器輸出序列。可看出：譯碼輸出碼元為“101010111011000100011011111111100……”，結果正確。

圖6卷積編碼器的仿真波形Fig.6 Simulation waveform of convolutional encoder

圖7維特比譯碼器的仿真波形Fig.7 Simulation waveform of veterbi decoder

6 結束語

通過對卷積編碼原理與維特比譯碼算法的深入研究，在理解傳統實現方法的基礎上提出適合FPGA存儲器和獨立運算單元豐富的特點的優化算法，有效地提高了譯碼器的處理速度，簡化了譯碼器的復雜程度。

[1]曹志剛.現代通信原理[M].北京：清華大學出版社，1994.

[2]王新梅，肖國鎮.糾錯碼原理與方法[M].西安：西安電子科技大學出版社，1991.

[3]夏宇聞.Verilog數字系統設計教程[M].北京:北京航空航天大學出版社，2003.

[4]ViterbiAJ.Errorboundsofconvolutionalcodesandanasymptotically optimum decoding algorithm [J].IEEE Transations on Information Theory,1967,13（2）:260-269.

[5]Anderson J B,Offer E.Reduced-state sequence detection with convolutional codes[J].IEEE Transactions on Information Theory,1994,40（3）:965-972.

[6]Proakis J G， Salehi M.Digital communications[M].北京：電子工業出版社，2006.