RS碼仿真與基于RiBM算法的硬件實現

張紹練，高世杰，吳志勇*

（1.中國科學院長春光學精密機械與物理研究所，吉林長春130033；2.中國科學院大學，北京100049）

RS碼仿真與基于RiBM算法的硬件實現

張紹練1，2，高世杰1，吳志勇1*

（1.中國科學院長春光學精密機械與物理研究所，吉林長春130033；2.中國科學院大學，北京100049）

分析了里德-所羅門碼（RS碼）的誤碼率性能，提出了一種基于RiBM算法的RS（15，9）譯碼器。該譯碼器采用流水線結構，通過RiBM算法求解關鍵方程，在此基礎上將高斯加性白噪聲（AWGN）引入光纖模擬大氣激光通信系統，并在現場可編程門陣列（FPGA）平臺上完成了測試。測試結果表明：提出的譯碼器譯碼速率達到1.11 Gbit/s，為A1tera IP核的3.54倍。RiBM算法具有硬件復雜度低、關鍵路徑延時短的優點，能滿足系統譯碼的要求。

RS碼；現場可編程門陣列（FPGA）；RiBM算法；誤碼率；譯碼速率

1 引 言

大氣激光通信是利用激光束作為載體在大氣中進行語音、數據、圖像信息雙向傳送的一種技術，在解決“最后一公里”問題、應急通信等方面具有良好的應用前景[1]。大氣對激光傳輸產生光強閃爍、波前畸變等影響，從而影響激光通信距離、誤碼率等工作性能，所以如何抑制大氣信道影響是一個必須突破的技術難點[2]。大氣激光通信系統的高實時性、高可靠性要求傳輸系統的誤碼率極低，為了保證相同的通信質量，采用信道編碼所獲得的增益可以提高通信距離，節省發射功率[3-5]。

1960年，Reed和So1omon應用MS多項式構造的RS碼是性能優良的多進制BCH（Bose Chaudhuri-Hochquenghem）碼，為極大最小距離可分碼（MDS碼）[6]，相比于其它線性分組碼，在同樣的編碼效率下，它具有較強的糾錯能力。在現有的大氣激光通信系統中RS碼是最有效、應用最廣的糾錯編碼之一，具有同時糾正隨機和突發兩種差錯的能力。它通過高斯加性白噪聲（AWGN）信道模擬大氣激光通信信道，用Simu-1ink仿真分析2-PAM（Pu1se Amp1itude Modu1ation脈幅調制）+RS碼在有無突發干擾情況下對大氣激光通信系統誤碼率性能的影響，并用RS碼直觀地說明圖像去噪的糾錯能力。一般來說，對于定義在有限域GF（2m）符號位寬度為m的RS碼，其碼字長度n=2m-1，這類RS碼稱為系統碼或全碼[7]。全碼的譯碼裝置包括伴隨式計算、關鍵方程求解、Chien搜索、Forney算法和錯誤求解4個部分，其中關鍵方程求解是RS譯碼過程中最復雜最重要的步驟。目前常見的求解算法，包括iBM（B1ahut）、iBM（Ber1ekamp）、Euc1idean和Euc1idean（fo1ded）算法，都無法很好地滿足大氣激光通信系統對數據高速處理的要求[8]。高速的激光通信系統要求較高的RS碼譯碼速率，因此提高求解速率對于硬件處理速率至關重要。

為了適應硬件設計的需要，由Ber1ekamp和Massey最早提出的BM算法幾經修改，主要有無逆BM算法（iBM）和重組的無逆BM算法（RiBM）。Di1ip V.Sarwate，Naresh R.Shanbhag于2001年提出RiBM算法[6]，該算法的硬件結構可采用規整的脈動陣列并行實現，門限復雜度更低，控制結構更簡單，能夠實現的譯碼速率更高，從而符合大氣激光通信系統對譯碼速率的要求。本文選用碼長n=15，信息長度k=9，碼率為3/5的RS（15，9）碼來降低誤碼率和設計難度；并對RS（15，9）碼用QuartusⅡ完成了基于RiBM算法的譯碼器電路設計，最終在現場可編程門陣列（FPGA）平臺上得以實現。

