一种自适应数据逐层分解的Reed-Solomon码迭代纠错方法及应用

王 娟 王 萍

（天津大学电气与自动化工程学院 天津 300072）

一种自适应数据逐层分解的Reed-Solomon码迭代纠错方法及应用

王 娟 王 萍*

（天津大学电气与自动化工程学院 天津 300072）

该文针对Reed-Solomon码纠错算法计算复杂度较高、运算时间较长等问题，提出一种自适应数据逐层分解的Reed-Solomon码的迭代译码纠错方法。首先，接收码通过逐层分解将随机错误或突发错误分散于不同的子序列中，缩小突发或随机错误的查找范围；其次，制定约束规则确定错误数目，同时根据不同的伴随矩阵维数自适应选择迭代求解关键方程的方法，定位子序列中误码的位置；最后，计算正确码字，结束纠错。实验测试表明，该算法在保证不漏检误码的前提下，能够有效简化计算多项式的维数，减少计算量和复杂度，纠错时效优于DFT（Discrete Fourier Transform）算法和BM（Berlekamp-Massey）算法。特别是对2维码数据的纠错测试中，与传统算法相比，该算法纠错时效可提升一个数量级。

Reed-Solomon（RS）码；逐层分解；降维；迭代求解

1 引言

信道码字在快速传输过程中难免会受到噪声侵袭，使其携带的信息出现偏差。为此，人们在输入码中加入冗余校验码字辅以纠错，以提高传输的正确率。BCH（Bose ray-Chaudhuri Hocquenghem）码［1］是带有此类纠错码的典型代表，而Reed-Solom on（RS）码［2］则是BCH码的一个重要子类，RS码首先由Reed和Solom on应用Mattson-Solomon多项式于1960年构造出来，是一类具有很强纠错能力的线性分组码，具有纠正随机错误及突发错误的能力，被广泛应用于数字信号传输、深空通信、高密度磁盘存储、量子计算等方面［3］。

自RS码被创建以来，众多学者对其纠错算法中关键步骤进行深入研究。目前，纠错算法分为硬判决和软判决两种，本文重点讨论硬判决译码纠错算法。关于硬判决纠错算法，文献［4］使用PGZ（Peterson Gorenstein Zierler）算法纠错，该算法实现简单，易于理解，对于较短码的纠错非常有效。但它使用穷举法求解误码位置多项式，耗时较长，不适合维数较高的误码位置多项式的求解。文献［5，6］将典型的欧几里德算法加入到求解过程中，该方法采用多项式分解的原理求解多项式的最大公因式，因此需要多次进行多项式长除运算，且在迭代过程中需要计算多项式的次数，计算方法易陷入不收敛；文献［7-10］将具有自回归滤波性质的BM（Berlekam p-Massey）迭代算法用于纠错，目前此方法应用较广泛。但上述方法所需时间和纠错周期依然较长，计算步骤仍较复杂。为提高纠错效率，文献［11，12］使用离散傅里叶变换（Discrete Fourier Transform， DFT）算法进行纠错，即将输入码变换至频域，使用DFT算法的特性求解复杂的方程式，在GF（2m）域上通过高效的DFT算法来计算错误信息多项式，提升纠错效率，但效果有限。

针对上述文献算法中的不足，本文提出了一种基于数据逐层分解的RS码的自适应迭代纠错算法，重新定义伴随式和误码数的判断，缩小误码的查找范围，快速判读误码数目，降低关键方程的求解维数，自适应选择穷举法或无求逆过程的iBM（inversionless Berlekamp-Massey）算法［9］求解关键方程。在不降低最大纠错能力的前提下，本文算法计算复杂度显著降低，纠错效率明显提升。

2 RS码及其纠错过程

RS码纠错算法大致分为4个步骤［14］：

（2）由伴随多项式得到伴随矩阵：用上述2t- 1个伴随式计算结果组成伴随矩阵M。可以证明［14］，接收码r中所含误码个数v等于矩阵M的秩，即v=rank（M），当且仅当接收码中实际误码个数大于等于t时，矩阵M满秩。

将本原元的各次幂的倒数α-1，α-2，…，α-t依次代入σ（p），若σ（a-j）=-1（j=1，2，…， t ），则表明接收码的第j个码字出现错误。

（4）修改误码位置的码字，完成纠错：根据Forney算法［14］计算出错误码字的差错值。将错误码字减去相应的差错值即可得到正确的码字。

3 基于逐层分解的纠错算法及分析

