基于CPLD的BCH碼編-譯碼器的設(shè)計(jì)與實(shí)現(xiàn)

1、基于CPLD的BCH碼編-譯碼器的設(shè)計(jì)與實(shí)現(xiàn)2010年9月西安郵電學(xué)院Sept.2010第15卷第5期JOURNALOFXIANUNIVERSITYOFIKISANDTELECi)MMUNICATIONSVo1.15No.5基于CPLD的BCH碼編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)張高記,羅朝霞2(1.西安郵電學(xué)院通信與信息工程學(xué)院,陜西西安710121;2.西安郵電學(xué)院電子工程學(xué)院,陜西西安710121)摘要:為提高BCH編僻碼器系統(tǒng)性能,使硬件設(shè)計(jì)更具靈活性,提出了一種基于CPLD的BCH編/譯碼器實(shí)現(xiàn)方法.通過(guò)設(shè)計(jì)BCH(57,44,6)編/譯碼器,對(duì)BCH碼的構(gòu)造方法,BCH編僭碼器進(jìn)行了研究.論述

2、了一種基于復(fù)雜可編程邏輯器件,采用模塊化設(shè)計(jì)思想,利用VHDL硬件描述語(yǔ)言實(shí)現(xiàn)BCH編僻碼器的方法;在QuartusII軟件環(huán)境下給出了BCH(57,44,6)編/譯碼器的仿真結(jié)果,并在CPLD器件上驗(yàn)證實(shí)現(xiàn).仿真和實(shí)驗(yàn)都證明了這種方法的可行性和正確性.關(guān)鍵詞:CPLD;VHDL;BCH碼;編碼器;Meggitt譯碼器中圖分類號(hào):TN919.3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):10073264(2010)050030040引言BCH(BoseChaudhuriHocquenghem)碼是一類特別適用于隨機(jī)差錯(cuò)校正的循環(huán)校驗(yàn)碼,也是最重要且最有效的線性分組碼之一,由Bose,Chaudhuri和Hocqu

3、enghem在1950年1960年問提出l1J.BCH碼具有嚴(yán)格的代數(shù)結(jié)構(gòu),能靈活地選擇碼參數(shù),如分組長(zhǎng)度和碼率,所以是到目前為止研究得最為詳盡,應(yīng)用最為廣泛的一類碼【2J.BCH編/澤碼器可通過(guò)硬件或軟件實(shí)現(xiàn).軟件實(shí)現(xiàn)方法特另lI適合計(jì)算機(jī)通信網(wǎng)等場(chǎng)合,可以直接利用網(wǎng)中的計(jì)算機(jī)進(jìn)行編碼和譯碼,不需要另加專用設(shè)備,但軟件實(shí)現(xiàn)速度較慢;硬件實(shí)現(xiàn)方法速度較高,比軟件實(shí)現(xiàn)可快幾個(gè)數(shù)量級(jí),適合于對(duì)實(shí)時(shí)性要求較高的語(yǔ)音,視頻等數(shù)字通信系統(tǒng)J.傳統(tǒng)硬件實(shí)現(xiàn)方法,主要采用傳統(tǒng)數(shù)字邏輯電路設(shè)計(jì)來(lái)實(shí)現(xiàn),即通過(guò)大規(guī)模集成電路來(lái)實(shí)現(xiàn),這種設(shè)計(jì)方法存在結(jié)構(gòu)復(fù)雜,體積大,集成度低,穩(wěn)定性不高等缺點(diǎn),而基于CPLD的硬件