2 RS碼誤碼率性能分析及圖像去噪

2.1 Simulink仿真分析RS碼誤碼率性能

對于強度調制/直接探測（IM/DD）的探測體制，理論和實驗早已證明在弱起伏大氣湍流下，大氣激光通信信道是低頻對數正態分布+高頻高斯噪聲的混合信道，在強起伏大氣湍流下，其信道是低頻負指數分布或低頻K分布+高頻高斯噪聲信道，而不是單一的高斯噪聲信道。可用SDGN（Signa1Dependent Gaussian Noise）模型模擬FSO（Free Space Optica1）信道[9]。為便于Simu1ink建模以及簡化Mat1ab運算，將大氣信道簡化為AWGN信道。理想AWGN信道只有當信噪比≥-1.6 dB時，才可能實現無差錯傳輸[10]。通過在AWGN信道中配置突發干擾所占比例W，可近似模擬大氣激光通信信道。

2-PAM+RS碼AWGN信道仿真模型如圖1所示。數據源產生每幀1 000·k·1og2（n+1）= 36 000個碼元的偽隨機二進制序列，經過RS（15，9）編碼、2-PAM調制、受突發干擾的高斯信道、2-PAM解調、RS（15，9）譯碼后統計編碼前后的誤碼率。

圖1 2-PAM+RS碼AWGN信道仿真模型Fig.1 Simu1ation mode1of2-PAM+RS codes in AWGN channe1

不考慮突發干擾，當信噪比為4 dB時輸出誤碼率在Disp1ay上顯示為10-2，而通過RS（15，9）碼編碼輸出誤碼率在Disp1ay1上顯示為10-4，編碼數據相比未編碼數據誤碼率提高了2 dB。

Simu1ink仿真結果如圖2所示。由圖可知，誤碼率隨著信噪比的增加而下降。在相同的信噪比下，有突發干擾的信道的誤碼率比無突發干擾的信道的誤碼率高。信道質量較差時，編碼對于接收數據誤碼率改善不大。當信道信噪比大于0 dB以后，編碼后對于誤碼率的改善非常明顯，可見RS編碼在理論上對于通信系統性能的改善是非常可觀的。

圖2 AWGN信道RS（15，9）編碼前后有無突發干擾時的誤碼率與信噪比的關系Fig.2 Re1ationship between BER and SNR of fore-andaft RS（15，9）encodings and with or without burst turbu1ences in AWGN channe1

2.2 RS碼的圖像去噪效果

為了更形象地觀察RS碼對信道傳輸性能的改善效果，將RS碼對受高斯噪聲污染的圖像進行處理，如圖3所示。由Mat1ab仿真可知，在相同的信噪比下，誤碼率隨著編碼效率的降低而減小。

圖3 RS碼對圖像的去噪效果Fig.3 RS′s noise suppressing effect for figure

3 RS（15，9）編譯碼原理及流水線結構

3.1 RS編碼

RS（15，9）碼可糾正t=（n-k）/2=3個錯誤[11]。信息多項式為m（x）=m8x8+m1x+m0，其中x代表信息位，mi（i=0，…，8）代表信息值。碼字生成多項式為：

式中，α代表生成元，則監督多項式表示為：

最終碼字多項式為U（x）=p（x）+x6m（x）。

硬件上通過6級4位二進制乘除法的線性反饋移位寄存器（LFSR）電路實現RS時域編碼器。

3.2 RS譯碼

若碼字中存在v個錯誤，位置分別在xj1，xj2，…，xjv，錯誤位置號為βi=αil，則錯誤圖樣多項式表示為：

式中：eji（i=1，…，v）代表錯誤值，r（x）表示受破壞的碼字多項式，為發射多項式和錯誤圖樣多項式之和，即r（x）=U（x）+e（x）。