第2节中RS码的纠错过程表明，为确定接收码r中是否存在误码，需要在计算2t- 1个伴随元素的基础上，对t× t阶矩阵及其降阶矩阵进行求秩运算，以便于找出错误码字并进行校正。求秩运算的复杂度为O（ t！），运算耗时较长。因此，本文通过对接收码的逐层分解，减少伴随矩阵的计算量，进而降低求秩运算的复杂度。

3.1 纠错算法实现过程

3.1.1 逐层分解算法的实现 在不降低最大纠错能力且提高效率的前提下，本文遵循将接收码中的错码尽量分散至子序列中和尽量降低定位错码计算复杂度的原则逐层分解接收码。首先，依照图1，对长度为N的接收码字序列r进行逐层分解（分解过程见表1）。

图1 逐层分解示意图

表1 逐层分解算法步骤

表2 误码数目判断步骤

表3 无求逆iBM迭代算法步骤

综上所述，基于数据逐层分解的RS码纠错算法流程图如图2所示。

3.2 算法复杂度分析

通过数据逐层分解后的RS码的纠错算法计算量明显下降，主要体现在：

实际应用中，RS码主要用于突发和随机错误的纠错，每个子序列均含有误码的概率较小。逐层分解后，部分子序列误码数目可能为0，因此，在实际中算法复杂度得到进一步的降低。同样，分解后误码均出现在同一个子序列中也较为少见，若发生此种情况，可根据误码的概率分布调整分解方案，以达到降低复杂度的目的［1］。

（3）关键方程的简化求解。采用无求逆iBM算法在时间上可将RS码计算的关键路径由2（Tmult+Tadd）缩短到（Tmult+ Tadd）。其中，Tmult和 Tadd分别是有限域乘法器和加法器的时延，从而缩减RS码纠错运算时间。

4 算法测试及应用

4.1 基于AWGN信道数据的算法对比测试

如表4所示，在误码率为10-3条件下，基于DFT变换和BM算法的RS纠错算法的矩阵维数较高，导致计算次数较高，运算时间较长。而本文算法在降低求解矩阵维数的基础上进行计算，计算复杂度与其他两种算法相比，运算时间平均可缩短1～1.5倍左右。

图2 基于数据逐层分解的纠错算法流程图

表4 运算时间对比统计结果（s）μ

4.1.2 误码纠正率比较 误码纠正率是指已纠正的误码数占所有误码数的比例。本文对不同码长的码字及不同的误码率中使用RS码对数据进行纠错，并与DFT算法进行误码纠正率对比实验，结果如图3所示。

图3的实验结果表明，在不同误码率的信道中，本文算法误码纠正率能够达到95%以上，高于DFT算法。究其原因，DFT算法在转向频域时，输入码有所亏损，致使能够纠正的误码数减少。综上，面对AWGN信道数据，本文算法纠错性能优于DFT算法。

4.2 2 维码纠错应用举例

2维条码长期暴露于印刷品表面或复杂的工况当中，很容易受到污损破坏。为了达到预期的识别效果，除了要设计合理条码结构外，还需要采用纠错能力强的纠错算法进行纠错。因此，2维条码采用RS码进行编码、译码和纠错［18］。

图3 纠错率对比

4.2.1 被污染2维条码的纠错 图4（a）为被墨迹污染的2维条码图像，编码规则为ECC200，其条码区域大小为20×20，接收码中含有12 bit错误，隶属于8个码字（图4（a）中灰色框体划分出具体码字分割情况，并标示错误码字所在），使用RS（127，107，10）编码［19］，其可纠错最大数为10个码字。

对图4中被污染条码分别使用传统BM算法、DFT算法以及本文算法进行纠错，耗时为10.257 ms，7.149 ms， 1.189 m s，由于未超过最大纠错数，3种算法在纠错率上并无差别。为验证算法的有效性，本文使用尺寸大小不一、编码参数不同、污染程度不同的50幅2维条码图像作为实验样本，分别使用本文算法、DFT算法以及BM迭代算法对进行纠错，统计实验结果如表5所示。

图4 被污染的2维条码纠错效果

被污染的2维条码中错误码字成片出现，经过逐层分解后，误码被分散到不同的子序列中，因而可快速定位到误码位置。此处纠错率是指已纠正的误码数占所有误码数的比例的平均值，此数值小于100%是由于当误码数超出最大纠错数时，算法无能力检测出所有误码。表5中统计数据表明本文算法在不降低最大纠错能力的前提下，运算时间分别比BM算法和DFT算法平均提高约3.64倍和2.55倍，运算复杂度大大降低。

