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