4、設(shè)計(jì)方法,正好可以克服這些缺點(diǎn),使電路設(shè)計(jì)更具靈活性和便捷性,便于實(shí)現(xiàn)系統(tǒng)的小型化,集成化.文中以BCH(57,44,6)碼為例研究了基于CPLD的BCH編/澤碼器的設(shè)計(jì)方法,選用Altera公司的可編程邏輯器件EP1CAQ240C8,在Quartus開發(fā)環(huán)境下,實(shí)現(xiàn)BCH編/譯碼器.BCH編碼器原理及實(shí)現(xiàn)1.1BCH(57,44,6)編碼器的原理BCH碼的結(jié)構(gòu)完全建立在有限域的基礎(chǔ)上,可以用近世代數(shù)的方法精確描述【.(57,44,6)BCH碼是一個(gè)系統(tǒng)循環(huán)碼,其產(chǎn)生的具體步驟為:(1)將信息多項(xiàng)式inf(z)預(yù)乘Xn;(2)將inf(z)除以g(z),得余式r(x);(3)系統(tǒng)循環(huán)碼的碼多項(xiàng)

5、式為c(z):inf(1z)z一+r(z)的形式【5l.由上述(57,44,6)BCH碼的產(chǎn)生過(guò)程可以看出:構(gòu)造一個(gè)(57,44,6)BCH碼的關(guān)鍵是要找出該碼的生成多項(xiàng)式g(z).當(dāng)碼長(zhǎng)及糾錯(cuò)能力給定后可以這樣來(lái)構(gòu)造生成多項(xiàng)式:因?yàn)?57,44,6)BCH代碼是以二元擴(kuò)域GF(2)N-元域GF(2)的變換為基礎(chǔ)的,故首先應(yīng)找到一個(gè)6次的本原多項(xiàng)式P(z):+z十1,產(chǎn)生一個(gè)GF(2)擴(kuò)域;然后在GF(2)上找一個(gè)本原元,利用本原多項(xiàng)式P(z)的根計(jì)算2個(gè)連續(xù)冪次根a,a,a=口所對(duì)應(yīng)的GF(2)域上的最小多項(xiàng)式ml(z)=,27+1,m2(z)=.+,27+1,m2(z)z.+z+./7+z

6、十1,這收稿日期:201007一l5作者簡(jiǎn)介:張高記(1968一),男,陜西禮泉人,西安郵電學(xué)院通信與信息工程學(xué)院工程師.第5期張高記,等:基于CPLD的BCH碼編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)?31?里t為BCH代碼能糾正差錯(cuò)的個(gè)數(shù),(57,44,6)BCH碼可糾兩個(gè)錯(cuò)誤,即t=2;最后計(jì)算這些最小多項(xiàng)式的最小公倍式LCM(LeastCommonMultiple),得到生成多項(xiàng)式g(.z):g(z)=LCM771(z),2(),2(z)=z134-.;1712+lzll+X10+z9+8+3;6+z3+z+1利用該生成多項(xiàng)式,就可構(gòu)造(57,44,6)BCH循環(huán)碼編碼器.(57,44,6)BCH循環(huán)碼

7、編碼器的電路結(jié)構(gòu)如圖116所示.當(dāng)開關(guān)A和B閉合,C打開時(shí),編碼器接收輸入信息位,并且直接將其變換成編碼輸出碼元,同時(shí)將輸入信息位送給遞歸移位寄存器組用來(lái)計(jì)算余式r(X);當(dāng)信息位數(shù)據(jù)都被處理完之后,開關(guān)A和B打開,C閉合,余數(shù)依次移位輸出,形成編碼器輸出.圖1(57.44.6)BCH碼的編碼器電路結(jié)構(gòu)圖1.2(57,44,6)BCH碼編碼器的CPLD實(shí)現(xiàn)采用模塊化的設(shè)計(jì)思想,BCH編碼器電路包括除法電路,控制電路和輸出電路等三個(gè)模塊組成,每一模塊對(duì)應(yīng)一部分VHDL的設(shè)計(jì)文件,這樣利于程序的編寫和調(diào)試,從而降低了整個(gè)程序的調(diào)試難度,提高了軟件的可維護(hù)性和可讀性【.BCH(57,44,6)編碼器