表5 各算法在污染2维码图像中的性能比较

4.2.2 非均匀光照下2维条码的纠错 图5（a）为非均匀光照下2维条码典型代表，条码信息区域大小为16×16。由于光照不均，条码区域出现模糊和缺损，共出现24 bit错误，隶属于7个码字。图5（a）采用RS（63，49，7）码编码，图中使用灰色框体划分出具体码字分割情况，并依次标示错误码字所在。

图5 非均匀光照引起的缺失条码纠错效果

对图5中缺损条码分别使用本文算法、DFT算法以及传统BM算法进行纠错，耗时分别为0.897 ms， 2.902 ms， 4.757 ms，纠错率均为100%。同理对50幅尺寸、参数各异的非均匀光照条件下的2维条码分别使用3种算法进行纠错。统计实验结果如表6所示。

表6 各算法在非均匀光照2维码图像中的性能比较

表6中统计数据表明，针对非均匀光照条件下2维码中的错误码字，本文算法在运算复杂度和运算时间均优于其他两种算法。其中，运算时间较BM算法提高3.29倍，而与DFT算法相比也提高了2.04倍。

综上所述，本文算法应用在2维条码纠错时，在纠错时间及计算复杂度等方面优于传统算法。采用逐层分解变换对条码数据进行分解后，大幅度降低了伴随式和关键方程的计算维数，从而减少了运算时间和复杂度，与BM迭代算法和DFT算法相比优势明显。

5 结束语

RS码纠错算法是经典的数据纠错算法之一。针对其计算复杂度高、运算时间长等弱点，本文提出从接收数据源头对数字序列进行逐层分解，设置分解结束条件，减少伴随式的计算长度和求解伴随矩阵秩的计算量。根据伴随矩阵维数，自适应选择穷举法或iBM迭代算法求解关键方程，进一步地降低计算复杂度。同时，误码数判断机制的提出，也为减少运算时间贡献力量。与其他算法相比，本文算法在应用实例中运算时间短，实时性好，可有效复原含加性白噪声的信道数据和2维条码中因局部受损造成的错误。

［1］ 阔永红， 曾伟涛， 陈健. 基于概率逼近的本原BCH码编码参数的盲识别方法［J］. 电子与信息学报， 2014， 36（2）: 332-339. Kuo Yong-hong， Zeng Wei-tao， and Chen Jian. Blind identification of prim itive BCH codes param eters based on probab ility approxim ation［J］. Journal of Electron ics & Information Technology， 2014， 36（2）: 332-339.

［2］ Couvreur A， Gaborit P， Gauthier-Umaña V， et al.. Distinguisher-based attacks on public-key cryptosystem s using Reed-Solomon codes［J］. Designs， Codes and Cryptography， 2014， 73（2）: 641-666.

［3］ Lin Shu and Costello D J. Error Control Coding ［M］. 2nd Edition， London， UK: Prentice Hall， 2004: 153-175.

［4］ Tilavat V and Shukla Y. Sim plification of p rocedure for decoding Reed-Solomon codes using various algorithms: an introductory survey［J］. International Journal of Engineering Development and Research， 2014， 2（1）: 279-283.

［5］ W achter-Zeh A， Zeh A， and Bossert M. Decod ing interleaved Reed-Solomon codes beyond their joint error-correcting capability［J］. Designs， Codes and Cryptography， 2014， 71（2）: 261-281.

［6］ Boito P. The Euclidean algorithm［J］. Structured Matrix Based M ethods for Approximate Po lynom ial， 2009， 15（1）: 45-58.

［7］ Park J I and Lee H. A rea-efficient truncated Berlekam p-Massey architecture for Reed-Solomon decoder［J］. Electronics Letters， 2011， 47（4）: 241-243.

［8］ Chen Y H， Truong T K， Chang Y， et al.. A lgebraic decoding of quadratic residue codes using Berlekam p-M assey algorithm［J］. Journal of Inform ation Science and Engineering，2007， 23（1）: 127-145.

［9］ Sarwate D V and Shanbhag N R. High-speed arch itectures for Reed-Solomon decoders［J］. IEEE Transactions on VLSI System s， 2001， 9（5）: 641-655.

［10］ Lin T C， Truong T K， Chang H C， et al.. A future sim p lification of procedure for decod ing nonsystem atic Reed-Solom on codes using the Berlekam p-M assey algorithm［J］. IEEE Transactions on Comm unications， 2011， 59（6）:1555-1562.

