糾三錯BCH碼改進查找表譯碼算法研究及其實現(xiàn)?

孔挺 余鵬 王浩

（海軍航空兵學院 葫蘆島 125001）

1 引言

BCH碼是目前已知的一類可以有效糾正多個獨立錯誤的循環(huán)碼，這類碼具有簡單的結構、較強的糾錯能力，在信道糾錯碼領域得到了廣泛應用。相較BCH碼的編碼而言，其譯碼要復雜得多，因此，尋找簡單、快速、易于實現(xiàn)的BCH碼譯碼算法一直是幾十年來編解碼研究領域關心的熱點之一。到目前為止，較為著名的BCH碼譯碼算法主要包括Peterson算法［1］、PGZ算法［2］、Chien搜索算法［3］、Forney 算法［4］、BM 迭代算法［5～6］、IBM 算法［7］等，其中，以BM迭代算法和Chien搜索算法最為有效［8］，然而，當碼字出錯位數(shù)增加，上述算法將需要大量復雜的代數(shù)運算，從而造成譯碼慢、電路復雜等問題。此外，還有一種查找表算法，它將碼字出現(xiàn)不超過其糾錯能力時所有錯誤圖樣與對應的校驗子存儲在查找表中，通過計算接收碼字的校驗子直接找到相應的錯誤圖案，實現(xiàn)糾錯，與前述算法相比，它具有計算量小、結構簡單、易于實現(xiàn)的優(yōu)點，但是隨著碼字的碼長增加和糾錯能力提高，其占用存儲資源較大的問題將變得非常突出，因此，這種算法主要用于中短碼長的BCH碼。對于查找表算法的優(yōu)化和應用，國內外一些專家學者也開展了相關研究［9～11］。其中，文獻［10］提出了利用校驗子的碼重參與譯碼的縮短查找表算法，該算法以糾三錯的（15，5，7）BCH碼和（31，16，7）BCH碼為例，只把信息位出2位以下錯時的錯誤圖樣和對應的校驗子存儲在查找表中，利用BCH碼是循環(huán)碼的特點，通過計算校驗子碼重來糾錯，該算法雖然比傳統(tǒng)查找表算法節(jié)省較多的存儲資源，但在信息位有1位出錯、校驗位有2位出錯的情況下，需要很多次循環(huán)運算，因而計算量過大，導致譯碼速度大幅下降；文獻［11］針對糾二錯BCH碼，把信息位出2位以下錯時的錯誤圖樣和對應的校驗子存儲在查找表中，雖然也通過計算校驗子碼重來糾錯，但不需循環(huán)運算，因此，在大幅降低資源消耗的同時，使譯碼速度得到了有效的提升。基于文獻［11］中的改進算法的思想，本文以（15，5，7）BCH碼為例，研究該算法在糾三錯BCH碼中的應用及性能表現(xiàn)，并基于FPGA研究其實現(xiàn)方法。

2 傳統(tǒng)查找表算法原理

傳統(tǒng)查找表算法的原理是基于接收碼字R的校驗子S與錯誤圖樣E之間存在著對應關系，根據(jù)兩者間的這種關系，建立一個查找表，將所有可能的校驗子和相應的錯誤圖樣存儲在查找表中，譯碼時將計算得到的校驗子與查找表中的數(shù)據(jù)進行查找對比，找到相同的校驗子即可得到錯誤圖樣，從而確定R的錯誤位置并加以糾正［11］。具體而言就是：

1）當 S=0時，說明 e1=e2=…=en=0，即E=0，R=C，說明R無錯誤。

2）當 S≠0 時，說明 e1，e2，…，en不全為0，即 R至少存在1位錯誤，根據(jù)校驗子的值與監(jiān)督矩陣H中列向量的對應關系，按以下方法確定R的錯誤位置：

（1）當R存在1位錯誤時，假設是R的第i位出錯，那么 ei=1，el=0（l=1，2，…n，l≠i），則 S向量應等于H矩陣的第i列向量，利用這個關系就能夠找到R的出錯位置。