譯碼目的是從r（x）中計算出e（x），進而糾正U（x）。若v≤t，譯碼器能夠正確譯碼。

本文通過采用四級流水線（pipe1ine）結構提高RS譯碼器處理速度：

3.2.1 一級流水：伴隨式計算

3.2.2 二級流水：關鍵方程求解

伴隨多項式表示為：

錯誤位置多項式定義為：

錯誤值多項式定義為：

這3個多項式的關系可通過關鍵方程描述：

3.2.3 三級流水：錯碼糾正

一旦σ（x）和ω（x）從S（x）中確定下來，可用Chien搜索算法σ（x）=0找出錯誤位置x=，并通過Forney算法計算出錯誤值：

式中，todd表示不大于t的最大奇數。有限域的求逆運算采用ROM查表法實現。將FIFO（first-in first-out）里緩存的接收數據讀出與計算得到的錯誤位置對應的錯誤值相減完成糾錯過程。

3.2.4 四級流水：伴隨式檢驗

對于糾錯后碼字再進行一次伴隨式檢驗，若結果syndomes為0，則譯碼成功，否則說明譯碼失敗。

四級流水結構中關鍵方程（8）的求解是決定RS譯碼速率的關鍵。本文采用RiBM算法設計譯碼電路。

4 RiBM算法電路設計

RiBM算法的硬件實現結構包括兩個部分：一是控制單元CONTROL實現差值更新；二是10個功能相同的PE1計算單元串接實現多項式的脈動計算，如圖4所示。

PE1i兩鎖存器初始化值（0）和（0）：PE10至PE15分別為S0至S5；PE16至PE18都為0；PE19為1。

CONTROL單元兩鎖存器初始化值：κ（0）= 0；γ（0）=1。

運算過程：控制單元內計數器CNTR值r每個時鐘上升沿加1，根據κ（r）和（r）計算MC（r），并更新γ（r）和δ（r）；從PE19至PE10依次計算（r）和（r），并最終更新（r），進入下一輪迭代。

圖4 脈動RiBM算法結構，PE1計算單元和控制單元Fig.4 Skematic of homogenous systo1ic RiBM architecture，PE1 processor and CONTROL b1ock

迭代6次后，PE13至PE16的（6）為錯誤位置多項式λ（x）系數，PE10至PE12的（6）為錯誤值多項式ωh（x）系數。由Chien搜索算法λ（x）=0計算出錯誤位置x=，Forney算法公式（9）修正為：

由圖4可見，RiBM算法對RS（15，9）碼電路需要22個鎖存器，20個有限域乘法器，12個選通門，10個有限域加法器，只需要6個周期就完成關鍵方程求解，關鍵路徑延時Tmu1t+Todd（Tmu1t表示乘法器處理延時，Todd表示加法器處理延時）。RiBM算法能工作在很高的頻率上，數據吞吐量得到了極大的提高，在FPGA的實現上具有很強的靈活性和通用性。

5 RS碼的算法仿真與FPGA實現

5.1 基于A ltera IP核與基于RiBM算法的RS（15，9）譯碼器的時序仿真與比較

系統整體實現在QuartusⅡ中完成。采用A1tera公司Cyc1one系列的EP1C3T144I7芯片進行編譯，該芯片共有2，910個邏輯單元，59，904 bit的存儲單元，可用IO引腳104個。采用QuartusⅡ自帶的A1tera IP核實現的RS譯碼器，基于Ava1on-ST深度為三碼長的流水線結構，運用修正的歐幾里德算法MEA（modified Euc1idean a1gorithm）求解關鍵方程[12]。兩種方法實現的RS（15，9）譯碼器的編譯報告如表1所示。

表1 RS（15，9）譯碼器在EP1C3T144I7芯片中的編譯報告Table 1 Compilation report of RS（15，9）decoders in EP1C3T144I7 device

