基于FPGA 的循環漢明碼編譯碼器的設計與實現

李壯壯，劉光祖，孫琳琳，鄒駿

（南京理工大學電子工程與光電技術學院，江蘇南京 210094）

數字信號在無線信道的傳輸過程中，受到信道傳輸特性不理想、干擾等多種因素的影響，碼元波形畸變，導致接收端解調判決發生錯誤，降低了通信系統的可靠性。當通過改變調制方式、發射功率、信道均衡等方式仍無法避免誤碼發生時，就需要利用差錯控制編碼ECC（Error Control Coding）來改善通信系統的質量[1-2]。

差錯控制編碼，又稱為信道編碼，即信道編碼器對傳輸的信息碼元按一定規則加入冗余信息（監督碼元）[3]。信道編碼主要包括分組碼、卷積碼等。循環漢明碼屬于分組碼的一種，它不僅能夠檢測出接收信息碼字中的錯誤碼元，還能糾正一位錯誤碼元[4-5]。

一般基于二進制多項式除法器的編碼電路需要移位補零，會造成一定的編碼延時[6-7]。在譯碼時，一般的梅吉特譯碼器搜尋錯誤圖樣的時間較長，降低了數據吞吐量。基于上述兩點，對編譯碼器電路進行了改進，成功消除了編碼延時并有效降低了譯碼延時。

1 編譯碼原理

循環漢明碼不僅具有一般分組碼的特性，還具有自身的獨特性——循環性[8]。循環性指循環漢明碼任一碼字循環移位后仍為該碼中的碼字。假設信息位數為k，編碼之后的碼長為n，監督碼元位數為r=n-k。對于r字長的監督碼元，組合共有2r種，可以監督的最大碼長為2r[9-10]。一個信息碼長為n的碼字可以表示為如式（1）的多項式（以下mod 均表示模）:

循環移位i次的結果為：

由循環碼的性質知，經過式（2）模xn+1 計算得到的碼字也為此碼中的碼字[11]。

一般的循環漢明碼編碼步驟分為兩步：

1）計算并選擇生成多項式g(x)。g(x)為xn+1 的因式，且g(x)的最高次冪為n-k[12]。

2）利用g(x) 對信息序列進行編碼。假設信息多項式為m(x)，最高次冪為k-1，編碼之后的多項式為:

由于所有的碼字多項式均可以被g(x)整除，所以A(x)≡0(modg(x))，即：

要使上式成立，需要滿足：

因為若xn-km(x)modg(x)≡r(x) 恒成立，二者模2之和必恒為0。

循環漢明碼譯碼方法種類較多，比如最大似然譯碼法[13-14]、梅吉特譯碼法[15]等。該次選擇了較為實用且相對簡單的梅吉特譯碼法，譯碼原理如下：

1）計算第n位碼元（最高位）發生錯誤時的伴隨式。設發送碼字為A(x)，最高位發生錯誤時的接收碼字為:

伴隨式為:

即：

2）若第n-1 位發生錯誤，伴隨式為：

因為:

乘上x即左移一位，確定錯誤碼元位置為次高位。

3）以此類推，若錯誤發生在第n-i位，伴隨式為：

因為:

乘上xi即左移i位，確定錯誤碼元位置為n-i。

2 編譯碼器設計

2.1 編碼器設計

根據上述的編碼原理，硬件實現時需要用到多項式除法電路。二進制多項式除法器可以由線性反饋移位寄存器實現。根據式（5），編碼器的實現結構如下：

利用圖1 結構進行編碼時，將所有信息碼元輸入編碼器后還需進行n-k次移位才能得到編碼結果。此編碼結構有一定缺點，因為需要額外移位n-k次，會產生n-k個時鐘延時。在硬件實現時，由于編碼延時的存在，若要保證編碼后的數據連續送入下一處理模塊，需將原始碼元緩存，得到監督碼元后一并輸出。

圖1 補零編碼結構

基于上述缺點，此次采用一種改進的編碼方式，消除了上述編碼器移位造成的輸出延遲。數學原理推導如下：

設被除多項式為B(x)=xn-km(x)，其中：

余式r(x)≡B(x)modg(x)，即：

對于xn-k+1modg(x)有如下關系：

根據式（15）對r(x)表達式進行重寫：

①上式中g(x)最高次冪為n-k，B(x)的最低次冪為n-k，將式（17）中ak-1xn-k與g(x)相除，得到最高次冪為n-k-1的余式。

②將①中余式與x相乘，最高次冪變為n-k，然后與ak-2xn-k進行模2 加，并將結果與g(x)相除，得到新的最高次冪為n-k-1的余式，重復上述步驟最后得到的余式系數即為監督碼元。

根據式（17），編碼器的實現結構如圖2 所示。

圖2 無延遲編碼結構

2.2 譯碼器設計

梅吉特譯碼器的譯碼原理是基于錯誤圖樣識別，對于不同的錯誤圖樣，伴隨式不同，通過識別不同的伴隨式確定錯誤碼元位置[16]。

譯碼步驟如下：

1）使用生成多項式g(x) 整除接收多項式R(x)，求出伴隨式r(x)。

2）判斷伴隨式系數是否全為0，若全為0，無誤碼，若不全為0，有誤碼。有誤碼時，將計算得到的伴隨式與本地保存的伴隨式進行比對，若兩者相同，可確定錯誤碼元位置，若不同，執行步驟3）。

3）對伴隨式左移一位，繼續除以g(x)求伴隨式并與本地伴隨式比對，若相同，通過移位的次數確定錯誤碼元位置，若不相同，重復步驟3），直到計算出的伴隨式與本地伴隨式相同為止。