8、電路框圖如圖2所示.圖2【57,44,6)BCH碼編碼器電路框圖(57,44,6)BCH碼編碼器時(shí)序仿真結(jié)果如圖3所示.下面舉例說(shuō)明該編碼器的編碼過(guò)程,假定輸入消息序列為:din=(111011011100101l101O1001l000011101l001010l00),因?yàn)?57,44,6)BCH碼是系統(tǒng)碼,故控制電路在輸人數(shù)據(jù)din的前44拍時(shí)發(fā)控制信號(hào)給輸出電路使編碼器輸出碼元clout等于din;44拍結(jié)束時(shí),除法電路的內(nèi)容就是余式,在接下來(lái)的13拍,輸出電路在控制電路的控制下依次輸出余數(shù)1100111010011,至此57拍對(duì)一個(gè)輸入數(shù)據(jù)的編碼完成.(57,44,6)B編碼器的完整

9、編碼輸出序列為:dout=11101101110010111010100110000111011001010l001100111010011圖3(57.44,6)BCH碼編碼器時(shí)序仿真結(jié)果2BCH譯碼器原理及實(shí)現(xiàn)BCH碼的譯碼分為頻域譯碼和時(shí)域譯碼.頻域譯碼是把碼字看作一個(gè)時(shí)域數(shù)字序列,對(duì)其執(zhí)行有限域的離散傅立葉變換(DFT)將它變換到頻域,然后利用其頻域特點(diǎn)譯碼.而時(shí)域譯碼是把碼字看成時(shí)間軸上的信號(hào)序列,利用碼的代數(shù)結(jié)構(gòu)進(jìn)行譯碼l8j.到目前為止,BCH碼在時(shí)域和頻域內(nèi)有很多種有效地譯碼器,Meggitt譯碼器就是其中之一.Meggitt譯碼器不僅可以用在時(shí)域譯碼,而且也可以用于頻域譯碼.這

10、里僅介紹Meggitt譯碼器在時(shí)域的譯碼.2.1Meggitt譯碼器的原理Meggitt譯碼器是利用循環(huán)碼的循環(huán)特征設(shè)計(jì)出來(lái)的一類譯碼算法,它的思路主要有兩條:(1)S(-z)和E(z)模g(z)相等并不能斷言兩式全等,但是如果能使E(z)的次數(shù)低于g(z)的次數(shù),zte,那么兩者模g()相等等效于兩者全等.為此,可利用循環(huán)特性把差錯(cuò)多項(xiàng)式E(-z)的次數(shù)循環(huán)得低于nle次,以達(dá)到E(:)與S()的一一對(duì)應(yīng)5l.(2)接收碼R(z)的循環(huán)對(duì)應(yīng)于差錯(cuò)E(X)的循環(huán),部分高位的差錯(cuò)(E(x)次數(shù)大于,z一是),可以通過(guò)循環(huán)變?yōu)榈臀徊铄e(cuò)(次數(shù)低于一是).這樣識(shí)別一個(gè)重量小于等于t且次數(shù)小于一是的可糾