基于RiBM算法的譯碼器與基于A1tera IP核的譯碼器相比，雖然使用的邏輯單元多一些，但是占用的存儲單元比特和引腳卻少得多，總體上看耗費的硬件資源并不多，說明RiBM算法硬件復雜度低。系統頻率達到55.5 MHz，保證了譯碼效率。RS（15，9）譯碼器經過邏輯綜合、布局布線后的時序仿真如圖5所示。

在圖5（b）中驗證：（1）輸入0 1 2 3 4 5 6 7 8 9 9 8 13 13 13，輸出0 1 2 3 4 5 6 7 8 9 9 8 9 3 10，糾錯e（x）=7+14x+4x2；（2）輸入13 10 11 12 13 14 15 0 13 15 8 12 9 13 6，輸出9 10 11 12 13 14 15 0 1 15 8 12 9 13 6，糾錯e（x）=12x6+4x14；（3）輸入2 3 4 5 6 7 8 9 10 13 11 5 6 5 2，輸出2 3 4 56 7 8 9 10 5 11 5 6 5 2，糾錯e（x）=8x5；（4）輸入13 12 13 14 15 0 1 2 13 13 0 12 2 4 13，輸出不變，而syndomes=6 12 11 1 10 3，伴隨式不為0，說明譯碼失敗。

圖5 RS（15，9）碼譯碼器仿真Fig.5 Simu1ation of RS（15，9）decoder

可見RS（15，9）碼能糾正1到3個錯誤，說明RiBM算法正確。結合改進的隔列交織方式，使信道更加離散化，能夠承受13-18的突發誤碼[13]。

從圖5（a）和圖5（b）中標記的usedw可知，基于A1tera IP核的RS（15，9）譯碼器，FIFO需要緩存85個時鐘周期才能實現譯碼；而基于RiBM算法的RS（15，9）譯碼器，由于關鍵路徑延時短，FIFO只需要緩存24個時鐘周期就可實現譯碼，譯碼速率提高到IP核的85/24≈3.54倍。譯碼速率為：

式中：n為碼長，m為碼字位數，Tc1k為時鐘周期，NFIFO為FIFO緩存周期數，Npara11e1為并行通信總數[14]。

5.2 RS碼的FPGA實現

設計了大氣信道模擬板產生高斯噪聲，并配置選通門模擬大氣激光通信信道。硬件平臺與示波器顯示如圖6所示。

圖6 硬件平臺與示波器顯示Fig.6 Hardware p1atform and osci11ograph disp1ay

在自制光纖通信電路板上，發送板（左）產生4位循環計數數據流A，寫時鐘周期為60 ns，經FIFO以周期36 ns的讀時鐘讀取，經RS（15，9）碼編碼后數據流為B，FPGA再通過Nationa1Semiconductor公司的DS92LV2421并串轉換芯片將B發送到光纖。大氣信道模擬板（中）調用Xi1inx公司的AWGN Core 1.0[15]產生高斯噪聲，通過周期T可控的選通門控制引入B的誤碼個數，從而模擬大氣激光通信系統中的隨機噪聲，并將相加生成的誤碼數據流C發送給光纖。接收板（右）的DS92LV2422串并轉換芯片從光纖接收C，通過基于RiBM算法的RS（15，9）譯碼器糾錯，還原為數據流D，經FIFO以周期為60 ns的寫時鐘讀取，恢復出原始數據流E。示波器顯示為T=5時A與E的最高位MSB（most significant bit）比較，可見數據能完全恢復，每個碼字成功糾錯3個錯誤。

譯碼前后的系統延時及其數據比較如圖7所示（為方便觀察，將示波器反色顯示）。圖7顯示為T=0，即不引入噪聲時接收的C與譯碼后的D的MSB比較，可見譯碼延時868 ns，約24.1個讀時鐘周期（36 ns），表明實測與仿真結果符合。

圖7 譯碼前后的系統延時及其數據比較Fig.7 System de1ays and data comparison of fore-andaft decodings

6 結 論

