RS码仿真与基于RiBM算法的硬件实现

2013-04-26张绍练高世杰吴志勇

中国光学 2013年2期

关键词：译码器码字译码

张绍练，高世杰，吴志勇*

（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

10.3788/CO.20130602.0171