11、正圖案,就等效于識(shí)別循環(huán)前的一類差錯(cuò)5l.根據(jù)Meggitt譯碼器的算法思路,Meggitt譯碼器的譯碼過(guò)程可分成以下三步進(jìn)行,如圖4【】所示.)計(jì)算電路(除法電路)n位移位寄存器圖4(57.44.6)Meggitt譯碼器C()?32?西安郵電學(xué)院2010年9月(1)由接收碼尺()計(jì)算伴隨式S(x)(用g(x)除法電路);(2)由伴隨式s(z)計(jì)算差錯(cuò)圖案估值E(z)(用各種譯碼,差錯(cuò)識(shí)別電路);(3)由差錯(cuò)圖案估值E(X)求譯出碼字C(z)(用關(guān)系式C(x)=R(z)一E(z)J.2.2(57.44,6)BCH碼的Meggitt譯碼器伴隨式的計(jì)算Meggitt譯碼器利用了BCH碼的循環(huán)性質(zhì),

12、使得該譯碼器對(duì)于僅有少數(shù)差錯(cuò)需要校驗(yàn)的代碼是非常有效的.由于只校驗(yàn)最高位位置的差錯(cuò),然后計(jì)算循環(huán)移位,所以實(shí)際上所有被破壞的位都要通過(guò)MSB位置,并且得到校正J.(57,44,6)BCH碼具有校正兩個(gè)差錯(cuò)的能力,如果僅有MSB位置的差錯(cuò)需要校正,那么由于伴隨式和錯(cuò)誤圖樣之間的映射單元必須能識(shí)別出所有單個(gè)和兩個(gè)錯(cuò)誤,故需存儲(chǔ)總數(shù)為1+(56/1)=57個(gè)不同的錯(cuò)誤圖樣,合理設(shè)計(jì)電路,采用VHDL硬件設(shè)計(jì)語(yǔ)言進(jìn)行描述,通過(guò)Quartus軟件仿真,可以計(jì)算這57個(gè)伴隨式.表1中簡(jiǎn)要列出了可能的差錯(cuò)圖樣及相應(yīng)地伴隨式.表1可能的差錯(cuò)圖樣及伴隨式表錯(cuò)誤圖樣E伴隨式S10010110o1001101010

13、10100o00101001111000011111001000101000O00l10001l11001011100001011000001101101111011001100111001O0110001l10010011011111001001l01002.3(57.44,6)BCH碼的Meggitt譯碼器電路組成及仿真實(shí)現(xiàn)譯碼電路通常比編碼電路復(fù)雜得多.一個(gè)好的譯碼方法不僅應(yīng)使糾錯(cuò)能力達(dá)到理論極限,而且應(yīng)能高速度,低成本地實(shí)現(xiàn)J.選用CPLD器件設(shè)計(jì)譯碼器電路即可達(dá)到這一要求.根據(jù)(57,44,6)BCH碼的Meggitt譯碼器原理,采用自頂向下的模塊化設(shè)計(jì)方法,用VHDL硬件描述語(yǔ)言設(shè)

14、計(jì)的(57,44,6)BCH碼譯碼器電路框圖如圖5所示.整個(gè)電路包括除法電路,錯(cuò)誤圖樣識(shí)別電路,57級(jí)緩存電路和輸出電路等四個(gè)模塊.輸入數(shù)據(jù)din57級(jí)緩存電路圖5(57,44,6)BCH碼Meggitt譯碼器電路框圖該Meggitt譯碼器具有兩個(gè)級(jí).第一階段(57拍),通過(guò)除法電路計(jì)算伴隨式S(X);第二階段(57拍)通過(guò)查詢差錯(cuò)圖樣伴隨式表,進(jìn)行實(shí)際的差錯(cuò)校正.圖6為(57,44,6)BCH碼Meggitt譯碼器的時(shí)序仿真結(jié)果.圖6中的(a)所示,假設(shè)譯碼器輸入序列為:din=1110110111001011101010011000011101100101O100l100111010011

15、(圖3中編碼器輸出序列)無(wú)差錯(cuò),譯碼器輸出dout等于din,差錯(cuò)告警輸出為全0,表示無(wú)差錯(cuò);圖6中的(b)所示,假設(shè)譯碼器輸入序列為:din=ll0011O11100lO11l010100l1OOO011101l0010101O011001l10l0011(第3位有1個(gè)差錯(cuò)),dout=11101101110010111010100110000111011001010100l1001110100l1(等于圖3中編碼器的輸出序列),差錯(cuò)告警第3位輸出一個(gè)脈沖,表示有1個(gè)差錯(cuò),輸出結(jié)果進(jìn)行了糾錯(cuò);圖6中的(c)所示,假設(shè)譯碼器輸入序列為:din=1100110111001011101010011

16、00O01110110010101001100111010001(第3,56位共2個(gè)差錯(cuò)),00OOO0l0叭l2345678一第5期張高記,等:基于CPLD的BCH碼編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)?33?dout=11101101110010111010100110000111011001010l00110011101o011(等于圖3中編碼器輸出序列),差錯(cuò)告警第3,56位各輸出一個(gè)脈沖,表示有2個(gè)差錯(cuò),輸出結(jié)果進(jìn)行了糾錯(cuò).fa1無(wú)差錯(cuò)時(shí)的仿真結(jié)果舔懶P;.L一一Jn00u0.0t0uLi0-一一一一一一一一一一一一一一一一(b)有一個(gè)差錯(cuò)時(shí)的仿真結(jié)果rc1有二個(gè)差錯(cuò)時(shí)的仿真結(jié)果圖6(57.44,

17、6)tH碼Meggitt譯碼器時(shí)序仿真結(jié)果從仿真結(jié)果可以看出,該Meggitt譯碼器符合設(shè)計(jì)要求.3結(jié)論Meggitt譯碼器作為一種通用循環(huán)碼譯碼器.從原理上說(shuō),它可以用于任何循環(huán)碼或縮短循環(huán)碼的譯碼.但實(shí)際上,該譯碼器的復(fù)雜度隨糾錯(cuò)能力的增加而飛速增長(zhǎng),因此,當(dāng)t3時(shí),或突發(fā)差錯(cuò)超過(guò)每碼字一次時(shí),一般不用此種譯碼器.漢明碼的t=1,所用差錯(cuò)圖樣可歸人同一類,特別適合用Meggitt譯碼.設(shè)計(jì)中采用自頂向下的設(shè)計(jì)方法,利用VHDL硬件描述語(yǔ)言對(duì)BCH編/譯碼器進(jìn)行設(shè)計(jì),在Quartus11集成開發(fā)平臺(tái)上進(jìn)行仿真,綜合,并下載到EP1C6Q240C8可編程邏輯器件中得以驗(yàn)證.實(shí)驗(yàn)證明用該方法進(jìn)行

