基于CycloneIII构成的RS编码系统

苗 鑫，邓 攀，殷奎喜

（南京师范大学 物理科学与技术学院，江苏 南京210046）

基于CycloneIII构成的RS编码系统

苗 鑫，邓 攀，殷奎喜

（南京师范大学 物理科学与技术学院，江苏 南京210046）

本文采用Altera公司的FPGA器件Cyclone III系列EP3C10作为核心器件构成了R-S（255，223）编码系统；利用Quartus II 9.0作为硬件仿真平台，用硬件描述语言Verilog_HDL实现编程，并且通过JTAG接口与EP3C10连接。R-S（Reed-Solomon）码是一类纠错能力很强的特殊的非二进制BCH码，能应对随机性和突发性错误，广泛应用于各种通信系统中和保密系统中。R-S（255，223）码能够检测32字节长度和纠错16字节长度的连续数据错误信息。

Cyclone III；Quartus II 9.0；Verilog_HDL；R-S（255，223）码

R-S码是用其发明人的名字Reed和Solomon命名的。它是一类具有很强纠错能力的多进制BCH码，既可以纠正突发错误，也可以纠正随机错误。目前，RS编码作为许多通信系统的重要编码方式，已经在数字通信、数字视频广播、卫星通信等领域得到广泛的应用。现代通信系统中，纠错码技术是实现可靠通信的基本方法。RS（255，223）码被CCSDS选为常规分包遥测信道纠错编码和高级在轨系统前向和反向链路的纠错编码，是实现CCSDS标准低差率信道纠错编码的关键部件。

目前，随着大规模、超大规模集成电路的发展，现场可编程门阵列（FPGA）技术得到迅速的发展和广泛的应用，其资源容量、工作频率以及集成度都有很大的提高，基于FPGA实现的编解码器便更具有优点，有着频率分辨率较高，运算速度更快，性价比更高的优点。本文便是使用Altera公司的FPGA器件CycloneIII系列EP3C10作为核心器件。应用Verilog HDL这样一种应用广泛的硬件描述语言，也为实现硬件编程提供了很好的方法。RS编译码系统如图1所示。

1 RS（255，223）编解码原理

图1 编译码系统图Fig.1 Encoding and decoding system diagram

RS编码是在代数编码理论的总体理论框架上实现编码过程的，中心思想是将原始数据流映射到抽象的代数多项式上，在映射的过程进行一系列的数学运算。若有有限个符号，其数目是一个素数的幂，并且定义有加法和乘法，则称这个有限符号的域为有限域。若有限域中的符号数目为2m，则称此有限域为伽罗华域，记为GF（2m）。

对于一个（n，k，t）RS 码，表示此生成码长n=2m-1 个符号或m（2m-1）比特，且RS编码码字中有k个数据信息符号或km比特数据，能监督n-k=2t个符号或m（n-k）比特数据或者纠正数据传输和处理中产生的t个符号错误或mt比特数据错误，最小码距d=2t+1个符号或m（2t+1）比特，每个符号是m比特。

RS（255，223）码是多进制BCH码，编码器将每接收 223字节的串行字符数据信息块，编码为255字节的码字信息。码字信息由223字节长度的数据块和32字节长度的编码校验信息块组成，能够检测和纠错16字节长度的连续数据错误信息。

设输入的信息序列为

k=223，mk-i为伽罗华域 GF（255）中的域元素，代表的是RS（255，223）码中的数据信息，xk-i仅是数据码元位置的标记。例如mk-1表示第223个数据的大小，xk-1表示第223个数据位置。

生成的码字为

n=255，表示编码生成255字节长度的码字信息，同样cn-i代表是码字信息大小，cn-i到ck是数据信息，ck-1到c0是校验信息。

对于一个信息码多项式，RS校验码生成多项式的一般形式为：

由校验码生成多项式就可以生成校验码信息r（x）。k0是偏移量，通常取0或1，剩余多项式r（x）满足

将生成的剩余多项式加到信息多项式后就是生成的码字信息。

所以，实现RS编码首先明确，在RS码的运算过程中，所有的加减乘除的运算都是定义在伽罗华域上的模2运算。采集进来的数据，查找已生成的GF（2m）域与二进制代码对照表，把数据转化成GF（2m）域元素。根据以上公式算出校验码，再将校验码追加到信息码后，完成编码。

2 RS（255，223）编码实现

2.1 GF（256）域的算术运算

通常，GF（2m）域的算术运算可处理2m个元素，且m表示数据信息字符的位宽。例如ASDL系统使用的就是GF（256）域的算术运算，其初等多项式p（x）可用下列式子表示：