通過Simu1ink仿真分析了RS碼對大氣激光通信系統誤碼率性能的影響，并在闡述RS（15，9）碼編譯碼原理的基礎上給出其Quartus II電路設計方案，譯碼器采用流水線結構，采用RiBM算法求解關鍵方程。RiBM算法是一種脈動陣列式的并行結構，具有低復雜度、高速譯碼的優點。設計的RS（15，9）碼譯碼器能對每個碼字（15個碼元）中的不大于3個碼元的錯誤進行糾正，譯碼速率達到1.11 Gbit/s，為A1tera IP核的3.54倍，滿足大氣激光通信系統高速率、高可靠性和高實時性的信息傳輸要求。最后在FPGA上實現了RS碼在大氣激光通信系統中的應用，表明采用FPGA實現該譯碼算法在工程上具有可行性。

[1] 杜安源，柯熙政.大氣激光通信系統中RS碼的研究與實現[J].光電工程，2004（增1）：44-47. DU A Y，KE X ZH.Study and imp1ementation of Reed-So1omon code in an atmospheric 1aser communication systerm[J]. Opto-Electronic Eng.，2004（Supp11）：44-47.（in Chinese）

[2] 付強，姜會林，王曉曼，等.空間激光通信研究現狀及發展趨勢[J].中國光學，2012，5（2）：116-125. FU Q，JIANG H L，WANG XM，etal..Research status and deve1opment trend of space 1aser communication[J].Chinese Optics，2012，5（2）：116-125.（in Chinese）

[3] 王怡.大氣無線激光通信信道編碼[D].哈爾濱：哈爾濱工程大學，2006. WANG Y.Atmospheric optica1wire1ess communication system channe1coding[D].Harbin：Harbin Engineering University，2006.（in Chinese）

[4] 李進，呂增明，陶宏江，等.適于高速CCD圖像數據光纖傳輸的糾錯技術[J].光學精密工程，2012，20（11）：2548-2558. LI J，LüZM，TAO H J，etal..Error correction techno1ogy for CCD image using high speed optica1 fiber transmission[J]. Opt.Precision Eng.，2012，20（11）：2548-2558.（in Chinese）

[5] 楊劍，韓建棟，秦品樂.視覺測量中可糾錯的編碼點識別及提取[J].光學精密工程，2012，20（10）：2293-2299. YANG J，HAN JD，QIN P L.Correcting error on recognition of coded points for photogrammetry[J].Opt.Precision Eng.，2012，20（10）：2293-2299.（in Chinese）

[6] 王新梅，肖國鎮.糾錯碼—原理與方法[M].西安：西安電子科技大學出版社，2001. WANG X M，XIAO G ZH.Errorcorrecting Code-Theory and Method，Revised Edition[M].Xi′an：University of E1ectronic Science and Techno1ogy of Xi′an，2001.（in Chinese）

[7] 趙旸，耿相銘.RS（16，12）縮短碼編譯碼原理及性能分析[J].通信技術，2012，45（02）：49-50. ZHAO Y，GENG X M.Encoding and decoding a1gorithm for RS（16，12）shortened codes and its performance ana1ysis [J].Communications Technology，2012，45（02）：49-50.（in Chinese）

[8] DILIP V S，NARESH R S.High-speed architectures for reed-so1omon decoders[J].IEEE T.VLSISYST.，2001，9（5）：641-655.

[9] KHAN M N，COWLEYW G.Signa1dependentGaussian noisemode1for FSO communications[C]//Communications Theory Workshop（AusCTW），2011 Austra1ian，Jan.31-Feb.3，2011，Me1bourne，Austra1ia.2011：142-147.

[10] 殷致云.FSO廣義信道特性研究[D].西安：西安理工大學，2009. YIN ZH Y.Research on the characteristics of FSO genera1ized channe1[D].Xi′an：Xi′an Techno1ogy University，2009.（in Chinese）

[11] Bernard Sk1ar，徐平平，宋鐵成，等.數字通信—基礎與應用[M].2版.北京：電子工業出版社，2002. BERNARD S，XU PP，SONG TCH，et al..Digital Communications-Fundamentals and Applications[M].2nd ed.Beijing：Pub1ishing House of E1ectronics Industry，2002.（in Chinese）

