维普资讯 http://www.cqvip.com
第７卷第９期２００７年５月 １６７１－－１８１９（２００７）０９－－１８８６－０４ 科学技术与工程 ＶｏＬ ７ Ｎｏ．９ Ｍａｙ ２００７ Ｓｃｉｅｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ ＠２００７ ＳＯｉ．Ｔｅｃｈ．Ｅｎｇｎｇ． 基于ＭＥ算法的ＲＳ译码器的原理 和ＦＰＧＡ实现． 曾德才魏延存 （西北工业大学软件与微电子学院，西安７１００６５；航空微电子中心 ，西安７１００７２） 摘要ＲＳ（Ｒｅｅｄ—Ｓｏｌｏｍｏｎ）码是具有很强纠错能力的线性分组码，广泛应用于各种通信和存储系统中。文中设计的译码器采 用修正的欧几里德算法（ＭＥＡ），并在实现中采用公共项提取算法有效地优化了乘法器，以迭代、复用等方法降低了Ｒｓ码译 码硬件实现的复杂度。并用Ｖｅｉｒｌｏｇ－ＨＤＬ语言实现了ＲＳ（２５５，２３９）码的译码器各个模块的功能。 关键词Ｒｅｅｄ—Ｓｏｌｏｍｏｎ译码ＭＥ算法ＦＰＧＡ Ｖｅｒｉｌｏｇ—ＨＤＬ 中图法分类号ＴＮ９１９．３； 文献标识码 提高信息传输的可靠性和有效性，始终是通信 系统设计所追求的目标。为改善误码率，人们提出 了多种信道纠错编码方案，如奇偶校验码、ＢＣＨ码、 １ ＲＳ码译码原理及实现 卷积码、Ｔｕｒｂｏ码等。Ｒｅｅｄ．Ｓｏｌｏｍｏｎ（ＲＳ）码是一种 多元ＢＣＨ码，属于线性分组循环码。Ｒｓ码编解码 Ｒｓ译码算法主要分为时域译码和频域译码＿ｌ ， 结构相对简单，具有同时纠突发错误和随机错误的 频域译码由于其结构特点，对于某些码长的ＲＳ码 能力，因而广泛应用于数据通信和数据存储系统的 会获得更快的译码速度，但由于增加了时域与频域 差错控制中，作为提高数据传输速率和存储可靠性 的变换和反变换以及相应的存储延时模块，需要消 的重要手段，它是当今最有效、应用最广的差错控制 耗更多的资源，因此本文仍采用时域译码方案，译码 编码方式之一＿Ｊ 。 的关键步骤为错误位置及错误值多项式的求解，主 Ｒｓ码采用伽罗华域ＧＦ（２ ）中的元素，并在 要算法为修正的欧几里德算法ＭＥＡ（Ｍｏｄｉｆｉｅｄ Ｅｕ－ 伽罗华域进行运算。在ＧＦ（２ ）上，纠错能力为ｔ ｃｌｉｄｅａｎ Ａｌｇｏｒｉｔｈｍ） 和伯利坎普一梅西ＢＭ（Ｂｅｒｌｅ— 的ＲＳ码的参数可表示为：码长ｎ＝２ 一１，信息位 ｋａｍｐ—Ｍａｓｓｅｙ）算法 ］。ＢＭ算法需要大量存储器 长度为ｋ，满足２ ｔ＝ｎ—ｋ，最小距离ｄ ｍｉ ：２ ｔ＋１。 和复杂的逻辑控制，更适于软件实现，而ＭＥ算法数 可知，ＲＳ码在相同的校验位数时，具有最大的距 据存储量少且硬件实现便于控制。因此，本文在硬 —ｌ 离ｎ］。码元多项式ｃ（ ）＝∑Ｃｉ ，生成多项式 件实现中采用ＭＥ算法。 ｉ。一＝０ Ｒｓ纠错译码步骤为 ］：１）计算伴随式（ｓｙｎ－ ２ｔ ｇ（ｘ）＝Ｈ（ｄｒｏｍｅｓ）；２）解关键方程（ｋｅｙ ｅｑｕａｔｉｏｎ）；３）钱搜索 ｆ＝ｌ —Ｏｔ ）。本文用Ｖｅｒｉｌｏｇ ＨＤＬ语言实现 （Ｃｈｉｅｎ ｓｅａｒｃｈ）；４）计算错误值（ｅｒｒｏｒ ｖａｌｕｅｓ）；５）修 了ＲＳ（２５５，２３９）码的译码器，ｍ＝８，ｎ＝２５５，ｋ＝ 正接收码字，如图１所示。 ２００６年ｌ２月４日收到 第一作者简介：曾德才，男，西北工业大学硕士研究生，研究方向： Ｖ１．ＳＩ设计、差错控制编码。 通信作者简介：魏廷存，男，西北工业大学教授，研究方向：数模 混合信号Ｖ１．ＳＩ设计技术以及平板显示驱动芯片技术。 图１ ＲＳ译码器结构 维普资讯 http://www.cqvip.com
９期 曾德才，等：基于ＭＥ算法的Ｒｓ译码器的原理和ＦＰＧＡ实现 １．１计算伴随式 。ｌｉ－ｌｌ［ 一１ａ 一１Ｑ 一１（ ）＋ ｉ一１ｂｉ一１Ｒｉ一１（ ）］ Ｑｉ（ ）＝ ｉ一１Ｑ 一１（ ）＋ ｉ一１Ｒ 一１（ ） Ｌ （ ）＝［ 一１ｂｉ一１Ｌ 一１（ ）＋ ｉ一１ａ 一１ Ｕｉ一１（ ）］一 ”Ｈ‘［ ¨ａ¨Ｕｉ一１（ ）＋ ｂ Ｌ （ ）］ （ ）＝ 一１Ｕ 一１（ ）＋ 一１Ｌ 一１（ ） 其中，ｚＨ＝ｄｅｇＲ （ ）一ｄｅｇＱ （ ），当ｚＨ≥０ 时， 一１＝１；当ＺＨ＜０时， 一１＝０。 ３）如果ｄｅｇＲ （ ）＜ｔ，迭代结束，得到∞（ ） ＝Ｒｉ（ ）， （ ）＝Ｌ （ ）。 图２伴随式计算电路 在硬件实现中，采用迭代结构，使用４组寄存器 分别存储 （ ），Ｑ（ ）， （ ）和 （ ）的系数 设接收码字为ｒ（ ）＝∑ ，伴随式Ｓ（ ） （Ｒｉ（ ），Ｑ （ ）的计算结构和Ｌｉ（ ），Ｕ （ ）相同， ＝Ｕ 一１ 下面只讲前者），设置寄存器存储 （ ）和Ｑ（ ）的 ＝ｓ１＋ｓ２ ＋…＋ｓ２ｌ ，其中ｓｊ＝∑ｒ最高位系数，即公式中的ａ和ｂ，每次迭代完成后根 ｉ＝ｏ ｉ ０ｃ ，化简 得Ｓ ＝（（ｒｎ－１ ＋ｒ ） ＋…＋ｒ１） ＋ｒ０，从而可 据ｄｅｇ Ｒ和ｄｅｇ Ｑ进行更新 。设置标志位ｓｗ，当 用图２所示串行迭代结构实现。 ｄｅｇ Ｑ＞ｄｅｇ Ｒ时，令ｓｗ取１，在代入公式进行计算 １．２ ＭＥ算法求错误位置多项式 （ ）和错误值多 前，将存储 和Ｑ，Ｌ和 寄存器内的值互换，否则 项式ＯＪ（ ） 不互换，这样算法公式简化为： 得到伴随式的值之后，采用ＭＥ算法，基于多项 Ｒ （ ）＝ｂｉ＿ｌＲｉ一１（ ）一 ａｉ＿ｌＱ 一１（ ），Ｑ （ ） ＝式分解原理求两个多项式最大公因式的迭代过程， Ｑ （ ） 对关键方程ｓ（ ） （ ）；∞（ ）（ｍｏｄ ）求解，得 Ｌｉ（ ） ＝６￡一１Ｌ 一１（ ）一 ¨ ａ 一１Ｕ 一１（ ）， （ ） 到错误位置多项式 （ ）和错误值多项式∞（ ），其 ＝Ｕｉ一１（ ） 算法描述如下： 为了提高速度，将寄存器组分成对应的高阶系 １）初始化：设Ｒｓ码的纠错能力为ｔ，伴随式计 数（ …Ｒ ，Ｑ。．．．Ｑ ）和低阶系数（ … ，， 算模块得到的结果为ｓ（ ），则令Ｒ。（ ）＝ ， Ｑ …Ｑ ，）两组并行计算（结构相同），这样一次迭 Ｑ。（ ）＝ｓ（ ），Ｌ。（ ）＝０，Ｕｏ（ ）＝１； 代计算可以在９个时钟周期内完成，大大提高了计 ２）设Ｒｉ（ ）的阶数为ｄｅｇＲ （ ），最高阶的系数 算速度，相应的代价是增加一个运算单元ＣＵ。Ｒ和 为ａｉ，Ｑｉ（ ）的阶数为ｄｅｇ Ｑｉ（ ），最高阶的系数为 Ｑ，Ｌ和 寄存器内的值互换采用可交叉传输的双 ｂｉ，则第 步的迭代计算可以表示为： 入双出开关盒实现，图４显示了ＭＥ算法 （ ）， Ｒｉ（ ）＝［ ｉ一１ｂｉ一１Ｒｉ一１（ ）＋ 一１ａ 一１Ｑｉ一１（ ）］一 Ｑ （ ）的低阶系数实现结构。 ＳＷ＝Ｉ ——————■ …＋ ＳＷ－－Ｏ ＣＵ 图３ ＭＥ算法Ｒ （ ），Ｑｉ（ ）的低阶系数实现结构 维普资讯 http://www.cqvip.com
１８８８ 科学技术与工程 ７卷 １．３钱搜索、计算错误值和纠错输出 得到 （ ）和 （ ）后，方程 （ ）＝０的根对 ２有限域乘法器结构优化 ＲＳ译码器中的乘法运算占用了大量的硬件资 源和功耗，因此乘法器性能的好坏对整个译码器的 性能都起着重要作用。本文采用提取公共项预运算 应错误位置在ＧＦ域的值，由于用硬件直接解方程 比较复杂，因此用钱搜索算法搜索解空问所有可能 发生错误的位置来求根，即检查是否 （ ）＝０（０ ≤ｉ≤２５５）来寻找差错位置ｉ。为方便计算，根据有 限域性质，当 （ ）＝０时差错位置为（ —ｉ），在第 ｉ个周期时电路算得 （ ‘）的值，再通过零检测电 的方法对乘法器结构进行优化，使电路的面积有较 路即可知是否为根。找到错误位置后用福尼（Ｆｏｒ－ ｎｅｙ）算法求出差错值，对错误码宇纠错后输出正确 ／ ｉ、 码字。福尼算法可表示如下：ｅ 一 ＝ ＝ Ｊ ／ ｉ、 ｉ ， 。酣（ ）表示 （ ）的奇次项之和。在实 ０ｄｄ 现钱搜索，计算 （ ）的同时得到 （ ）。 （ ‘） 的计算电路和 （ ）完全相同，为节省面积可复用 钱搜索电路计算 （ ）和 （ ‘），为使错误值输出 和整体速度一致，必须使模块时钟两倍于系统时钟 和两倍的寄存器，在偶数时钟计算 （ ‘），在奇数 时钟计算 （ ‘）。ｅ 求解中的除法运算采用对除数 进行查表求逆，再乘以被除数的方法。在求出错误 位置和相应位置的错误值后，将其与ＦＩＦＯ中存储 的ｒ（ ）进行异或，得到纠错后的码字。如图４、图５ 所示。 Ｌ ｆ 图４钱搜索 图５福尼算法纠错输出 大改善。 设 是ＧＦ（２ ）上的本原元则ＧＦ（２ ）域上的任 意两个元素Ａ和 及其乘积ｃ可以表示为Ａ（ ） ７ ７ ７ ＝∑ Ｚ，‘＝ｏ （ ）＝∑ｂＬ＝ｏ ｉ Ｚ，ｃ（ ）＝∑ｃＬ＝Ｕ ｚ则ＧＦ （２ ）上的乘法定义为Ｃ（ｘ）＝Ａ（ ）×Ｂ（ ）ｍｏｄＰ（ｘ）， 这里Ｐ（ｘ）为本原多项式，Ｐ（ｘ）＝ ＋ ＋ ＋ ＋１， 通过推导可以分两步实现乘法，先将Ａ（ｘ）和Ｂ（ｘ）两 个多项式按常规方法相乘得到一个次数不大于１４的 １４ 多项式 （ ）＝∑ｍ ，再将 （ ）对本原多项式 Ｐ（ ）求模所得到的次数不大于７的多项式就是乘积 ｃ，经计算得 ｍｏ＋ｍ８＋ｍ１２＋ｍ１３＋ｍ１４ ｍ１＋ｍ９＋ｍ１３＋，ｎ１４ ｍ２＋ｍ８＋，ｎ１Ｏ＋ｍ１２＋ｍ１３ ｍ３＋ｍ８＋ｍ９＋ｎｉｌ＋ｍ１２ Ｃ＝ ｍ４＋ｍ８＋ｍ９＋ｍｌｏ＋，ｎ１４ ｍ５＋ｍ９＋ｍｌｏ＋ｎｉｌ ｍ６＋ｍｌｏ＋ｎｉｌ＋ｍ１２ ｍ７＋ｎｉｌ＋，ｎ１２＋ｍ１３ ｍｏ＋ｍ１４＋（（ｍ８＋ｍ１２）＋ｍ１３） ｍ１＋（ｍ９＋ｍ１４）＋ｍ１３ ｍ２＋ｍ１ｏ＋（（ｍ８＋ｍ１２）＋ｍ１３） ｍ３＋（ｍ８＋ｍ１２）＋（ｍ９＋ｍｌ１） ｍ４＋ｍ８＋ｍ１ｏ＋（ｍ９＋ｍ１４） ｍ５＋ｍ１ｏ＋（ｍ９＋ｍｌ１） ｍ６＋ｍ１０＋（ｍｌ１＋ｍ１２） ｍ７＋（ｍｌ１＋ｍ１２）＋ｍ１３ 可以看出上式左边逻辑运算还可以通过公共项 提取进一步优化例如ｍ８＋ｍ１２，ｍ１２＋ｍ１３，ｍ１１＋ｍ１２ 都先后出现了３次，因而它们均可以作为公共项提 维普资讯 http://www.cqvip.com
９期 曾德才，等：基于ＭＥ算法的Ｒｓ译码器的原理和ＦＰＧＡ实现 １８８９ 取并预先计算，这样可以进一步减少异或门的数量， 合设计要求。 优化电路结构 ｊ。优化后如上式右边，式中的括号 项为提取的公共项，共有５个，优化后需要的异或门 数由２８个减至２２个，也使得乘法器的异或门数从 ７７个减少为最终的７１个。变量乘法器和常量乘法 器都可用提取公共项的方法进行优化，优化后面积 减少了１５％左右。 ４结论 本文对ＲＳ（２５５，２３９）译码器的关键模块进行了 结构优化，设计中采用公共项提取算法有效地减少 了乘法器中异或门的数量，在计算伴随式、ＭＥ算法 解关键方程、钱搜索的电路中都应用了迭代算法，并 ３硬件实现和测试 该设计在ＩＳＥ６．３ｉ环境下完成，使用综合工具 Ｓｙｎｐｌｉｆｙ ｐｒｏ ７．６，仿真工具Ｍｏｄｅｌｓｉｍ ＳＥ ６．０，设计语 言使用Ｖｅｒｉｌｏｇ ＨＤＬ。使用Ｘｉｌｉｎｘ的ＦＰＧＡ芯片Ｖｉｒ— ｔｅｘ Ｈ ｘｃ２ｖ４０—４ｃｓ１４４进行测试。译码器使用１６７１ 个Ｓｌｉｃｅ Ｆｌｉ ＰＦｌｏｐｓ，３５０８个４输入ＬＵＴｓ，整个的等 效门数是１０２８６５ ｆ－ｊ，占芯片总资源的３５％，最高工 作时钟超过１００ＭＨｚ；并对伴随式、ＭＥ算法、钱搜 索、求错误值４个模块分别综合，等效门数分别为 １０３６４、３５９４０、１３６５５、２２６９１，能达到的时钟频率分别 为１４１．６ ＭＨｚ、１０２．５ ＭＨｚ、１１６．１ ＭＨｚ、１２２．０ ＭＨｚ。 对钱搜索模块进行复用，减少了芯片面积，降低了复 杂度，提高了芯片速度。 参考文献 １王新梅，肖国镇．纠错码一原理与方法．西安：西安电子科技大 学出版社，２００３ ２ Ｈａｎｈｏ Ｌｅｅ．Ｈｉｇｈ Ｓｐｅｅｄ ＶＬＳＩ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｐａｒａｌｌｅｌ Ｒｅｅｄ Ｓｏｌｏｍｏｎ Ｄｅｃｏｄｅｒ．ＩＥＥＥ Ｔｒａｎｓ ｏｎ ＶＬＳＩ Ｓｙｓｔｅｍ，２００３，ｌｌ（２）：２８８—２９４ ３ Ｓｈａｏ Ｈｏｗａｒｄ Ｍ．Ｒｅｅｄ Ｉｒｖｉｎｇ Ｓ．Ｏｎ ｔｈｅ ＶＬＳＩ Ｄｅｓｉｇｎ ｏｆ ａ Ｐｉｐｅｌｉｎｅ Ｒｅｅｄ Ｓｏｌｏｍｏｎ ＤｅｃｏｄｅＴ Ｕｓｉｎｇ Ｓｙｓｔｏｌｉｃ Ａｒｒａｙｓ．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｏｍｐｕｔ— ｅｒｓ，１９９８，３７（１Ｏ）：１２７３—１２８０ ４ Ｐａａｒ Ｃ．Ｏｐｔｉｍｉｚｅｄ Ａｒｉｈｍｅｔｔｉｃ ｆｏｒ Ｒｅｅｄ—Ｓｏｌｏｍｏｎ Ｅｎｃｏｄｅｒｓ．Ｐｒｏｃ ＩＥＥＥ Ｉｎｔ Ｓｙｍ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ．１９９７，２５０ ５ Ｋｗｏｎ Ｓ．ＳｈｉｎＨ．Ａｎ ａｒｅａ—ｅｆｆｉｃｉｅｎｔＶＬＳＩ ａｒｃｈｉｔｃｔｅｕｒｅ ｏｆ ａＲｅｅｄ—Ｓｏｌｏ— ｍｏｎ ｄｅｃｏｄｅｒ／ｅｎｃｏｄｅｒ ｆｏｒ ｄｉｇｉｔａｌ ＶＣＲｓ．ＩＥＥＥ Ｔｒａｎｓ Ｃｏｎｓｕｍｅｒ Ｅｌｅｃ— 由此可见，ＭＥ算法模块的速度是译码器译码速度 的瓶颈所在，我们可以对该模块继续优化，比如分成 更多组并行计算。将编码得到的码字人为加入８位 错误，启动仿真，解码输出８位错误均得到纠正，符 Ｉｒｏｎｉｅｓ，１９９７，４３（４）：１０１９—１０２７ Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ＦＰＧＡ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＲＳ Ｄｅｃｏｄｅｒ Ｂａｓｅｄ ｏｎ ＭＥ Ａｌｇｏｒｉｔｈｍ ＺＥＮＧ Ｄｅ—ｃａｉ，ＷＥＩ Ｔｉｎｇ—ｃｕｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｓｏｆｔｗａｒｅ ａｎｄ Ｍｉｃｒｏｅｌｃｔｅｒｏｎｉｃｓ，Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖ，ＸｉＩｍ ７１００６５，Ｐ．Ｒ．Ｃｈｉｎａ； Ａｖｉａｔｉｏｎ Ｍｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ Ｃｅｎｔｅｒ，Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖ ，ＸｉＩｍ ７１００７２，Ｐ．Ｒ．Ｃｈｉｎａ） ［Ａｓｔｒａｃｔ］ ＲＳ（Ｒｅｅｄ—Ｓｏｌｏｍｏｎ）ｃｏｄｅ ｉｓ ａ ｌｉｎｅａｒ ｂｌｏｃｋ ｃｏｄｅ ｈａｖｉｎｇ ｖｅｒｙ ｓｔｒｏｎｇ ｃａｐａｂｉｈｔｙ ｏｆ ｃｏｒｒｅｃｔｉｎｇ ｒａｎｄｏｍ ａｎｄ ｂｕｒｓｔ ｅｒｒｏｒｓ，ｗｈｉｃｈ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｖａｒｉｏｕｓ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｎｄ ａｍｅｍｏｒｙ ｓｙｓｔｅｍｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ｄｅｃｏｄｅｒ ｉｓ ｄｅｓｉｇｎｅｄ ｕｓｉｎｇ ｍｏｄｉｉｆｅｄ Ｅｕｃｌｉｄｅａｎ ａｌｇｏｒｉｈｍ（ＭＥＡ），ｔｔｈｅ ｐｕｂｌｉｃ ｅｘｔｒａｃｔｉｏｎ ａｌｇｏｒｉｈｍ ｉｔｓ ｕｓｅｄ ｔｏ ｏｐｔｉｍｉｚｅ ｈｅ ｔｍｕｌｔｉ— ｐｌｉｅｒ，ａｎｄ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｔｈｅ ｐｏｗｅｒ ｃｏｎｓｕｍｐｔｉｏｎ ｏｆ ＲＳ ｄｅｃｏｄｅｒ ｒｅ ａｒｅｄｕｃｅｄ ｂｙ ｕｓｉｎｇ ｈｅ ｉｔｔｅｒａｔｉｏｎ ｎｄ ｍｕｌａｔｉｐｌｅ ｍｅｔｈｏｄｓ．Ｔｈｅ ａｌｌ ｂｌｏｃｋｓ ｏｆ ＲＳ（２５５，２３９）ｄｅｃｏｄｅｒ ａｒｅ ｒｅａｌｉｚｅｄ ｂｙ Ｖｅｒｉｌｏｇ—ＨＤＬ． ［Ｋｅｙ ｗｏｒｄｓ］ Ｒｅｅｄ—Ｓｏｌｏｍｏｎ ｄｅｃｏｄｅｒ ＭＥ ｌａｇｏｉｒｈｔｍ ＦＰＧＡ Ｖｅｒｉｌｏｇ・ＨＤＬ