利用初等多项式可产生GF（2m）中任意D阶多项式f（x）其他各阶的项，例如：

表1是GF（256）域的全部元素。

由表1中可以看出，GF（28）的所有元素都可以利用1，α，…，α7的和来表示，将各表示多项式中的系数排列起来，可以实现GF（28）中所有元素的8 bit二进制表示。

表1 GF（28）的全部元素Tab.1 All elements of GF（28）

多项式的加减乘除可以转移到有限域上元素的加法和乘法运算，有限域上的加法和乘法遵循一定的法则，即加法遵循异或法则，乘法遵循与法则。例如GF（256）域上的两个元素α2，α4相加，将α2和α4对应项进行模二加法，对应项进行异或运算；域上的元素乘法，遵循与法则，例如两个元素α211，α223相乘，得到 α211·α223=α（211+233）mod255=α189。

GF（2m）域的任意多项式都可以利用其初等多项式得到一个唯一的 GF（2m）域中的对应多项式，因此，GF（2m）域的算术运算与 GF（2m）域相同。

2.2 RS（255，223）编码器的 FPGA 实现

2.2.1 GF（256）域乘法的FPGA实现

GF（256）域乘法运算是编码系统中最重要的算术运算，因此乘法运算的设计显得尤为重要，其所占用FPGA芯片的资源和速度也就决定了编码系统所占的资源和性能。本系统采用一种基于多项式乘法理论的8位串行乘法系统的设计方法，用Verilog_HDL硬件描述语言来描述乘法器的运算。

GF（256）域乘法运算算法可以表述为：将8位的乘数和被乘数用多项式表示，先按照多项式 乘法法则将此两个多项式做乘法，再对乘积多项式按照以为底做取模运算，由于生成多项式已知，所以对其进行超前运算过后可以得到结果符号多项式各阶系数对于输入多项式的函数。

对于 GF（256）域的元素[7:0]a，[7:0]b，生成多项式为：

GF（256）域的元素[7:0]a，[7:0]b 多项式表示为：

将两个有限域多项式按照多项式乘法规则作乘法，得到多项式：

将积多项式对生成多项式p（x）求模，可得化简的及多项式为：

由乘积多项式系数和取模后的多项式c（x）对应的关系为

由上式可知，GF（256）域的乘法运算过程只使用到了异或逻辑和与逻辑，对应GF（2）域的加法运算和乘法运算。

端口定义：input[7:0]a:输入的数据信息字符；input[7:0]b:输入的生成多项式各项的加权系数；output[7:0]c:乘积输出。

图 2 GF（256）域的乘法Fig.2 GF （256） field multiplication

整个乘法计算过程只使用到了异或逻辑和与逻辑，对应GF（2）域的加法运算和乘法运算。

2.2.2 RS（255，223）编码器的 FPGA 实现

RS（255，223）编码器的生成多项式 g（x）为

RS（255，223）编码器的电路主要部分有：线性反馈移位寄存器、有限域加法器、开关。该电路结构实际上是由32个加法器和32个乘法器构成的级联电路，从时序设计的角度来说，RS（255，223）编码器的电路结构具有32级流水线阶段，每个阶段包含了一个加法器、一个乘法器和一个D触发器组。在RS（255，223）编码器中，乘法器和加法器是主要的运算单元，因其所在域的特征为2.所以加法器可用异或逻辑来实现，乘法器是可用与逻辑来实现，因而大大的提高了硬件资源的使用效率。

图 3 RS（255，223）编码器电路结构Fig.3 RS （255，223） encoder circuit

Cyclone III是Altera公司开发的首款65 nm低成本FPGA，Cyclone III FPGA比竞争FPGA的功耗低75%，含有5 K至120 K逻辑单元（LE），比前一代产品每逻辑单元成本降低20%。使用Cyclone III来设计完成位宽为8 bit的RS（255，223）编码系统，芯片资源和管脚资源都可以满足其要求。

3 RS（255，233）编码仿真实现

本系统设计是在Quartus II9.0环境下，使用Verilog_HDL语言描述整个编码器模型，并且以Altera公司生产的EP3C10E144C8N FPGA芯片作为硬件平台进行实现。

系统设计端口定义：

clk:芯片时钟信号，编码器在其上升沿处进行数据采样并进行编码运算。

clrn:编码器异步复位控制信号。定义为1表示采样数据有效，编码器正常操作；定义为0表示采样数据寄存器清零，编码器复位清零。

