摘 要：介紹了一種新型的BCH碼的譯碼方法，并給出了該譯碼算法的FPGA器件實現(xiàn)方法。與傳統(tǒng)的譯碼算法相比，該算法具有譯碼速度快、硬件實現(xiàn)復(fù)雜度低等優(yōu)點，從而使得該譯碼器具有速度快、體積小、性能穩(wěn)定等特點。
關(guān)鍵詞：差分CDMA；BCH碼; FPGA; 譯碼器；設(shè)計
一、引言
BCH碼是一類重要而有效的糾正多個隨機(jī)錯誤的循環(huán)碼，由于該碼具有嚴(yán)格的代數(shù)結(jié)構(gòu)，所以是到目前為止研究得最為詳盡、應(yīng)用最為廣泛的一類碼，已有多種譯碼算法。但是這些傳統(tǒng)的譯碼算法，比如Berlekamp-Massey算法、Peterson算法［1，2］等，要經(jīng)過多次迭代，運(yùn)算復(fù)雜，在硬件實現(xiàn)時仍然相當(dāng)困難。為了便于在硬件上實現(xiàn)，本文提出了一種利用群變換的新的BCH碼的譯碼算法，該算法具有譯碼速度快、硬件實現(xiàn)復(fù)雜度低等特點。本文中還研究了基于這種譯碼算法的BCH碼譯碼器的FPGA器件實現(xiàn)方法,并給出以差分CDMA(diffCDMA)系統(tǒng)［3］中使用的BCH(63,51)碼為例的譯碼器設(shè)計。
二、BCH碼的新型譯碼方法
一個BCH碼的碼字是有限域中的一組符號序列，每個符號都是GF(2)域中的元素，符號序列可以根據(jù)生成多項式g(x)產(chǎn)生，也可以用生成矩陣G來生成，將信息數(shù)據(jù)構(gòu)成的向量與G相乘就可以得到相應(yīng)BCH碼。根據(jù)碼的結(jié)構(gòu)可分成系統(tǒng)碼和非系統(tǒng)碼［2］。
對于在差分CDMA(diffCDMA)系統(tǒng)中使用的BCH（63,51,2) 碼而言，由于采用的是BCH系統(tǒng)碼，相應(yīng)的編碼矩陣可以表示成
為51×51階的單位陣，P51×12起產(chǎn)生“冗余”位的作用, 其對應(yīng)檢驗矩陣為
設(shè)原碼字為C=(cn-1cn-2……c1c0)，經(jīng)傳送后接收到碼字為R=(rn-1rn-2……r1r0)，其中包含錯
要檢測出錯誤位置和錯誤值，必須解上式所確定的非線性方程組，直接求解很困難。為此許多譯碼方法都引入中間變量來進(jìn)行計算。著名的有Peterson方法、Berlekamp-Massey方法和Chien Search方法等 ［1，2］。這幾種方法對BCH碼進(jìn)行復(fù)號，計算相當(dāng)復(fù)雜，運(yùn)算量極大。
針對現(xiàn)有復(fù)號方法的不足之處，本文介紹一種群變換的新型算法［4］進(jìn)行譯碼。 在伽羅瓦有限域中，對BCH碼生成行列和檢驗行列進(jìn)行有限域變換(群變換通常指行、列向量變換、鏡像變換、旋轉(zhuǎn)變換等)，將生成行列和檢驗行列變換成既約臺形(reduced echelon form)形式的行列。
以(7,4)BCH碼為例，其一般的校驗矩陣為
其中hi(i=1,2……,7)為
中的列向量。對于一般情況下，矩陣可都表示成=(h0h1h2……h(huán)n-1)， 對于這種形式的檢驗矩陣，由S=RT，可得S與中列向量的對應(yīng)關(guān)系，進(jìn)而可以確定出錯誤位置并進(jìn)行糾正。原理如下：
(1)當(dāng)S=0時，即e0=e1=……=en-1=0即E=0,R=C,說明此時未發(fā)生錯誤；
(2)當(dāng)S≠0時，則說明e0,e1,……en-1不全為0，此時有錯誤發(fā)生。根據(jù)伴隨值S與中列向量線性關(guān)系，可得以下結(jié)論:
當(dāng)發(fā)生一位錯誤時，則有ei=1, el=0(L=1,2……n-1,L≠i),于是S向量必與矩陣第i列向量相等，利用這一關(guān)系可知第i位即為R向量中出錯位置。
當(dāng)發(fā)生二位錯誤時，則有ei=1, ej=1, el=0(L=1,2……n-1,L≠i,j),于是S向量等于矩陣中第i,j列向量之和，且這兩列的取法是唯一的。利用這一關(guān)系可知第i位和第j位即為R中出錯位置。
依此類推，根據(jù)S向量與中列向量的對應(yīng)關(guān)系，只要滿足糾錯能力，BCH碼就可糾正R中多個錯誤。因為是二進(jìn)制碼，找到錯誤位置后，隨即就可以糾正。用這種方法進(jìn)行譯碼，運(yùn)算程序大為簡化，因此具有較高的運(yùn)算效率和速度。
三、硬件設(shè)計
根據(jù)上述算法分析, 可以直接由電子線路中普通的乘法器、存儲器、計數(shù)器等電路構(gòu)成,但這樣做會導(dǎo)致系統(tǒng)體積增大，不便于系統(tǒng)的小型化、集成化,穩(wěn)定性也不高。FPGA是在 PAL、GAL等邏輯器件基礎(chǔ)上發(fā)展起來的,與PAL、GAL等相比較,FPGA的規(guī)模大,更適合于時序、組合等邏輯電路應(yīng)用場合,并且由于芯片內(nèi)部硬件連接關(guān)系的描述可以存放在下載芯片中,因而具有可編程性和設(shè)計方案容易改動等特點。目前FPGA器件已被廣泛應(yīng)用于代替中小規(guī)模數(shù)字電路,以提高系統(tǒng)的可靠性、抗干擾性能和處理速度�？紤]到BCH碼的譯碼過程只涉及到數(shù)字信號,因而選用FPGA器件構(gòu)成譯碼器電路完全可行。
此處以diffCDMA 系統(tǒng)中采用的BCH(63,51,2)碼為例，圖1給出了基于FPGA器件所研制的BCH碼譯碼器的結(jié)構(gòu)。譯碼器的外部信號包括clk、 R、 Reset、 DINEN、 Dout、DOEN等，其中clk為時鐘信號,R為輸入BCH碼序列,Reset是計數(shù)器復(fù)位信號,DINEN是輸入有效信號，在輸入有效碼字期間為高，其余時間為低，Dout為輸出BCH碼序列，DOEN為輸出信息位有效信號，在輸出有效信號信息位期間為高，其余時間為低。
下面結(jié)合框圖來說明BCH 碼譯碼器的譯碼過程。在DINEN信號為高期間，接收傳送過來的BCH碼序列，并保存在移位寄存器中，以便對其糾錯。與此同時將輸入的BCH碼序列與存儲器中保存的檢驗矩陣的各向量相乘，計算出伴隨值S，并存儲在伴隨值寄存器中。對于本例而言，存儲器的寬度為12位,長63位。接著啟動地址計數(shù)器，使存儲器循環(huán)輸出檢驗矩陣的每一列，并送入加法器進(jìn)行求和，求出的和與伴隨值S進(jìn)行比較，直至兩者相等，此時比較器輸出“1”，控制電路收到“1”信號后，立即停止計數(shù)器計數(shù)，保持原計數(shù)值不變。根據(jù)譯碼原理，此時保存的計數(shù)值就是BCH碼序列的錯誤位置。隨后移位寄存器中暫存的BCH碼序列輸出，依次通過位糾錯器。位糾錯器在比較器輸出為“1”時，根據(jù)計數(shù)器值指示的位置對原BCH碼序列相應(yīng)位取反。輸出BCH碼序列信息位時，DOEN信號為高，有效信息位輸出，而在輸出冗余位時，DOEN變低，這樣冗余位就被去掉, 所以譯碼器在糾錯的同時就把信息位提取出來，從譯碼器輸出的就是原信息碼序列。
由上述分析，我們根據(jù)自上而下(Top- down)的設(shè)計思想，用硬件描述語言進(jìn)行編程，由綜合器進(jìn)行自動邏輯綜合。這樣一來，可以避免繁瑣的信號連接，加快設(shè)計進(jìn)程，軟件流程圖如圖2所示�？紤]到乘法器消耗FPGA資源較大，而BCH碼和檢驗矩陣的元素都是二進(jìn)制數(shù)0和1，因此我們利用與門和加法器代替乘法器功能，來計算伴隨值S，這樣可以大大減小FPGA資源的消耗。
四、實驗結(jié)果
本文針對BCH（63，51）碼，選用Altera公司的FPGA器件EPF10K10LC84作為目標(biāo)芯片，EPF10K10LC84內(nèi)部有576個宏單元，10 000個可用門，總的RAM位達(dá)到6 144位，最高工作頻率可以達(dá)到150 MHz以上。應(yīng)用MAX+PlusII和Synopsys公司的綜合工具對其進(jìn)行了仿真，部分仿真結(jié)果如圖3所示。
設(shè)原數(shù)據(jù)信息為101011001011110011010010000100010100110110101110000，即565E6908A6D70H,經(jīng)編碼后得到的BCH碼序列為 110101011111101011001011110011010010000100010100110110101110000，即 6AFD65E6908A6D70H,為了檢驗譯碼器的工作效果，人為在0→62位序列中的第5位和第9位施加了錯誤，因此輸入譯碼器的BCH碼序列實際為110101011111101011001011110011010010000100010100110111101010000,即 6AFD65E6908A6F50H。
由圖可知，經(jīng)譯碼器處理，發(fā)現(xiàn)計數(shù)器最后分別停在5和9時，這說明錯誤位置在BCH碼序列的第5位和第9位，經(jīng)糾錯后可以看到輸出碼序列為565E6908A6D70H，與原數(shù)據(jù)序列一樣，證明譯碼正確。
根據(jù)Synopsys公司的綜合工具報告結(jié)果，該譯碼器寫入一片EPF10K10LC84芯片后，占用邏輯單元數(shù)378個，大約5 800個門。經(jīng)與日本愛知工業(yè)大學(xué)合作，在差分CDMA系統(tǒng)中實際使用驗證，該譯碼器的譯碼速度最高可達(dá)到10 Mbit/s，功耗約為1 W。
五、結(jié)束語
本文在系統(tǒng)地介紹了一種BCH碼譯碼算法的基礎(chǔ)上，詳細(xì)討論了基于該算法的譯碼器的FPGA器件設(shè)計。由于FPGA器件的可編程性，使電路實現(xiàn)簡明，設(shè)計更具靈活性，便于實現(xiàn)系統(tǒng)的小型化、集成化。實驗結(jié)果表明譯碼器的設(shè)計是正確可行的。
參考文獻(xiàn)
［1］王新梅,肖國鎮(zhèn).糾錯碼-原理與方法［Ｍ］.西安：西安電子科技大學(xué)出版社,2001
［2］Peterson w.w.Encoding and Error-correction procedures for the Bose-Chaudhuiri Code［Ｊ］.IRE Trans Inform Theory, 1960.459～470
［3］Masahishi Kishi，Kuixi YinConsideration on System Capability Characteristics of Portable 2Mbps/8 Mcps CDMA with Phase Continuous QPSK［Ａ］.IEEE VTC'98［Ｃ］.Canada：Ottawa，May 1998924～928
［4］殷奎喜，譚錫林.群變換方法構(gòu)成的BCH符號編碼、解碼多重糾錯器件［Ｐ］.中國專利：CN1247355A，2000，03－15
［5］侯伯亨,顧新.VHDL硬件描述語言與數(shù)字邏輯電路設(shè)計［Ｍ］.西安： 西安電子科技大學(xué)出版社,1999
［6］潘松,王國棟.VHDL實用教程［Ｍ］.成都： 電子科技大學(xué)出版社,2000