[12] 劉學，蘇建峰，孫婷.基于A1tera IP核的RS譯碼器的設計與實現[J].時間頻率學報，2010，33（1）：28-31. LIU X，SU JF，SUN T.Design and imp1ementation of a RSDECODER BASEd on A1tera′s IP core[J].J.Time and Frequency，2010，33（1）：28-31.（in Chinese）

[13] 魏強.大氣激光通信高速信道RS+交織復合碼的FPGA實現[D].哈爾濱：哈爾濱工業大學，2010. WEIQ.FPGA rea1ization of fast channe1RS+inter1eaving composite coding in atmospheric optica1communication[D]. Harbin：Harbin Institute of Techno1ogy，2010.（in Chinese）

[14] Nationa1Semiconductor Corporation 301101.DS92LV2421/DS92LV2422 10 to 75 MHz，24-bit Channe1Link IISeria1izer and Deseria1izer[EB/OL].[2010-05-25]http：//www.nationa1.com.

[15] DONG U L，WAYNE L，JOHN D V，et al..A hardware gaussian noise generator using the wa11acemethod[J].IEEE T. VLSISYST.，2005，13（8）：911-920.

Simulation of RS codes and hardware implementation based on RiBM algorithm

ZHANG Shao-1ian1，2，GAO Shi-jie1，WU Zhi-yong1*
（1.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Sciences，Changchun 130033，China；2.University of Chinese Academy of Sciences，Beijing 100049，China）
*Corresponding author，E-mail：wuzy@ciomp.ac.cn

To improve communication qua1ity and meet the re1iabi1ity requirement of data transmission，the Bit Error Rate（BER）performance of Reed-So1omon（RS）codes is ana1yzed，and a RS（15，9）hardware decoder based on Reformu1ated Inversion1ess Ber1ekamp-Massey（RiBM）a1gorithm is proposed.The decoder operates in pipe1ine architecture，and its key equation is reso1ved by the RiBM a1gorithm.On thatbasis，an atmospheric 1aser communication system is simu1ated by adding AdditiveWhite Gaussian Noise（AWGN）in a fiber，and it is tested on a Fie1d Programmab1e Gate Array（FPGA）p1atform.The experimenta1resu1t shows that decoding speed can be up to 1.11 Gbit/s，as3.54 times as that of A1tera′s IP core.The RiBM a1gorithm has advantages of 1ow hardware comp1exity and short critica1path de1ay，and can meet the demands of the decoding system.

Reed-So1omon（RS）codes；Fie1d Programmab1e Gate Array（FPGA）；Reformu1ated Inversion1ess Ber1ekamp-Massey（RiBM）a1gorithm；Bit Error Rate（BER）；decoding speed

TN918

A

10.3788/CO.20130602.0171

張紹練（1986—），男，貴州甕安人，碩士研究生，2010年于中國科學技術大學獲得學士學位，2013年于中國科學院長春光學精密機械與物理研究所獲得碩士學位，主要從事大氣激光通信信道編碼方面的研究。E-mai1：zs11ck@mai1.ustc. edu.cn

高世杰（1979—），男，吉林撫松人，博士研究生，助理研究員，2000年于哈爾濱理工大學獲得學士學位，2003年于中國科學院長春光學精密機械與物理研究所獲得碩士學位，主要從事高速光通信技術的研究。E-mai1：yoursjohn@163. com

吳志勇（1965—），男，內蒙通遼人，學士，研究員，博士生導師，1989年于長春理工大學獲得學士學位，主要從事光電測控設備總體技術、視頻調光調焦技術和光纖通訊技術的研究。E-mai1：wuzy @ciomp.ac.cn

1674-2915（2013）02-0171-08

2012-12-16；

2013-02-18

中國科學院長春光學精密機械與物理研究所創新工程資助項目（No.Y10532B110）