［11］ Truong T K， Chen P D， W ang L J， et al.. Fast， prime factor，discrete Fourier transform algorithm s over GF（2m） for 8≤m≤10［J］. Inform ation Sciences， 2006， 176（1）: 1-26.

［12］ Schm idt G， Sidorenko V R， and Bossert M. Collaborative decoding of interleaved Reed-Solomon codes and concatenated code designs［J］. IEEE Transactions on Inform ation Theory， 2009， 55（7）: 2991-3012.

［13］ 孙小钧， 刘晓健， 赵春明. 迭代译码的级联Reed-Solom on乘积码与卷积码［J］. 电子与信息学报， 2009， 31（12）: 2917-2921. Sun Xiao-jun， Liu Xiao-jian， and Zhao Chun-m ing. Concatenated Reed-Solomon p roduct code/convolutional code w ith iterative decoding［J］. Journal of Electronics & Inform ation Technology， 2009， 31（12）: 2917-2921.

［14］ 邱昕， 张浩， 亓中瑞， 等. 一种高速自适应Reed-Solom on译码结构及其VLSI优化实现［J］. 电子与信息学报， 2009， 31（2）: 484-488. Qiu Xin， Zhang Hao， Qi Zhong-rui， et al.. An architecture and VLSI imp lementation for adaptive Reed-Solomon decoder［J］. Journal of Electronics & Inform ation Technology，2009， 31（2）: 484-488.

［15］ W ang K， Tang Z， Song Z， et al.. Verilog HDL op tim isation design and simulation for modified inversionless Berlerkam p-Massey algorithm and the mu ltip lier over canonical field［J］. In ternational Journal of M obile Network Design and Innovation， 2013， 5（1）: 51-62.

［16］ Van V T， M ita S， Li J， et al.. Bit-level soft-decision decod ing of triple-parity Reed-Solomon codes through automorphism groups［J］. IEEE Communications Letters， 2013， 17（3）: 553-556.

［17］ Rahm an M M and Enam F. Secu re m essage transm ission over w ireless communication［J］. Research Journal of Physical and Applied Sciences， 2013， 2（3）: 30-35.

［18］ Dychka I A， Novosad M V， and G rybok T Y. Data conversion in creation and processing of mu lticolored graphic codes［J］. Radio Electronics and Communications System s， 2013， 56（7）: 335-344.

［19］ Automatic identification and data cap ture techn iques. ISO/IEC 16022-Data m atrix bar code sym bology specification［S］. Sw itzerland， IHS， 2006.

王 娟： 女，1983年生，博士生，研究方向为DPM工业2维码识别及其纠错.

王 萍： 女，1955年生，教授，博士生导师，主要研究方向为计算机视觉、运动目标的识别、跟踪与理解；模式识别、图像识别方法、分类特征的分析与提取.

An Adaptive Reed-Solomon Iterative Correction M ethod Based on Data Layer-w ise Decom position and Its App lication

Wang Juan Wang Ping
（College of Electrical and Automation Engineering， Tianjin University， Tianjin 300072， China）

In order to reduce the com putational com plexity， an im proved decoding algorithm based on a layer-w ise decom position transform is p roposed for Reed-Solomon （RS） codes in this paper. Firstly， the received codewords are split into a number of sub-sequence codewords by layer-wise decom position. The random or burst error are dispersed in different sub-sequences， narrowing search areas of the burst or random errors. Secondly， the appropriate rules are developed to determ ine the number of errors. To help locate the error pattern of the sub-sequence， an adaptive iterative method to solve the key equation is used according to the adjoin matrix dimension. Finally， the correct codewords are obtained by subtracting error estimation from the received sequence. The tests show that in prem ise of detecting all errors the order of the polynom ial is reduced and the com putational comp lexity is lowered. The rate of error correction of the proposed algorithm is higher than DFT （Discrete Fourier Transform） algorithm and BM （Berlekam p-Massey） algorithm. Especially in the tests of the two-dimensional code，error correction efficiency is im proved one order of magnitude.

Reed-Solomon （RS） code； Layer-wise decomposition； Dimensionality reduction； Iterative solution

TN911.22

： A

：1009-5896（2015）05-1173-07

10.11999/JEIT140907

2014-07-11收到，2014-11-18改回

河北省科技支撑项目资助课题

*通信作者：王萍 wangps@tju.edu.cn