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

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

（南京理工大學(xué)電子工程與光電技術(shù)學(xué)院，江蘇南京 210094）

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

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

一般基于二進(jìn)制多項(xiàng)式除法器的編碼電路需要移位補(bǔ)零，會(huì)造成一定的編碼延時(shí)[6-7]。在譯碼時(shí)，一般的梅吉特譯碼器搜尋錯(cuò)誤圖樣的時(shí)間較長(zhǎng)，降低了數(shù)據(jù)吞吐量?；谏鲜鰞牲c(diǎn)，對(duì)編譯碼器電路進(jìn)行了改進(jìn)，成功消除了編碼延時(shí)并有效降低了譯碼延時(shí)。

1 編譯碼原理

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

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

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

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

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

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

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

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

因?yàn)槿魓n-km(x)modg(x)≡r(x) 恒成立，二者模2之和必恒為0。

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

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

伴隨式為:

即：

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

因?yàn)?

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

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

因?yàn)?

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

2 編譯碼器設(shè)計(jì)

2.1 編碼器設(shè)計(jì)

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

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

圖1 補(bǔ)零編碼結(jié)構(gòu)

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

設(shè)被除多項(xiàng)式為B(x)=xn-km(x)，其中：

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

對(duì)于xn-k+1modg(x)有如下關(guān)系：

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

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

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

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

圖2 無延遲編碼結(jié)構(gòu)

2.2 譯碼器設(shè)計(jì)

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

譯碼步驟如下：

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

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

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

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

圖3 改進(jìn)后的譯碼器結(jié)構(gòu)

為計(jì)算添加一個(gè)伴隨式識(shí)別電路對(duì)譯碼時(shí)間的影響，設(shè)接收碼元長(zhǎng)度為n，添加的伴隨式對(duì)應(yīng)的錯(cuò)誤碼元位置為：

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

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

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

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

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

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

編碼器結(jié)構(gòu)主要借助圖2 編碼電路及圖4 的狀態(tài)機(jī)得以實(shí)現(xiàn)。

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

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

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

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

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

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

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

伴隨式計(jì)算：完成接收多項(xiàng)式與生成多項(xiàng)式的相除，求解伴隨式。

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

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

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

圖6 編碼器綜合后原理圖

圖7 編碼器綜合后資源

表1 編碼器占用資源

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

圖8 改進(jìn)前譯碼器綜合后資源

圖9 改進(jìn)后譯碼器綜合后資源

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

表2 譯碼器占用資源

4 編譯碼的仿真結(jié)果

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

圖10 編碼器仿真1

為了驗(yàn)證增加一個(gè)檢測(cè)伴隨式帶來的優(yōu)勢(shì)，實(shí)驗(yàn)中兩個(gè)譯碼器中錯(cuò)誤碼字位置有所不同（最低位為0，最高位為151）。對(duì)于改進(jìn)的譯碼器，該文設(shè)置了兩個(gè)檢測(cè)伴隨式，一個(gè)對(duì)應(yīng)最高位（151），一個(gè)對(duì)應(yīng)中間位（76）。譯碼器仿真1 中碼元錯(cuò)誤位置設(shè)置為120，譯碼器仿真2 中碼元錯(cuò)誤位置設(shè)置為17。譯碼器仿真圖中依次從下向上，1-4 行對(duì)應(yīng)兩個(gè)檢測(cè)伴隨式的譯碼器輸出，5-8 行對(duì)應(yīng)一個(gè)檢測(cè)伴隨式的譯碼器輸出。

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

圖11 譯碼器仿真1

圖12 編碼器仿真2

圖13 譯碼器仿真2

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

5 結(jié)束語

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