基于FPGA 的循環(huán)漢明碼編譯碼器的設計與實現(xiàn)

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

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

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

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

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

1 編譯碼原理

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

循環(huán)移位i次的結果為：

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

一般的循環(huán)漢明碼編碼步驟分為兩步：

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。

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

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

伴隨式為:

即：

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

因為:

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

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

因為:

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

2 編譯碼器設計

2.1 編碼器設計

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

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

圖1 補零編碼結構

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

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

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

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

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

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

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

根據(jù)式（17），編碼器的實現(xiàn)結構如圖2 所示。

圖2 無延遲編碼結構

2.2 譯碼器設計

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

譯碼步驟如下：

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

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

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

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

圖3 改進后的譯碼器結構

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

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

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

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

3 編譯碼器的FPGA實現(xiàn)

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

3.1 編碼器的實現(xiàn)

編碼器結構主要借助圖2 編碼電路及圖4 的狀態(tài)機得以實現(xiàn)。

圖4 編碼器狀態(tài)轉移圖

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

S_CODE:完成數(shù)據(jù)碼元的編碼。

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

3.2 譯碼器的實現(xiàn)

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

圖5 譯碼器實現(xiàn)流程圖

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

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

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

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

圖6 編碼器綜合后原理圖

圖7 編碼器綜合后資源

表1 編碼器占用資源

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

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

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

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

表2 譯碼器占用資源

4 編譯碼的仿真結果

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

圖10 編碼器仿真1

為了驗證增加一個檢測伴隨式帶來的優(yōu)勢，實驗中兩個譯碼器中錯誤碼字位置有所不同（最低位為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）截短循環(huán)漢明碼編譯碼器進行了仿真，驗證了一種無延遲編碼方式，并對其數(shù)學原理進行了推導。由于在筆者參與的某衛(wèi)星通信項目中對循環(huán)漢明碼譯碼時間要求較高，所以對梅吉特譯碼器做出了一定改進，通過增加檢測伴隨式有效降低了譯碼延時，硬件資源增加較少，滿足了項目對譯碼時間及資源利用率的要求。同時驗證了改進后編譯碼器的正確性和可靠性，具有很高的使用價值和指導意義。