（2）當R存在2位錯誤時，假設是R的第i、j兩位出錯，那么 ei=ej=1，el=0（l=1，2，…，n，l≠i，j），則S向量應等于H 矩陣的第i列和第 j列向量的模2和，且這兩列的取法具有唯一性，利用這個關系就能夠找到R的2個出錯位置。

同理，按照上述方法，只要R的出錯位數(shù)在BCH碼的糾錯能力范圍內，就可以根據(jù)S向量與H矩陣的列向量的對應關系對R進行糾錯。

上述算法在具體實現(xiàn)時，只須用一塊ROM存儲校驗子和相應的錯誤圖樣，譯碼時將計算得到的校驗子與查找表中的校驗子進行逐一對比，找到相同的校驗子，便可得到相應的錯誤圖樣，實現(xiàn)糾錯［12］。以（15，5，7）BCH碼為例，該碼可以糾3位錯，因此，其ROM中需要存儲=575組數(shù)據(jù)，每組數(shù)據(jù)中S向量與E向量分別占用2 bytes的存儲空間，即共需占用4 bytes的存儲空間。

由此可知，傳統(tǒng)查找表算法因無迭代或循環(huán)運算，其譯碼速度快、硬件實現(xiàn)也比較簡單。但是，它也存在明顯的不足：當碼字較長或碼字的糾錯能力強時，會占用較多的存儲資源。因此，這種算法更適用于短或中等長度碼字的譯碼。

3 基于查找表的改進算法原理

文獻［11］以可以糾正兩位錯誤的（31，21，5）BCH為例，基于傳統(tǒng)查找表提出了一種改進的譯碼算法，不僅節(jié)約了存儲資源，還提升了譯碼速度。借鑒該算法的思想，下面以（15，5，7）BCH碼為例，研究該算法如何實現(xiàn)糾三錯BCH碼的譯碼。

假設（15.5.7）BCH碼采用系統(tǒng)碼，接收碼字為R=(r2，…，r15)，其中 r1～r5為信息位，r6～r15為校驗位，校驗子 S=R·HT=E·HT=[PTI10]。根據(jù)改進查找表算法的思想，應把（15，5，7）BCH碼信息位出3位以下錯時的錯誤圖樣和對應的校驗子圖樣（統(tǒng)稱為查找圖樣）存儲在查找表中，則查找表中總共應存儲=25個查找圖樣，每個查找圖樣中S向量為10 bits，E向量為15 bits，均需占用2 bytes的存儲空間，因此，一個查找圖樣需占用4 bytes的存儲空間。

與傳統(tǒng)查找表算法一樣，在碼字最多只發(fā)生3位錯誤的前提下，S應該等于監(jiān)督矩陣H中某些與錯誤位置對應的列的模2和，改進算法確定接收碼字出錯位置的原則如下：

1）信息位無錯，僅校驗位出錯的情況：如果校驗位r6～r15有1位出錯，因為H對于碼字校驗位的后半部分是單位陣，所以此時校驗子S的碼重w(S)=1；同理，校驗位有2位出錯時，碼重w(S)=2；校驗位有3位出錯時，碼重w(S)=3。并且在上述錯誤情況下，S中1的位置與r6～r15中的出錯位置一一對應，可以直接糾錯。

2）僅信息位出錯，校驗位不出錯的情況：此情況下，碼重w(S)≥3，但由于信息位只發(fā)生1位～3位以下錯誤的錯誤圖樣和對應的校驗子圖樣已經存儲在查找表中，只需搜索查找表就可找到對應的錯誤圖樣，進行糾錯。

3）信息位和校驗位都出錯的情況：假設信息位有1位出錯誤，校驗位有1位或2位出錯，S與查找表中對應的校驗子圖樣Si求模2和后得到的的碼重w()應等于1或2，且中1的位置與碼字校驗位出錯的位置對應；假設信息位有2位出錯，校驗位有1位出錯，S與查找表中對應的校驗子Si求模2和后得到的的碼重應等于1，同樣，中1的位置與碼字校驗位出錯的位置對應。