在上述梅吉特譯碼方式基礎上，額外添加一個檢測伴隨式，會極大降低譯碼時間。譯碼器電路結構主要包含：數據緩沖糾錯電路、伴隨式計算電路、錯誤圖樣識別電路、糾錯選擇電路。其結構如圖3所示。

圖3 改進后的譯碼器結構

為計算添加一個伴隨式識別電路對譯碼時間的影響，設接收碼元長度為n，添加的伴隨式對應的錯誤碼元位置為：

[·]為向下取整，設(n,k)循環漢明碼每次錯誤一個碼元，且不同位置上的碼元錯誤可能性相同，即每個碼元錯誤概率P(x)=，僅采用最高位碼元對應的伴隨式作為檢測目標的平均移位次數為：

采用上述改進后譯碼方式的平均移位次數約為：

由上可知，譯碼延時降低約為一半。

3 編譯碼器的FPGA實現

此次對循環漢明碼（255，247）的截短碼（152，144）進行仿真驗證，生成多項式選擇435（435 為八進制表示，100011101，左側為多項式最高位）。截短循環漢明碼的編譯碼方式與一般循環漢明碼的編譯碼方式完全相同，唯一的不同在于編譯碼的有效碼元數目不同。

3.1 編碼器的實現

編碼器結構主要借助圖2 編碼電路及圖4 的狀態機得以實現。

圖4 編碼器狀態轉移圖

S_IDLE:完成編碼前的準備工作，包括將余式寄存器及編碼計數器清零、檢測數據有效標志的邊沿等操作。

S_CODE:完成數據碼元的編碼。

S_FINISH:完成監督碼元輸出。在編碼完成之后，將監督位依次輸出。

3.2 譯碼器的實現

譯碼器主要借助圖3 中譯碼電路和圖5 譯碼流程圖得以實現。

圖5 譯碼器實現流程圖

伴隨式計算：完成接收多項式與生成多項式的相除，求解伴隨式。

伴隨式判斷：若計算求得的伴隨式系數全為0，數據無誤碼，可將去除監督碼元后的數據輸出。若伴隨式系數不全為0，表明數據有誤碼。

錯誤圖樣識別：完成定位錯誤碼元位置。將本地伴隨式與當前計算出的伴隨式比對，若兩者一致，誤碼位置即可定位，若不一致，繼續將伴隨式移位與g(x)相除求解新的伴隨式。

編碼器電路綜合后原理圖、資源圖分別如圖6和圖7 所示，其占用資源如表1 所示。

圖6 編碼器綜合后原理圖

圖7 編碼器綜合后資源

表1 編碼器占用資源

改進前后譯碼器資源利用圖分別如圖8 和圖9（由于譯碼器原理圖過于復雜，未列出）。

圖8 改進前譯碼器綜合后資源

圖9 改進后譯碼器綜合后資源

圖8 對應只有一個錯誤圖樣的譯碼資源利用率，圖9 中對應有兩個錯誤圖樣的譯碼資源利用率。綜合兩圖，改進后譯碼器的資源使用與改進前的相比，LUTs 增加了83 個，寄存器增加了一個。表2中為譯碼器改進前后占用資源數量

表2 譯碼器占用資源

4 編譯碼的仿真結果

圖10-13 為兩組不同數據的編譯碼仿真圖。此次仿真，時鐘頻率為80 MHz，周期為12.5 ns。對于編譯碼器1，編碼過程（第一個數據碼元開始進入到最后一個碼元輸出）消耗時鐘數目為153（碼元輸出占用152，外加一個時鐘的數據延遲）。可知改進后的編碼器相較于一般補零編碼器，已經消除了補零帶來的延遲。

圖10 編碼器仿真1

為了驗證增加一個檢測伴隨式帶來的優勢，實驗中兩個譯碼器中錯誤碼字位置有所不同（最低位為0，最高位為151）。對于改進的譯碼器，該文設置了兩個檢測伴隨式，一個對應最高位（151），一個對應中間位（76）。譯碼器仿真1 中碼元錯誤位置設置為120，譯碼器仿真2 中碼元錯誤位置設置為17。譯碼器仿真圖中依次從下向上，1-4 行對應兩個檢測伴隨式的譯碼器輸出，5-8 行對應一個檢測伴隨式的譯碼器輸出。

觀察圖11 可知，改進后與改進前譯碼器錯誤位置指示變量i最終都定位在32，錯誤位置為120(152-32=120)。對于改進后的譯碼器，若錯誤位置落在151～77 之間，譯碼時間未改變。觀察圖13，改進后的譯碼器的位置指示變量i為60，錯誤位置為17(77-60=17)，而改進前的譯碼器位置指示變量為135，錯誤位置為17(152-135=17)，但對比二者的譯碼時間，改進后譯碼器比改進前譯碼時間減少937.5 ns[理論值(135-60)×12.5=937.5 ns]。

圖11 譯碼器仿真1

圖12 編碼器仿真2

圖13 譯碼器仿真2

以此類推，也可以嘗試加入更多的檢測伴隨式，將譯碼的時間縮小更多，該文篇幅有限，不再贅述。

5 結束語

使用Verilog HDL 硬件描述語言對（152，144）截短循環漢明碼編譯碼器進行了仿真，驗證了一種無延遲編碼方式，并對其數學原理進行了推導。由于在筆者參與的某衛星通信項目中對循環漢明碼譯碼時間要求較高，所以對梅吉特譯碼器做出了一定改進，通過增加檢測伴隨式有效降低了譯碼延時，硬件資源增加較少，滿足了項目對譯碼時間及資源利用率的要求。同時驗證了改進后編譯碼器的正確性和可靠性，具有很高的使用價值和指導意義。