高速并行RS解碼器

高速并行RS解碼器1引言Reed-Solomon(簡稱RS)碼是差錯控制領(lǐng)域中一類重要的線性分組碼，具有較強(qiáng)的糾正突發(fā)錯誤和隨機(jī)錯誤的能力，廣泛應(yīng)用于各種差錯控制領(lǐng)域。RS解碼器可在FPGA或ASIC上實現(xiàn)IP核。但目前國內(nèi)RS編碼速度約為400Mb/s，糾錯能力為4bit，仍存在編碼速度低、糾錯能力不完善、系統(tǒng)的吞吐率受限等問題。因此提出一種改進(jìn)的IBM算法.進(jìn)一步提高RS編碼器的編碼速度及糾錯能力，擴(kuò)大應(yīng)用范圍。這樣RS編解碼器能夠?qū)崿F(xiàn)遠(yuǎn)距離傳輸信息，太空航天通信的快速存儲及全球定位系統(tǒng)需求。2RS編解碼原理2.1編碼原理m=(m0，m1…mk-1)表示GF(28)的k位信息符號序列，該信息矢量多項式：m(x)=m+m1x+…+mk-lxk-1。將左移2t位的信息多項式與生成多項式g(x)相除，得到：p(x)=x2m(x)modg(x)，c(x)=x2tm(x)+p(x)。顯然，以矢量表示編碼后的碼字為：C=(p，p，…p，m，m，…m)。編碼的碼字C中，信息位可以清晰地與校驗位區(qū)分開。因此，RS編碼的實質(zhì)就是解決以生成多項式g(x)為模的除法問題。2.2解碼原理RS解碼算法分時域解碼算法和頻域解碼算法。這里主要討論時域解碼算法。時域解碼是將碼字看成時間軸上的信號序列，利用碼的代數(shù)結(jié)構(gòu)進(jìn)行解碼。常見的IBM算法解碼分為四個步聚：①由接收的碼字R(x)計算伴隨式S(x);②根據(jù)關(guān)鍵方程計算錯誤值多項式w(a)和錯誤位置多項式σ(x);③錢搜索找到錯誤位置，并計算錯誤值;④糾正錯誤。圖1為RS編解碼系統(tǒng)原理圖，其中虛線框部分是編碼器流程。其余則為解碼流程。3實現(xiàn)RS(204，188)編解碼器3.1RS優(yōu)化的編碼方法傳統(tǒng)的編碼器算法實現(xiàn)RS(204，188)編碼器，需要16個有限域乘法器和16個有限域加法器。根據(jù)RS碼型的確定來固定RS碼的生成多項式，圖2中g(shù)0,g1……g15為常數(shù)，RS編碼器邏輯電路的乘法器則變?yōu)槌?shù)×變量的形式，利用有限域常數(shù)乘法器的特點，對編碼器進(jìn)行兩級優(yōu)化，具體操作如下：①)GF(28)域上的RS(204，188)生成多項式為：g(x)=(x+1)(x+a)(x+a2)…(x+a15)，其中a，a2…a15為GF(28)的本原元。生成多項式確定后，計算得到生成多項式的16個系數(shù)g0，g1…g15。當(dāng)有限域乘法器的一個乘數(shù)為常數(shù)時，乘數(shù)運算時只需模2運算所需的異或門而不用與門;②預(yù)先計算出現(xiàn)頻率較高的并或運算，使用新元素代替矩陣中重復(fù)出現(xiàn)的異或計算，這樣就實現(xiàn)乘法器結(jié)構(gòu)的第二級優(yōu)化。利用上述兩種優(yōu)化RS編碼器的乘法器的方法能夠?qū)崿F(xiàn)RS(204，188)編碼器，可節(jié)省RS(204，188)編碼器資源20%。3.2解碼實現(xiàn)電路RS(204，188)編碼解碼器的解碼按以下四個步驟實現(xiàn)：①從接收到的碼字R(x)計算伴隨式S(x);②利用IBM算法計算錯誤位置多項式σ(x)和錯誤值多項式w(x);③利用錢搜索算法找出錯誤位置;④利用Fomey算法計算錯誤值，與FIFO控制器所存儲的接收碼字相異或，得到正確的傳輸碼字。圖3給出RS(204，188)編解碼器的解碼電路。3.3改進(jìn)的流水線結(jié)構(gòu)圖4給出了傳統(tǒng)和改進(jìn)的流水線結(jié)構(gòu)對比。傳統(tǒng)的流水線結(jié)構(gòu)各模塊處理周期差距很大，約達(dá)8：1比例，造成周期極大浪費。改進(jìn)的流水線結(jié)構(gòu)則采用時分復(fù)用，可在相應(yīng)的處理周期不變的情況下可將并行處理的數(shù)據(jù)率提高到原數(shù)據(jù)率的8倍。4FPGA仿真測試在OuatusⅡ5.O平臺上采用Verilog編寫編解碼器代碼，測試步驟為：分析與綜合;生成功能網(wǎng)表;配置輸入信號波形;功能仿真;整體編譯;時間仿真。4.1系統(tǒng)性能測試(1)資源利用率綜合功能仿真和時間仿真的編譯報告，系統(tǒng)占用資源詳細(xì)情況如表1所示。(2)解碼數(shù)據(jù)率解碼數(shù)據(jù)率=每幀數(shù)據(jù)的字節(jié)數(shù)×解碼頻率/系統(tǒng)所需周期。采用Ahera公司的RS解碼器的IP器件，使用CycloneⅡ器件，其解碼數(shù)據(jù)率為104Mb/s。由該設(shè)計的時序仿真表明解碼器8路復(fù)用后的解碼數(shù)據(jù)率高達(dá)116.65Mb/s。(3)糾錯能力及糾錯仿真糾錯能力由碼型、解碼算法、控制信號、時鐘等因素共同決定，該設(shè)計的單路數(shù)據(jù)輸入解碼器最大糾錯能力為7字節(jié)/204字節(jié)(每幀數(shù)據(jù)204字節(jié)，糾正隨機(jī)錯誤7字節(jié))，接近RS碼的糾錯上限8字節(jié)/204字節(jié)。8位輸入數(shù)據(jù)發(fā)生錯誤：02H～09H變成了01H，經(jīng)系統(tǒng)糾錯得到正確的輸出波形。4.2系統(tǒng)構(gòu)造(1)查表法代替復(fù)雜的求逆單元為了獲得更高的解碼速率，使用更少的FPGA資源，系統(tǒng)設(shè)計使用標(biāo)準(zhǔn)基到復(fù)數(shù)基的變換與逆變換，用復(fù)數(shù)基進(jìn)行乘法器設(shè)計，除法器設(shè)計是把處理數(shù)據(jù)從標(biāo)準(zhǔn)基轉(zhuǎn)化為指數(shù)冪的表示形式，改用高效查表法代替復(fù)雜的求逆單元，將σ(x)的逆單元按照尋址方式轉(zhuǎn)換為表格形式，在程序中直接調(diào)用，簡化設(shè)計，提高了解碼頻率。(2)并行流水線結(jié)構(gòu)由于傳統(tǒng)設(shè)計是利用SC模塊求解伴隨式，KES模塊求解關(guān)鍵方程，CESS模塊求解錯誤位置和錯誤值，它們之間的處理周期差距很大，造成周期的極大浪費。而采用時分復(fù)用的流水線結(jié)構(gòu)可有效解決這一問題，對結(jié)構(gòu)簡單的模塊進(jìn)行復(fù)用，在處理周期基本不變的情況下，從而提高并行處理的解碼數(shù)據(jù)率。5結(jié)語RS編解碼器應(yīng)用于諸多系統(tǒng)，例如：在數(shù)據(jù)傳輸鏈路應(yīng)用中，可在SANDHB和SANTarget上安裝高速并行R