摘? 要: 提出了基于歐氏算法和頻譜分析相結合的RS碼硬件編譯碼方法;利用FPGA芯片實現了GF(2⁸)上最高速率為50Mbps、最大延時為640ns的流式譯碼方案,滿足了高速率的RS編譯碼需求。

　　關鍵詞: RS碼? FPGA? 伴隨式? 關鍵方程" title="關鍵方程">關鍵方程? IDFT

?

　　差錯控制編碼技術對改善誤碼率、提高通信的可靠性具有重要作用。RS碼既可以糾正隨機錯誤,又可以糾正突發錯誤,具有很強的糾錯能力,在通信系統中應用廣泛。由于RS碼的譯碼復雜度高,數學運算量大,常見的硬件及軟件譯碼方案大多不能滿足高速率的傳輸需求,一般適用于10Mbps以下。本文提出的歐氏算法和頻譜結構分析相結合的RS硬件解碼方案,適用于FPGA單片實現,速率高、延遲小、通用性強、使用靈活。筆者在FPGA芯片上實現了GF(2⁸)上符號速率為50Mbps的流式解碼方案，最大延時為640ns,參數可以根據需要靈活設置。

1 RS碼的結構

　　碼字長度為N=q-1(q=2ⁱ),生成多項式為g(x)=(x-α^m0)(x-α^m0)…(x-α^m0+1),的RS碼有最小碼距δ=2t+1,能夠糾正t個隨機或突發錯誤^[1]。本文列舉的方案測試中采用的RS碼主要參數為N=255、m₀=0、t=8,其中GF(2⁸)的生成多項式為g(x)=x⁸+x⁴+x³+x²+1。由于RS碼的編碼邏輯結構比較簡單,文中僅給出仿真結果。

2 RS碼的譯碼算法

　　RS譯碼算法一般分為三步:伴隨式計算、關鍵方程獲得和錯誤圖樣的求解。其中關鍵方程的獲得是RS譯碼中最困難、最為關鍵的一步。

　　在利用伴隨式求解關鍵方程時,BM算法和Euclidean(歐氏)算法是兩種較好的選擇。BM算法涉及大量的變量存儲和復雜的邏輯控制,適用于軟件編程而不適合硬件實現" title="硬件實現">硬件實現。歐氏算法數據存儲量少、控制便捷,適合硬件實現。且采用歐氏算法確定關鍵方程所需時間與錯誤個數成正比,因此從處理時間上考慮,歐氏算法也是較好的選擇。

　　在獲得關鍵方程后,采用時域處理方法,需要大量的運算單元和控制電路,在硬件實現中是不可取的。而采用頻譜結構分析方法,利用最短線性移位寄存器" title="移位寄存器">移位寄存器綜合及離散傅氏逆變換進行處理,邏輯簡單、耗時少,適合硬件實現。雖然在傅氏變換時需要較多的邏輯單元,但對GF(2ⁿ)在n<10的情況下,變換域譯碼器" title="譯碼器">譯碼器要比時域譯碼器簡單得多。因而本文提出了歐氏算法和頻譜結構分析相結合的方案,并在實踐中獲得了較好的效果。

　　Euclidean算法^[3]步驟如下:

3 方案流程

　　方案流程框圖如圖1所示。

?

?

3.1 伴隨式S₀，S₁，…,S_2t-1的計算

　　令r₁，r₂，…,r_n為接收到的RS碼字,根據系統碼監督矩陣的特性,可構造如圖2所示伴隨式計算電路S_i=(((r₁αⁱ+r₂)αⁱ+r₃)αi…)αⁱ+r_n，從而實現伴隨式序列的計算。

?

?

3.2 利用伴隨式確定關鍵方程

　　Euclidean算法的難點主要在于迭代計算過程中存在的被除數多項式和除數多項式長度的不確定性,使每次計算中產生的商序列的長度不等,以及因此可能涉及到的不定長多項式的相乘和相加問題,增加了硬件設計的難度。系統采用了嵌套雙循環的方法,利用‘時鐘產生2’控制外循環,‘時鐘產生1’控制內循環,從而優化了算法,得到了問題的解決方案。在獲得伴隨式的基礎上,圖3電路可具體完成Euclidean算法對關鍵方程的求解σ(x)=σ_tx^t+σ_t-1x^t-1+…+σ₁x+1。

?

?

3.3 利用最短線性移位寄存器綜合和離散傅氏變換

　　獲取錯誤圖樣

　　在得到關鍵方程后,首先應進行錯誤位置(關鍵方程的根)的確定,這樣可減小電路的規模;利用錢搜索^[1](工程上求解σ(x)根的實用方法)的方法可以簡捷地確定錯誤位置。然后,啟動最短線性移位寄存器綜合和離散傅氏逆變換,經過N次(運算所在域的長度)迭代,即可求得對應各個錯誤位置的錯誤圖樣，如圖4所示。用錯誤圖樣對接收碼字進行糾錯,就可得到正確的信息序列。