根據(jù)上述原則，（15，5，7）BCH碼采用改進查找表算法的譯碼流程如圖1所示，圖中“選擇滿足唯一糾錯條件的”中的“糾錯條件”是：S與信息位發(fā)生1位錯誤時對應的Si求模2和所得的的碼重w(≤2；S與信息位有2位出錯時對應的Si求模2和所得的的碼重w(≤1；S與信息位有3位出錯時對應的Si求模2所得的的碼重w(=0。

4 算法性能分析

4.1 資源消耗

（15，5，7）BCH碼分別采用不同算法時的存儲資源消耗情況見表1。

圖1 改進算法的譯碼流程

表1 不同查找表算法的存儲資源消耗

從表1數(shù)據(jù)可以看出，相對傳統(tǒng)查找表算法而言，文獻［10］提出的縮短查找表算法僅將碼字信息位出現(xiàn)兩位以下錯誤時的查找圖樣存儲在查找表中，因而其資源節(jié)省率最高，而改進查找表算法因在查找表中比它多存儲了信息位出現(xiàn)三位錯誤時的查找圖樣，導致其資源節(jié)省率略低于縮短查找表算法，但仍然遠高于傳統(tǒng)查找表算法。

4.2 譯碼性能

圖2所示為譯碼性能的仿真模型。圖中，設定AWGN信道的信噪比（EbNo）為2.5dB，采用兩種算法譯碼時均隨機生成10萬幀信息位碼字。仿真計算機處理器為 Intel（R）Core（TM）2 Duo CPU T6500 2.10GHz；計算機系統(tǒng)內存為2GB。仿真結果如表2所示。

圖2 仿真模型

表2 傳統(tǒng)與改進查找表算法的譯碼性能

從表中的數(shù)據(jù)可以看出，（15，5，7）BCH碼采用兩種譯碼算法時的BER性能相當，這說明改進查找表算法適用于可糾3位錯的BCH碼。但是，由于改進查找表算法的查找表中查找圖樣比傳統(tǒng)查找表少得多，因此，其譯碼延時比傳統(tǒng)查找表算法減小了近1.6倍；而文獻［10］縮短查找表算法的查找表中的查找圖樣雖然比傳統(tǒng)查找表算法和改進查找表算法都少，但是其譯碼過程中需要利用循環(huán)碼的循環(huán)移位特性進行多次循環(huán)移位計算，因此，其譯碼速度較慢，譯碼延時幾乎是傳統(tǒng)查找表算法的10倍。

此外，對比文獻［11］的表1的仿真結果可知，BCH碼的糾錯能力、信息位長度對改進查找表譯碼速度的提升有較大影響。

5 改進查找表算法的FPGA實現(xiàn)

5.1 設計方案

采用改進查找表算法譯碼的實現(xiàn)框圖如圖3所示。其中輸入碼字為在Matlab隨機生成的（15，5，7）BCH碼碼字，經隨機加3位以下錯誤后形成的待譯碼數(shù)據(jù)。

圖3 改進查找表譯碼的FPGA實現(xiàn)框圖

為了提高譯碼速度，碼字的傳輸采用比特并行方案，如圖4所示，圖中，nbits數(shù)據(jù) bn，…，b2，b1在一個時鐘、n條線上并行發(fā)送。具體而言就是，每個時鐘完成一個15bits的（15，5，7）BCH碼字的接收，并存儲于寄存器內，等待與錯誤序列進行異或。

圖4 碼字傳輸比特并行方案示意圖

圖5 校驗子比特si的實現(xiàn)電路

利用容量為25×25，地址線和數(shù)據(jù)輸出線數(shù)量分別為5根、15根的ROM存儲25個10bits大小的校驗子和5bits大小的錯誤圖樣。計算得到S后，按照圖1的改進算法流程找出錯誤圖樣，對輸入碼字糾錯后輸出譯碼碼字。

圖6為基于Quartus軟件平臺構建的系統(tǒng)頂層框圖，利用VHDL編程將其封裝成圖形形式，圖中從左至右依次為控制模塊、糾錯模塊和輸出模塊［15］。譯碼器采用Altera公司的cycloneⅡ系列的EP3C5F265C6芯片實現(xiàn)。

圖6 譯碼電路系統(tǒng)頂層框圖文件

5.2 仿真結果

根據(jù)Quartus軟件最終的綜合編譯報告結果，該譯碼器對任意3bits的錯誤組合圖樣均可正確糾錯，譯碼過程共占用593個邏輯單元（占用率12%）；在50MHz時鐘下，譯碼器可在2個時鐘內完成譯碼，譯碼時序仿真結果如圖7所示。

圖7 譯碼電路時序仿真圖

6 結語

在BCH碼傳統(tǒng)查找表譯碼算法的基礎上，以（15，5，7）BCH碼為例，研究了文獻［11］提出的改進查找表算法對可糾正3位錯誤的BCH碼的譯碼原理和流程，仿真比較了該算法與傳統(tǒng)查找表算法的譯碼性能，并基于FPGA研究了該算法的硬件實現(xiàn)方法。研究表明，改進算法與傳統(tǒng)查找表算法在BER性能上一致，但前者在資源消耗和譯碼速度性能上的表現(xiàn)明顯優(yōu)于后者；設計的譯碼器具有結構簡單、資源占用少、運行速度快的特點，非常適合中短碼長BCH碼在硬件設備受限或高速數(shù)據(jù)傳輸系統(tǒng)中的應用。

［1］W.W.Peterson.Encoding and Error-Correction Proce?dures for the Bose-Chaudhuiri Code［J］.IRE Trans.In?form.Theory，1960，6：459-470.

［2］ D.Gorenstein，N.Zierler.A Class of Cyclic Linear Er?ror-Correcting Codes in pm Symbols［J］.J.Soc.Ind.Appl.Math，1961，9：207-214.

［3］ R.T.Chien. Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes［J］.IEEE Trans.Inform.Theory，1964，10：357-363.

［4］G.D.Forney.On Decoding BCH Codes［J］.IEEE Trans.In?form.Theory，1965，11：549-557.

［5］ E.R.Berlekamp.On Decoding Binary Bose-Chaud?huri-Hocquenghem Codes［J］.IEEE Trans.Inform.Theo?ry，1965，11：577-580.

［6］J.L.Massey.Shift-Register Synthesis and BCH Decoding［J］.IEEE Trans.Inform.Theory，1969，15（1）：122-127.

［7］H.O.Burton.Inversionless Decoding of Binarry BCH Codes［J］.IEEE TRrans.Inform.Theory，1971，17（4）：464-466.

［8］Shu Lin，Daniel J.Costello，Jr著.晏堅等譯.差錯控制編碼（第2版）［M］.北京：機械工業(yè)出版社，2007：130.

Shu Lin，Daniel J.Costello.Jr.Error Control Coding（2nd ed）［M］.Beijing：Machine Industry Press，2007：130.

［9］李雄飛，李振華，邱樂德.縮短BCH碼（16，8，5）編譯碼算法及其實現(xiàn)［J］.空間電子技術，2009，6（2）：33-38.

LI Xiongfei，LI Zhenhua，QIU Lede.A Coding and Decod?ing Algorithm and its implementation of shortened BCH Codes（16，8，5）［J］.Space Electronic Technology，2009，6（2）：33-38.

［10］H.P.Lee，H.C.Chang，T.C.Lin，T.K.Truong.A Weight Method of Decoding the Binary BCH Code［C］//8th International Conference on Intelligent Systems De?sign and Applications.IEEE Computer Society，2008：545-548.

［11］孔挺，宮芳，方揚揚.基于查找表的BCH碼快速譯碼算法［J］.哈爾濱商業(yè)大學學報（自然科學版），2011，27（6）：819-823.

KONG Ting，GONG Fang，F(xiàn)ANG Yangyang.A fast de?coding Algorithm for BCH codes based on lookup table［J］.Journal of Harbin University of Commerce（Natural Sciences Edition），2011，27（6）：819-823.

［12］周盛容，胡正飛.基于BM迭代的高速BCH譯碼方法［J］.電腦知識與技術，2007（4）：1019-1020.

ZHOU Shengrong，HU Zhengfei.Fast BCH decoding de?sign using BM iteration［J］.Computer Knowledge and Technology，2007（4）：1019-1020.