在FPGA上实现对RS译码器的优化设计_李锦明.pdf

敬请登录网站在线投稿（）年第期 在 上实现对 译码器的优化设计李锦明，张萍萍（中北大学 半导体与物理学院，太原 ）摘要：针对里德所罗门码（，）译码在硬件实现时存在数据量大、消耗资源多等问题，基于 标准中的 （，）码，根据欧几里得核心译码算法，在 上实现对 译码器的优化设计。本文提出采用乘法器因子矩阵方法将有限域中的乘法计算转换为加法运算，用异或操作在硬件中实现，简化硬件运算数据量；在欧几里得算法核心模块实现中，采用多项式除法电路和多项式乘法电路进行硬件电路设计，降低运算复杂度，可以有效节约硬件资源。通过 测试验证，优化设计的译码器可以有效译码并具有较好的译码性能，完成最多 个码元数据的纠错。关键词：里德所罗门码；译码器；欧几里得算法；中图分类号：文献标识码：，（，）：（），（，），：；引言 码作为一种纠错码，在线性分组码中占有重要地位，因为其在中短码长中纠正随机错误和突发错误的能力十分突出，纠错性能几乎接近理论值。在实际应用中，码的编码算法相对更易实现，这就使得译码成为 码应用中的重点和难点。目前 译码核心就是关键方程的算法，常用的有 （）算法、伯利坎普（）算法和欧几里得（）算法。算法需要求得矩阵的逆，而 算法以代数迭代的算法方式进行计算，由于这两种算法不利于硬件实现，因此本文采用欧几里得算法作为核心算法，使得本文设计的 译码器在实现译码功能的基础上降低硬件实现复杂度。译码原理对于定义在（）的（，）码，（）表示编码后的校验多项式，（）为生成多项式，在传输过程中编码后的信息叠加噪声干扰等影响，输入中引入叠加错误的多项式为（），因此待译码数据 的多项式可表示为：（）（）（）（）（）（）若（）（），则说明（），（）（），即在传输过程中没有受到干扰，码字一致，不存在错误；若（）（），则说明存在错误（），需要译码纠错。在（，）中，满足的矩阵定义为监督矩阵，则其监督矩阵的表达式如下：（）（）（）（）根据监督矩阵和待译码数据 的关系可求得伴随子矩阵，表达式如下：年第期 （）令、，称为错误位置，为错误估值，由错误位置，构成一个错误子多项式（）如下：（）（）（）（）译码算法的核心就是求关键方程，即错误子多项式（），本文采用在迭代过程完成并同时得到错误子多项式（）和错误值多项式（）的欧几里得算法。欧几里得算法采用多项式分解方法，根据已知的伴随子，求解 和（）的最大公因式。获取到（）和（）之后，采用钱搜索法确定，从而获得错误位置，将域中的所有元素，代入（），判断（）是否为，得到（）的根，求取根的倒数之后，其指数即错误位置，错误估值一般由（）和（）经过 公式（如下式）计算得到：（），（）译码电路设计与实现根据译码原理对 （，）码进行电路设计，总体框图如图所示，主要由数据分组模块、伴随子求取模块、欧几里得算法核心模块、钱搜索模块和 模块部分组成。图 译码总体框图首先输入编码后叠加噪声的待译码数据，数据分组模块进行数据分组处理得到（），由伴随子求取模块计算得到本 组 数 据 的 伴 随 子 ，由 欧 几 里 得 算法核心模块计算关键方程，得到错误子多项式（）和错误多项式（）。钱搜索模块负责计算错误位置，模块负责计算错误估值，最后将计算结果导入纠错公式对分组后数据（）进行错误纠正，从而得到正确的码字（），结束译码。数据分组模块译码系统中加入数据分组模块是因为信息数据在传输过程中受到噪声因素影响，可能会接收到不完整的数据，因此在译码处理之前先对数据进行分组处理，防止存在数据丢失等情况导致译码错误。伴随子求取模块伴随子求取过程数据分组完成后，待译码数据将进入伴随子求取模块进行数据计算。根据 译码原理，可用接收码字，表示，由其归纳可得伴随子的求取核心公式为：（）（）（），因此，可以得到：（）（），根据伴随子的求取过程，设计求，的运算电路如图所示。图伴随子求取电路硬件实现优化针对有限域乘法器在硬件实现时存在数据量大、运算消耗硬件资源多等问题，在硬件电路设计时，根据有限域乘法原理，采用乘法器因子矩阵的计算方法实现乘法器计算，原理如下：设、均为有限域 （）中的元素，令 ，表 示 元 素 的 乘 法，矩 阵 可 表 示 为 ，。其中，为：式中，为乘法器因子矩阵，当元素一定时，乘法器因子矩阵系数（）保持不变，乘法器因子矩阵也是定值。将乘法器因子矩阵应用到乘法器计算时，可以通过加法运算代替乘法运算，同时在硬件实现上，加法运算可以敬请登录网站在线投稿（）年第期 通过异或操作完成，这种优化方式降低了算法的运算复杂度，减少了硬件实现时消耗的资源。欧几里得算法核心模块欧几里得算法实现欧几里得算法的核心主要是计算 和（）最大公因式，采用多项式分解原理实现。令（），（）（），计算（）的参考多项式（），（），运算步骤如下：求（）（）的商（）和余（）。求（）（）（）（）。判断（）值是否为，若为，则迭代结束；否则取（）（），（）（），重复前两个步骤继续迭代，直到（）为止。硬件实现优化根据传统欧几里得算法的计算流程进行 实现时消耗的资源过多，因此在本阶段进行硬件实现优化是很有必要的。欧几里得算法的核心是求取最大公因式，通过迭代方式一直到（）结束，观察整个流程，迭代的关键就是求取多项式（）（）的商（）和余（）以及（）（）项，因此在硬件实现上采用多项式除法设计电路和多项式乘法设计电路进行优化。对于（，）码，（）、（）的最高次数和 小于等于，（）的最高次数为，所以（）可以表示为：（）其中，（）（）的计算过程由多项式除法设计电路实现，多项式乘法设计电路根据（）（）的计算过程设计，其设计的硬件实现优化电路如图和图所示。图多项式除法电路图多项式乘法电路 钱搜索模块钱搜索法将错误子多项式（）中的变量代入有限域中的元素，判断（）结果是否为，之后计算满足条件的元素的逆，就会得到错误子，和错误位置，。由译码原理可知，其错误子多项式（）可表示为：（），根据上述原理设计的硬件电路如图所示，在迭代过程中，该电路可以完成有限域中所有元素的计算。图钱搜索电路 模块根据 公式原理设计的硬件实现电路如图所示。图 电路在已知错误位置和错误估值的基础上，可以通过纠错公式（）（）（）对待译码数据进行纠错，从而得到正确的译码结果。测试与验证基于 开发板对（，）译码器进行硬件测试，设计的系统工作流程如图所示。当系统的时钟有效时，在此基础上收到系统启动信号 ，待译码数据经数据分组处理后发出读取待译码数据信号 ，译码系统接收待译码数据进行译码，并发出 信号，表示译码正在进行，译码后的数据发送至输出存储单元进行暂存，并发出译码完成信号 ，提示可进行下一次译码。年第期 图系统工作流程通常在验证译码系统时，庞大的数据量会使译码结果与原码的比对变得困难，为了更加方便地验证仿真结果，选择待译码数据的首尾作为错误数据干扰位置，共设置 个错误数据，将存在错误数据干扰的待译码数据输入至译码系统。仿真结果如图、图所示。可知，错误位置干扰为待译码数据的第至位和第 至 位数据，经译码系统纠错后输出的数据为、，与未 加 错 误 数 据 干 扰 前 的 数 据 保 持 一 致，译 码成功。结语本文基于 译码理论设计了硬件电路，设计中采用图待译码数据图译码后数据乘法器因子矩阵构造有限域乘法器，采用多项式乘、除法电路实现欧几里得算法。通过编写 代码完成了 译码系统的设计并在 上得以实现，然后进行了软件仿真，验证了该译码系统满足设计要求，可以有效实现 译码功能。参考文献李锦明，贾博雄 编码的硬件实现及 研究 单片机与嵌入式系统应用，（）：王兰珠，李锦明 基于 的 译码器的设计与实现电子测量技术，（）：薛丽 一种码率兼容 码译码器的研究及实现 电子质量，（）：王国栋，李锦明，郑志旺，等基于 的 编码器设计与实现（英文），（）：梦欣 基于 的 编译码研究与设计 太原：中北大学，李锦明，刘梦欣，成乃朋 编码算法的优化与 实现电子技术应用，（）：，王兵锐，杨晓非，姚行中 译码优化及卫星通信 下 译码仿真 计算机应用研究，（）：胡鹏飞，沈力，宋茂江，等 可见光通信中 编译码 硬件算法及具体实现 贵州科学，（）：孙健，张辉，王宇飞，等 一种基于 （，）的编译码器设计微电子学与计算机，（）：张鹏泉，曹晓冬，范玉进，等 一种基于 的 编译码器设计与实现电子测试，（）：李锦明（副教授），主要研究方向为动态测试、数据采编；张萍萍（硕士研究生），主要研究方向为通信信号处理和 设计。通信作者：张萍萍，。（责任编辑：薛士然收稿日期：）