?

3.4 RS編譯碼在FPGA上的實現

　　有限域的乘法、加法運算單元和各模塊的控制邏輯設計是系統成功的關鍵。涉及有限域的各個運算單元的運算速度制約了譯碼器的速度,而控制邏輯引導了譯碼的流程。硬件電路的軟件開發工具給設計復雜電路提供了簡捷思路。系統采用了QUARTUS與第三方軟件相結合的方法,用VHDL語言設計了大部分功能模塊。特別是在乘法器" title="乘法器">乘法器設計中,乘數確定、被乘數不定的乘法器以及乘數、被乘數均不定的有限域乘法器,經邏輯綜合和優化設計后,運算速度可分別在6.8ns和11.6ns內完成,完全可以滿足系統符號速率50Mbps的要求。應該指出,系統速度的進一步提高受到求逆運算的限制,求逆運算沒有明確的數學結構(通常采用查表的方法),這是制約運算速度的瓶頸。但針對流式譯碼算法,上述結構已能滿足要求。

4 仿真結果

4.1 編碼器的仿真

　　仿真的時鐘頻率為50MHz,在EN為高電平時輸入信息有效。為簡單起見,采用系統碼的縮短型,即信息為(00，00，…,00,02,01,02)。編碼器的仿真結果如圖5所示。其中,IN為輸入信息,CLK為系統時鐘,C為編碼輸出(輸入和輸出均為16進制)。

?

?

4.2 譯碼器的仿真

首先,給出系統的仿真全貌,如圖6所示。其中C為接收到的RS碼,SP為伴隨式S15,shang為運用歐氏算法得到的商序列,SeryDA為S序列,anssd和ERTD分別對應碼字可能存在的第四個錯誤位置和錯誤值,仿真中的接收碼字在位置(105,106,107,108,109,110,111,112)上錯誤均為(01)_HEX。

?

?

　　伴隨式的計算結果：S₁₅,S₁₄,…,S₁,S₀為(FD,8D,CE,4A,51,B2,A1,CA,C4,0D,73,56,A6,F5,01),圖6和圖7中的sp即為S₁₅。

?

?

　　這里重點給出利用伴隨式計算關鍵方程的電路仿真結果,如圖7所示。當輸入伴隨式結果以后,運算電路啟動,在計算商序列的同時進行聯接多項式的迭代運算。歐氏算法的商序列shang為:(FF，58),(37，92),(50，45),(E9，C7),(F4，B9),(5D，33),(87,8F)。當滿足終止條件以后顯示標志QQC,同時,給出關鍵方程系數如圖7中(AI，AH，AG，AF，AE，AD，AC，AB，AA)即(00，19，2E，EC，A8，AD，41，E6，95)，對應有限域上的表達式為：

　　δ(x)=α¹⁹³x⁷+α¹³⁰x⁶+α¹²²x⁵+α¹⁴⁴x⁴+α²⁵²x³+α¹⁹¹x²+α¹⁶⁰x+α¹⁸⁴；

　　有解為(α¹⁰⁵，α¹⁰⁶，α¹⁰⁷，α¹⁰⁸，α¹⁰⁹，α¹¹⁰，α¹¹¹)，與假定錯誤位置完全一致。然后求解S序列,同時針對各錯誤位置進行IDFT,就可以得到對應的錯誤值。圖6中anssd和ERTD表示位置108上存在的錯誤為(01)_HEX。

??? 系統仿真表明,譯碼器獲得的錯誤位置和錯誤圖案與實際假設的錯誤位置(105,106,107,108,109,110,111)和錯誤值(01)HEX完全一致。

　　基于APEX架構的可編程單芯片RS編譯碼硬件解決方案在中國普天集團西安藍牙通訊設備有限公司的二次群無線擴頻通信機的改造項目中得到了應用。它可用于離散譯碼、流式譯碼,在添加一級緩存的基礎上,同樣適用于連續譯碼。

?

參考文獻

1 王新梅，肖國鎮.糾錯碼-原理與方法.西安：西安電子科技大學出版社, 2001

2 I.S.Reed. A Comparison of VLSI Architecture for Time and Transform Domain Decoding of Reed-Solomon Codes.

? University of Southern California， 1990

3 I.S.Reed. A Single Chip VLSI Reed-Solomon Decoder.University of Southern California， 1990

4 I.S.Reed.A VLSI Single Chip (255，233) Reed-Solomon?Encoder. University of Southern California, 1990

5 趙雅興.FPGA原理、設計與應用.天津：天津大學出版社,1999

6 侯伯亨，顧新.VHDL硬件描述語言與數字邏輯電路設計.西安：西安電子科技大學出版社,2001