并行流水结构的RS255/RS233译码器设计实现
时间：2010-06-15 09:25:48
手机看文章
扫描二维码
随时随地手机看文章
[导读]并行流水结构的RS255/RS233译码器设计实现
RS纠错编码是目前最有效、应用最广泛的差错控制编码之一，是一种纠错能力很强的多进制BCH码，也是一类典型的代数几何码。它是由里德(Reed)和索洛蒙(Solomon)应用MS多项式于1960年首先构造出来的。
RS码被广泛用于差错控制系统中，以提高数据的可靠性，而且可以用来构造其他码类，如级联码。在无线通信、卫星通信、磁或光存储以及网络通信中RS码也有较为广泛的应用。RS码不仅具有良好的随机纠错和突发纠错能力，而且有低复杂度的编译码算法，因此被国际电信联盟(ITU)推荐为光纤子系统的前向纠错(FEC)码。RS(225，223)码被CCSDS选为常规分包遥测信道纠错编码和高级在轨系统前向和反向链路的纠错编码，是实现CCSDS标准低差错率信道纠错编码的关键部件。只要每个码字(255个符号)中出现的错误不超过16个符号，它就能将其纠正。
近年来，关于RS(255，223)码译码器实现的算法得到了广泛的关注，但是这些算法的实现速度都不太快，即便有速度稍高的，其占用硬件资源也较多，而一些占用硬件资源较少的算法速度却很慢。本文采用基于ME算法的8倍并行设计方案，结合流水线技术，克服了上述算法的缺陷，利用尽可能少的硬件资源获得了极高的译码速度。
1 RS(255，223)码及其译码原理
1.1 RS(255，223)码
因其码元取自GF(q)，RS编解码过程中的所有运算都是在GF(q)的有限域上面进行。RS(n，k)码的编码过程是将k个输入信息码字，用生成多项式产生(n，k)个冗余的纠错信息码字，与原码字合成形成n个信息码字进行传输。译码是在接收端，对接收的n个码字信息进行纠错处理，恢复k个信息码字。对于1个长度为am-1符号的RS码，每个码字都可以看成是有限域GF(am)中的1个元素。最小码距为d的码字，其RS码生成多项式具有如下形式：
其中ai是GF(am)中的1个元素。
对于RS(255，223)码而言，q=256，a=2，码字符号在GF(28)中。m=8，是每个RS符号的码元数；n=28-1，是每个RS码字的符号数；k=223，是RS码中信息位的符号数；t=16，是RS码字内符号的纠错能力；d=33，是最小码距。
1.2 RS(255，223)码译码原理
由于RS码为分组码，故其译码算法主要由伴随式计算、关键方程求解和钱搜索和Forney算法3部分构成，译码器结构如图1所示。
首先，根据接收码字乘以校验矩阵得到其伴随多项式，对于RS(225，223)码，其伴随式求解式可以表示为：
求得伴随式以后，则利用伴随多项式求解关键方程：错误位置多项式σ(x)和错误特征多项式ω(x)，如下所示：
求解关键方程现可采用的算法主要有BM(Belekamp-Messey)算法和ME(Modified Euclidean)算法。之后便得到错误位置多项式σ(x)与错误特征多项式ω(x)。
此后，由错误位置多项式与错误特征多项式来求得错误位置与错误值。求解错误位置本设计采用穷举算法——钱搜索算法来完成。同时，使用Forney公式求得错误值。最后，用延时后的接收值减去错误值，得到最后的译码输出。Forney公式可以表示为：
其中，ei代表发生在i位置上的错误值，σodd(x)代表错误位置多项式奇数次项之和。
2并行流水结构方案
本设计采用8倍并行流水方案。将255个码元8倍并行后，只需要32个周期便完成所有32个伴随多项式系数的求解。然后将32个伴随多项式系数顺序输出到下一级，在此基础上采用流水线结构，周期刚好满足且不会浪费资源。本设计中所有乘法器都是采用GF(28)有限域乘法器。
[!--empirenews.page--]
2.1 伴随式计算
8倍并行伴随多项式的求解算法，是在迭代算法的基础上展开实现，其推导过程如下：
式(6)中，R255=0；i=1，2，…，2t-1，2t。其电路结构如图2所示。
2.2 关键方程求解
本设计中关键方程的求解采用ME算法。BM算法具有反馈结构，不适合使用流水结构，而ME算法可采用流水结构。其算法描述如下：
其中，S(x)为输入的伴随多项式。
ME算法为1种迭代算法，目的在于求i阶余式Ri(x)，相应的多项式ri(x)与Li(x)满足：
ri(x)A(x)+Li(x)S(x)=Ri(x)(8)
当i阶余式Ri(x)的阶数小于t时，迭代算法结束。算法结束时的Ri(x)即为错误特征多项式ω(x)，而Li(x) 即为所求的错误位置多项式δ(x)。
ME算法在每一次迭代时进行的运算为：
具体推导请见参考文献[8-9]。
单级迭代电路结构如图3所示。
[!--empirenews.page--]
由ME算法推导可知，使用脉动电路结构实现ME算法时，至多使用2级迭代电路即可降低R(x)多项式阶数1阶。因此，脉动电路结构采用32阶流水结构电路即可保证迭代算法完成收敛得到最后结果。电路结构如图4所示。
2.3 钱搜索和Forney算法
钱搜索模块接收KES模块的错误位置多项式信号δ(x)，利用钱搜索算法逐个检查符号位是否发生错误，输出错误位置和错误位置多项式的奇数项之和，供EE模块计算错误图案和纠错。
设错误位置多项式δ(x)可以表达为奇数项和偶数项之和：
并行钱搜索电路子结构如图5所示。图中m表示并行模块编号数，m=1，2，…，8。所有的乘法器均是常数乘法器，8倍并行结构由图5所示的8个同样的结构组成。
EE(错误值计算)模块根据CS模块输出的δodd(x)以及KES模块输出的ω(x)计算出错误图案。
EE模块需要求解w(ai)，电路结构推导过程和求解δ(ai)的过程一样，电路结构也基本相同，这里不再累述。
3 仿真验证与综合
上述译码器采用自顶向下的设计流程划分模块，用Verilog HDL完成RTL代码的编写，然后在Mentor公司的ModelSim SE 6.1b仿真验证工具下编写测试代码进行仿真验证。仿真结果如图6所示，译码器能正确实现译码功能。
因本译码器可纠正16个错误，超过16个错误便不可纠正，在仿真时译码输入样本采用了2种：一种样本不超过16个错误，另一种样本超过16个错误。仿真结果表明，此译码器能在不超过16个错误的样本下正常译码。
译码器在Quartus II 8.0上进行综合和优化，采用Altera公司Cyclone系列的EP2C15AF256C8芯片为目标器件。译码器的工作时钟频率可达85 MHz，数据吞吐率可达5 440 Mb／s，占用逻辑单元数为13 947个(片内共14 448，占用率为97％)，RAM占用16 698位(片内共239 616位，占用率为7％)。译码器性能对比如表1所列。
与参考文献[4]相比，由于本译码器采用了并行结构在增加了不到3倍的硬件资源的情况下，吞吐率时钟比(吞吐率／时钟)提高了8倍，而且缩短了3／4的泽码延迟。与参考文献[5]相比，本文所采用的译码器增加了不到3倍的硬件资源，提高了8倍的吞吐率时钟比。由于参考文献[5]采用串行译码结构，本文所采用的并行流水译码结构较串行译码结构缩减了19／20的译码延迟。
RS码被广泛用于差错控制系统中，以提高数据的可靠性，而且可以用来构造其他码类，如级联码。在无线通信、卫星通信、磁或光存储以及网络通信中RS码也有较为广泛的应用。RS码不仅具有良好的随机纠错和突发纠错能力，而且有低复杂度的编译码算法，因此被国际电信联盟(ITU)推荐为光纤子系统的前向纠错(FEC)码。RS(225，223)码被CCSDS选为常规分包遥测信道纠错编码和高级在轨系统前向和反向链路的纠错编码，是实现CCSDS标准低差错率信道纠错编码的关键部件。只要每个码字(255个符号)中出现的错误不超过16个符号，它就能将其纠正。
近年来，关于RS(255，223)码译码器实现的算法得到了广泛的关注，但是这些算法的实现速度都不太快，即便有速度稍高的，其占用硬件资源也较多，而一些占用硬件资源较少的算法速度却很慢。本文采用基于ME算法的8倍并行设计方案，结合流水线技术，克服了上述算法的缺陷，利用尽可能少的硬件资源获得了极高的译码速度。
1 RS(255，223)码及其译码原理
1.1 RS(255，223)码
因其码元取自GF(q)，RS编解码过程中的所有运算都是在GF(q)的有限域上面进行。RS(n，k)码的编码过程是将k个输入信息码字，用生成多项式产生(n，k)个冗余的纠错信息码字，与原码字合成形成n个信息码字进行传输。译码是在接收端，对接收的n个码字信息进行纠错处理，恢复k个信息码字。对于1个长度为am-1符号的RS码，每个码字都可以看成是有限域GF(am)中的1个元素。最小码距为d的码字，其RS码生成多项式具有如下形式：
其中ai是GF(am)中的1个元素。
对于RS(255，223)码而言，q=256，a=2，码字符号在GF(28)中。m=8，是每个RS符号的码元数；n=28-1，是每个RS码字的符号数；k=223，是RS码中信息位的符号数；t=16，是RS码字内符号的纠错能力；d=33，是最小码距。
1.2 RS(255，223)码译码原理
由于RS码为分组码，故其译码算法主要由伴随式计算、关键方程求解和钱搜索和Forney算法3部分构成，译码器结构如图1所示。
首先，根据接收码字乘以校验矩阵得到其伴随多项式，对于RS(225，223)码，其伴随式求解式可以表示为：
求得伴随式以后，则利用伴随多项式求解关键方程：错误位置多项式σ(x)和错误特征多项式ω(x)，如下所示：
求解关键方程现可采用的算法主要有BM(Belekamp-Messey)算法和ME(Modified Euclidean)算法。之后便得到错误位置多项式σ(x)与错误特征多项式ω(x)。
此后，由错误位置多项式与错误特征多项式来求得错误位置与错误值。求解错误位置本设计采用穷举算法——钱搜索算法来完成。同时，使用Forney公式求得错误值。最后，用延时后的接收值减去错误值，得到最后的译码输出。Forney公式可以表示为：
其中，ei代表发生在i位置上的错误值，σodd(x)代表错误位置多项式奇数次项之和。
2并行流水结构方案
本设计采用8倍并行流水方案。将255个码元8倍并行后，只需要32个周期便完成所有32个伴随多项式系数的求解。然后将32个伴随多项式系数顺序输出到下一级，在此基础上采用流水线结构，周期刚好满足且不会浪费资源。本设计中所有乘法器都是采用GF(28)有限域乘法器。
[!--empirenews.page--]
2.1 伴随式计算
8倍并行伴随多项式的求解算法，是在迭代算法的基础上展开实现，其推导过程如下：
式(6)中，R255=0；i=1，2，…，2t-1，2t。其电路结构如图2所示。
2.2 关键方程求解
本设计中关键方程的求解采用ME算法。BM算法具有反馈结构，不适合使用流水结构，而ME算法可采用流水结构。其算法描述如下：
其中，S(x)为输入的伴随多项式。
ME算法为1种迭代算法，目的在于求i阶余式Ri(x)，相应的多项式ri(x)与Li(x)满足：
ri(x)A(x)+Li(x)S(x)=Ri(x)(8)
当i阶余式Ri(x)的阶数小于t时，迭代算法结束。算法结束时的Ri(x)即为错误特征多项式ω(x)，而Li(x) 即为所求的错误位置多项式δ(x)。
ME算法在每一次迭代时进行的运算为：
具体推导请见参考文献[8-9]。
单级迭代电路结构如图3所示。
[!--empirenews.page--]
由ME算法推导可知，使用脉动电路结构实现ME算法时，至多使用2级迭代电路即可降低R(x)多项式阶数1阶。因此，脉动电路结构采用32阶流水结构电路即可保证迭代算法完成收敛得到最后结果。电路结构如图4所示。
2.3 钱搜索和Forney算法
钱搜索模块接收KES模块的错误位置多项式信号δ(x)，利用钱搜索算法逐个检查符号位是否发生错误，输出错误位置和错误位置多项式的奇数项之和，供EE模块计算错误图案和纠错。
设错误位置多项式δ(x)可以表达为奇数项和偶数项之和：
并行钱搜索电路子结构如图5所示。图中m表示并行模块编号数，m=1，2，…，8。所有的乘法器均是常数乘法器，8倍并行结构由图5所示的8个同样的结构组成。
EE(错误值计算)模块根据CS模块输出的δodd(x)以及KES模块输出的ω(x)计算出错误图案。
EE模块需要求解w(ai)，电路结构推导过程和求解δ(ai)的过程一样，电路结构也基本相同，这里不再累述。
3 仿真验证与综合
上述译码器采用自顶向下的设计流程划分模块，用Verilog HDL完成RTL代码的编写，然后在Mentor公司的ModelSim SE 6.1b仿真验证工具下编写测试代码进行仿真验证。仿真结果如图6所示，译码器能正确实现译码功能。
因本译码器可纠正16个错误，超过16个错误便不可纠正，在仿真时译码输入样本采用了2种：一种样本不超过16个错误，另一种样本超过16个错误。仿真结果表明，此译码器能在不超过16个错误的样本下正常译码。
译码器在Quartus II 8.0上进行综合和优化，采用Altera公司Cyclone系列的EP2C15AF256C8芯片为目标器件。译码器的工作时钟频率可达85 MHz，数据吞吐率可达5 440 Mb／s，占用逻辑单元数为13 947个(片内共14 448，占用率为97％)，RAM占用16 698位(片内共239 616位，占用率为7％)。译码器性能对比如表1所列。
与参考文献[4]相比，由于本译码器采用了并行结构在增加了不到3倍的硬件资源的情况下，吞吐率时钟比(吞吐率／时钟)提高了8倍，而且缩短了3／4的泽码延迟。与参考文献[5]相比，本文所采用的译码器增加了不到3倍的硬件资源，提高了8倍的吞吐率时钟比。由于参考文献[5]采用串行译码结构，本文所采用的并行流水译码结构较串行译码结构缩减了19／20的译码延迟。
下载文档