18、設(shè)計(jì)可縮短設(shè)計(jì)周期,提高系統(tǒng)集成度及性能,使電路設(shè)計(jì)更具靈活性.本設(shè)計(jì)還具有一定的通用性,它的邏輯大部分只涉及到編/譯碼器本身,而與外部的接口十分簡(jiǎn)單,并且對(duì)其它的設(shè)計(jì)是十分獨(dú)立的.另外,由于選用器件資源比較豐富,故對(duì)其進(jìn)行功能添加十分方便,只需添加電路設(shè)計(jì)而不必對(duì)原有電路進(jìn)行修改.參考文獻(xiàn)1吳湛擊.現(xiàn)代糾錯(cuò)編碼與調(diào)制理論及應(yīng)用M.北京:人民郵電出版社,2008.2JunhoCho.EfficientSoftware-BasedEncodingandDecodingofBCHCodesJ.IEEETRANSACTIONSONC0M_PUTERS,2009,58(7):878889.3寧楠.一種

19、基于FPGA的糾錯(cuò)編譯碼器的設(shè)計(jì)與實(shí)現(xiàn)J.通信技術(shù),2008(8):5661.4盧開澄.編碼理論與通信安全M.北京:清華大學(xué)出版社,2006.5張宗橙.糾錯(cuò)編碼原理和應(yīng)用M.北京:電子工業(yè)出版社,2003.6劉凌.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)M.北京:清華大學(xué)出版社,2003,7羅朝霞.CDMA系統(tǒng)中反向鏈路卷積編碼器的CPLD實(shí)現(xiàn)J.西安郵電學(xué)院,2005,10(1):5861.8李雄飛.縮短BCH碼(16,8,5)編譯碼算法及其實(shí)現(xiàn)J.空間電子技術(shù),2009,6(2):8489.9王進(jìn)宏.BCH(15,7,5)糾錯(cuò)譯碼的MATLAB實(shí)現(xiàn)J.華東理工學(xué)院,2006,29(1):97102.ImplementationofBCHcoder/decoderbasedonCPLDZHANGGao-ji,LUOZhao-xia2(1.SchoolCommunicationandInformationEngineering,XianUniversityofPostsandTelecommunications,Xian710121,China;2.SchoolofElec