enable:编码器使能控制信号。定义为1表示芯片对输入字符进行RS（255，223）编码；定义为0表示编码器继续采样，但不对其进行编码。

data:有效字符输入控制信号。定义为1表示输入字符无效；定义为0表示输入字符有效，编码继续进行。

x:数据信息块得字符输入端口，其位宽为8 bit。

y：编码码字输出端口，其位宽为8 bit。

打开 Quartus II 9.0， 使用 File菜单中的 “New Project Wizard”命令创建一个工程，然后新建一个Verilog_HDL语言文件，输入程序。编译通过以后，创建波形仿真文件，加入输入输出信号，进行仿真得到编码结果。

图4 编译结果Fig.4 Compiles the results

由编译结果可以看出，RS（255，223）编码使用 Cyclone III芯片的相关信息。芯片总的资源为10 320个逻辑单元，本设计使用了其中的303个；芯片总管脚有95个，本设计使用了其中的20个，占21%。

图 5 RS（255，223）编码系统仿真波形Fig.5 RS （255，223） coding system simulation waveform

编码系统在前223个字符信息输入时，直接输出x端得数据信息字符。此外，由于芯片内部的寄存器延迟效应，y端较x端滞后一个时钟周期；当223个字符信息（十六进制为DF）输出完毕后，有效字符输入控制信号data值由1变成0，编码系统开始进入冗余校验信息输出阶段，编码系统完成输出接收到的数据信息字符后，紧接着输出32个校验字符。输出数据字符是从01到223，32个校验码字符为184，32，247，171，36，60，227，188，154，55，147，106，94，94，20 3，163，227，48，127，207，53，23，106，196，188，77，106，51，16 7，148，14，65.

4 结束语

目前，随着电子技术的不断发展，各个FPGA生产厂家都已有自己的IP核可以使用，例如，Altera公司提供的Reed-Solomon编译器MegaCoreTM功能的IP核供给用户使用。本文介绍了一种基于Altera公司Cyclone III系列的RS编解码系统，可以实现 RS（255，223）的编解码。

[1]樊昌信，曹丽娜.通信原理[M].6版.北京：国防工业出版社，2007.

[2]陈亮，杨吉斌，张雄伟.信号处理算法的实时DSP实现[M].北京：电子工业出版社，2008.

[3]王金明.数字系统设计与Verilog HDL[M].北京：电子工业出版社，2011.

[4]田耕，徐文波，张延伟.无线通信FPGA设计[M].北京：电子工业出版社，2008.

[5]CHANG Xiao-jun，GUO Jun，LI Zhi-hui.RS encoder design based on FPGA[C]//ICACC 2010，2010:419-421.

[6]YAN Lai-jin，LI Ming.Design and implementation of RS（255，223） decoder on FPGA[J].Control&Automation，2005（1）:76.

[7]Seroussi G A.systolic reed-solomon encoder[J].IEEE Trans information Theory，1991，37（4）:45-48.

[8]许春风，李健，武文红.基于FPGA的RS（255，223）编码器的设计[J].微计算机信息，2006，22（9）：175-176.

XU Chun-feng，LI Jian，WU Wen-hong.Design of the RS（255，223） encoder based on FPGA [J].Microcomputer Information ，2006，22（9）:175-176.

[9]张怡，韩维.高速RS编码算法及FPGA实现[J].无线通信技术，2005（1）：23-30.

ZHANG Yi，HAN Wei.High speed reed-solomon encode algorithm and FPGA realization[J].Wireless Communications Technology，2005（1）:23-30.

[10]余旋.RS编码的FPGA实现[D].南京：东南大学，2008.

A RS coding system based on Cyclone III

MIAO Xin，DENG Pan，YIN Kui-xi
（School of Physics and Technology of Nanjing Normal University，Nanjing210046，China）

This paper uses Altera company FPGA Cyclone III series EP3C10 devices as a core component of R-S （255223）coding system；Using Quartus II 9.0 as a hardware emulation platform， using hardware description language Verilog_HDL programming，and through the JTAG interface and EP3C10 connection.R-S （Reed-Solomon）code is a kind of special non binary BCH code which's error correction capability is very strong， can deal with random and burst error， widely used in all kinds of communication systems and security systems.R-S （255223）code is capable of detecting and correcting the length of 32 bytes 16 byte length of continuous data error information.

Cyclone III； Quartus II 9.0； Verilog_HDL； R-S（255，223） code

TN911.22

A

1674－6236（2012）04-0189-04

2011-12-21 稿件编号：201112121

苗 鑫（1987—），男，江苏南京人，硕士研究生。研究方向：电路与系统。