里德-所罗门伞型代码的并行分解

摘要

本发明的各实施方式总体上涉及里德-所罗门伞型代码的并行分解。具体地，呈现了一种用于处理码字的系统、方法、装置和技术。接收长度为n个符号并且具有k个校验符号的里德-所罗门母码字，并且接收的里德-所罗门母码字的n个符号被分成v个里德-所罗门子码字，其中v是与接收的里德-所罗门母码字相关联的分解因子。在v个并行处理的相应子集中处理v个里德-所罗门子码字以输出v个解码的码字。

说明书

背景技术

许多现代应用在使用循环纠错代码（诸如里德-所罗门代码）在 网络上传输数据之前对数据进行编码。此类代码能够提供强大的纠 错能力。例如，长度为n并且包括n-k个校验符号的里德-所罗门代 码可以检测多达t=n-k个错误符号的任意组合并且纠正多达个符 号的任意组合，其中表示地板函数。

里德-所罗门代码逐渐地用于高速数据应用。例如，针对底板的 IEEE802.3标准规定了里德-所罗门代码的使用。然而，足够快地对 里德-所罗门代码解码以满足此类高速数据应用的吞吐量要求可能是 具有挑战的。在一个方法中，多个前向纠错（FEC）电路被视为解码 器的一部分，以便达到期望的数据吞吐量。虽然多个FEC电路可以 以与整体器件成本（整体器件成本可以包括用于所需大小的裸片、 数字逻辑和收发器以及封装的成本）相比相对低的成本实现，但是 考虑到其他因素可能使得此类设计并不是所期望的。例如，实例化 与最大情况下所需一样多的FEC可能导致现场可编程门阵列 （FPGA）中包括太多的专用组件。

针对使用FEC代码（诸如里德-所罗门代码）的许多应用，其被 设计用于“典型”信道。在已知信道具有比代码被设计更低的错误 率的情况下，可以执行码字的部分解码。针对里德-所罗门代码，可 以采取完整码字被编码并且仅解码错误多项式的子集的形式。备选 地，码字可以仅被部分编码。

发明内容

呈现了一种用于处理码字的系统、方法、装置和技术。在某些 布置中，接收长度为n个符号并且具有k个校验符号的里德-所罗门 母码字，接收的里德-所罗门母码字的n个符号被分成v个里德-所罗 门子（daughter）码字，其中v是与接收的里德-所罗门母码字相关联 的分解因子。在v个并行处理的相应子集中处理v个里德-所罗门子 码字以输出v个解码的码字。

在某些布置中，码字处理电路包括：接收器电路，被配置为接 收长度为n个符号并且具有k个校验符号的里德-所罗门母码字；并 行化电路，被配置为将接收的里德-所罗门母码字的n个符号分成v 个里德-所罗门子码字，其中v是与里德-所罗门母码字相关联的分解 因子；以及解码电路，被配置为在v个并行处理的相应集合中处理v 个里德-所罗门子码字以输出v个解码的码字。

在某些布置中，错误定位多项式电路包括：以循环移位结构布 置的寄存器组，其中该寄存器组被配置为存储里德-所罗门母代码的 校验子（syndrome）值并且可分解成多个寄存器子组，每个寄存器 子组以循环移位结构布置并且被配置为存储与里德-所罗门母代码相 关联的里德-所罗门子代码的校验子值。

在某些布置中，钱氏搜索电路包括基于伽罗瓦域的乘和加结构， 以及分解的乘和加结构。在钱氏搜索电路的某些实现方式中，基于 伽罗瓦域的乘和加结构包括多个伽罗瓦域变量乘法器，其中该多个 伽罗瓦域变量乘法器被配置为将校验子值集合中的每个校验子值与 元素集合中的相应元素相乘，并且将每次乘法运算的结果相加以产 生多项式的根。另外，分解的乘和加结构包括与基于伽罗瓦域的乘 和加结构的一部分相同的电路，该分解的乘和加结构被配置为向与 基于伽罗瓦域的乘和加结构的一部分相同的电路应用元素集合的子 集。

在钱氏搜索电路的某些其他实现方式中，钱氏搜索电路包括基 于伽罗瓦域的乘和加结构，该基于伽罗瓦域的乘和加结构包括多个 伽罗瓦域固定乘法器，其被配置为选择该多个伽罗瓦域固定乘法器 的子集，使用该多个伽罗瓦域固定乘法器的子集中的一个伽罗瓦域 固定乘法器逐步地将校验子值集合中的每个校验子值与元素集合中 的相应元素相乘，并且将每次乘法运算的结果相加以产生多项式的 根。另外，分解的乘和加结构包括与基于伽罗瓦域的乘和加结构的 一部分相同的电路，并且被配置为向与基于伽罗瓦域的乘和加结构 的一部分相同的电路应用元素集合的子集。

附图说明

本发明的上述及其他优势在结合附图考虑了以下详细描述之后 将容易理解，其中贯穿全文相似的参考字符指代相似的部分，其中：

图1图示了根据一个布置的里德-所罗门解码架构；

图2图示了根据一个布置用于从接收的码字的校验子值确定错 误定位多项式的架构；

图3图示了根据一个布置用于基于里德-所罗门代码的伞型分解 从接收的码字的校验子值确定错误定位多项式的多核架构；

图4图示了根据一个布置用于执行钱氏搜索并且计算错误值的 架构；

图5图示了根据一个布置用于执行钱氏搜索并且计算错误值的、 基于里德-所罗门代码的伞型分解的架构；

图6图示了根据一个布置对应于具有长度为16个系数的错误定 位多项式（即，能够纠正多达16个符号错误）、并且具有并行度为 21的里德-所罗门母代码的移位系数；

图7图示了根据一个布置对应于图6的里德-所罗门母代码的两 个里德-所罗门子代码的移位系数；

图8图示了根据一个布置对应于图6的里德-所罗门母代码的四 个里德-所罗门子代码的移位系数；以及

图9比较并对比用于根据一个布置处理里德-所罗门母代码和里 德-所罗门子代码的对应子集的数据流。

具体实施方式

本文公开了一种用于在网络环境中实现里德-所罗门解码器和其 他类型的解码器的方法、系统和装置。所公开的方法、系统和装置 的优势在于使用了伞型代码以减少与解码里德-所罗门码字相关联的 延迟。

在许多情况下，为了减少的延迟权衡编码增益是占有优势的。 此类权衡可以基于里德-所罗门伞型代码在单个架构中实现。具体地， 里德-所罗门伞型代码被限定为更大里德-所罗门（RS）代码的整数 个子集。例如，（n，k）里德-所罗门代码分解成两个（n/2，k/2）里 德-所罗门代码，或者四个（n/4，k/4）里德-所罗门代码。在本公开 中，（n，k）里德-所罗门代码将被称为“母代码”，而基于该（n，k） 里德-所罗门代码分解的里德-所罗门代码（例如，（n/2，k/2）里德- 所罗门代码或（n/4，k/4）里德-所罗门代码）将被称为“子代码”。 作为第一说明性示例，（440，424）里德-所罗门母代码可以被分解成 两个（220，212）里德-所罗门子代码，或者四个（110，106）里德- 所罗门子代码。作为另一示例，（528，516）里德-所罗门母代码可以 被分解成两个（264，258）里德-所罗门子代码，或者四个（132，129） 里德-所罗门子代码。在四个（132，129）里德-所罗门子代码的情况 下，每个代码包括三个校验符号，因此能够纠正一个符号错误，这 与仅使用两个校验符号纠正的错误的数目相同。然而，这种由（132， 129）代码使用奇数个校验符号是有用的，这是因为相比于校验符号 的数目仅为二（即，偶数），码字之间增加的距离可以用于更精确地 检测错误。

用于改进FEC伞型代码实现方式的效率的一种可能是基于里德- 所罗门代码的伞型分解将里德-所罗门解码器分解成多个并行核。具 体地，通过里德-所罗门解码架构的延迟通常与2n成比例，因此如果 n被减少了，则延迟也被减少。无论使用多个并行核还是串行分解架 构，总功耗将是近似相同的，但是与串行分解情况相比，在多个并 行核的情况下延迟将被减少。另外，在多个并行核的情况下，相同 的接口和变速箱（gearbox）可以用于母代码和任意子代码。

图1图示了根据一个布置的里德-所罗门解码架构。解码器100 用于连续地处理接收的码字以恢复对应的数据字。解码器100通过 有线、无线或混合网络上的接收器电路（图1中未示出）接收码字。 在一个布置中，码字在100G底板上接收。

解码器100接收码字110，该码字110具有n个符号，其中k个 符号对应于数据符号以及n-k个符号对应于校验符号。因此，接收的 码字110还可以由其符号r₁,...,r_n或者一般地由符号r_i表示。在一个 布置中，接收的码字110由（440，424）里德-所罗门代码（即，k=424 并且n=440）生成，其中每个符号输送m=9比特的信息。常规地， 针对给定代码符号的可能值的数目由q^m表示，其中q和m均是整数 （换言之，代码符号选自GF（q^m），其中GF（u）表示u阶伽罗瓦 域）。这里，q=2并且m=9。在本发明的其他布置中，可以使用k、n 和/或q^m的其他值。

接收的码字110被提供至数据延迟缓冲器120和校验子计算模 块130。如这里所使用，术语“模块”指代用于实现关系该模块所述 的功能的任意适当电路。在一个布置中，给定模块的功能主要（或 全部）以基于FPGA的逻辑实现。数据延迟缓冲器120将接收的码 字110的输出延迟（例如，存储在寄存器中）以下时间长度（即， 时钟周期的数目），其足够接收的码字110的全部或一部分被校验子 计算模块130、错误定位多项式模块140以及钱氏搜索和错误计算模 块150处理。如下文所述，校验子计算模块130、错误定位多项式模 块140以及钱氏搜索和错误计算模块150中的每一个均采用基于里 德-所罗门伞型代码的并行架构。

校验子计算模块130处理接收的码字110以获得对应于该接收 的码字110的2t个校验子值135。该校验子值135将由S₁,...,S_2t表示。 例如，在（255,251）解码器的情况下，其特征在于值t=2，校验子值 由S₁、S₂、S₃和S₄表示。该校验子值根据以下等式计算

$S_j\left(x\right)=\underset{i=0}{\overset{n-1}{\Sigma }}{r}_i{x}^{\mathrm{ij}}$

其中j=1、2…2t，并且其中x^ij是来自m阶伽罗瓦域的元素。

虽然用于校验子计算的乘法器可以是变量乘法器（其中两个输 入可以被改变），使得并行分解可以通过仅改变系数实现，但是这并 不是非常高效。常量有限域乘法器（其中一个输入是可变的，而其 他输入是固定的）通常更小并且更快（更短的组合深度）。下面描述 了一种用于校验子值的计算的并行分解的技术。

由于校验子计算通常是解码器中最小的一部分，因此通常更有 效用于复制针对每个子代码的校验子计算的子集。针对母代码的校 验子计算可以用于通过将输入归零至更高阶校验子计算（更高的j 值）来计算针对任意子代码的校验子。所需的附加校验子计算结构 继而为Sj{0,t}、Sj{0,t/2}、Sj{0,t/4}等，假设总校验子计算 区域多达单独母代码的两倍。由于校验子计算是解码器中最小的一 部分，因此将设计的该部分的区域双倍将对整个区域的影响最小。

错误定位多项式模块140处理校验子值135以产生错误定位多 项式143和错误评估多项式146。错误定位多项式143和错误评估多 项式146在这里也可以分别由Λ(x)和Ω(x)表示。基于这里的公开和 教导，本领域普通技术人员容易理解错误定位多项式143和错误评 估多项式146可以使用适当的技术从校验子值135导出。例如，在 各布置中，错误定位多项式模块140包括实现欧几里得算法、彼得 生-哥伦斯汀-纪尔勒演算法、伯利坎普-梅西算法和伽罗瓦域傅里叶 变换方法之一的功能。

不考虑用于导出错误定位多项式143和错误评估多项式146的 技术，这些量中的每个量可以由m阶伽罗瓦域中的多项式表示。具 体地，错误评估多项式146由以下多项式表示

Ω(x)＝(Ω₁+Ω₂x+Ω₃x²....)   (1)

其中每个系数Ω_i均来自m阶伽罗瓦域。类似地，错误定位多项式143 由以下多项式表示

Λ(x)＝Λ₀+Λ₁x+Λ₂x²+Λ₃x³+Λ₄x⁴+Λ₅x⁵+....   (2)

其中系数Λ_i来自m阶伽罗瓦域。基于这里的公开和教导，本领域普 通技术人员容易理解错误定位多项式143用于执行钱氏搜索，而错 误定位多项式143的导数用于评估错误值。错误定位多项式143被 提供至钱氏搜索和错误计算模块150以产生错误值160。该错误值 160也可以由e₁,...e_n表示，其中e_i表示接收的码字110第i个位置中 错误的值。

为了确定错误值160，钱氏搜索和错误计算模块150实现钱氏搜 索模块和错误值计算模块两者，其中钱氏搜索模块用于标识接收的 码字110中包含错误的符号位置，而错误值计算模块用于确定在所 标识符号位置处的错误值。基于这里的公开和教导，本领域普通技 术人员容易理解钱氏搜索模块确定错误定位多项式143的根（如果 有的话）。具体地，钱氏搜索模块通过评估适当伽罗瓦域中对应于接 收的码字110中相应位置的每个值处的错误定位多项式以确定该错 误定位多项式是否在该位置具有等于0的值来实现。如果是，则接 收的码字110被标识为在该位置具有错误。如果否，则接收的码字 110被标识为在该位置没有错误。

等价地，为了便于实现，钱氏搜索模块可以通过代数上相同或 等价的方式将错误定位多项式减去值1的值与该值1进行比较，而 不是将错误定位多项式的评估值与值0进行比较。类似地，钱氏搜 索模块可以执行与这里所述相比任意其他代数上等价形式。

钱氏搜索和错误计算模块150将针对接收的码字110中由钱氏 搜索模块标识的每个位置的错误值e_i确定为包含符号错误。具体地， 钱氏搜索模块使用基于福尼算法的技术来评估错误值。使用福尼算 法，钱氏搜索模块根据以下关系确定错误值e_i

$e_i=\frac{\Omega \left(x^{-i}\right)}{{\Lambda }^{\prime }\left(x^{-i}\right)}---\left(3\right)$

基于这里的公开和教导，本领域普通技术人员容易理解钱氏搜索模 块还可以使用代数上等价关系确定错误值e_i。

图2图示了根据一个布置用于从接收的码字的校验子值确定错 误定位多项式的架构。在一个布置中，架构200包括在错误定位多 项式模块140中。图2图示了错误定位多项式模块140基于伯利坎 普-梅西算法计算错误定位多项式并且校验符号的数目n-k为16的情 况。因此，存在16个校验子值S₁,...,S₁₆，其被存储在寄存器组201 的16个对应寄存器中。因为存在16个校验子值，因此架构200需 要16次迭代以产生错误定位多项式（即，存在与校验子同样多的迭 代）。具体地，存储在寄存器组201中的校验子值随每次迭代循环移 位。错误定位多项式是将所有符号连接在一起的多项式，即，任意 校验子值可以通过将先前校验子多项式与错误定位多项式相乘找 到。

架构200的每次迭代的第一步骤是找到错误定位多项式当前状 态的校验子与先前校验子之间的差或增量值。这可以通过采取寄存 器组201中存储的校验子的数目与错误定位多项式当前状态（其存 储在寄存器组219中）的点积完成，从而使用乘法器组220的伽罗 瓦域乘法器将这些两个量相乘在一起，使用伽罗瓦域加法器209、210 和212将各结果相加，并且使用伽罗瓦域加法器211加上第一校验 子。在对应的迭代结束时，将计算的增量值存储在寄存器213中。

如果增量值非零，则更新错误定位多项式。这通过将存储在寄 存器组221中的先前错误定位多项式逐项与包括被先前增量值相除 的增量值的值（后一个值由除法器214计算）相乘来完成。乘法器 组220的各乘法器输出继而使用加法器组217相加至相应的错误定 位多项式项，并且其结果被存储在寄存器组219中。增量值继而被 存储在寄存器213中，并且错误定位多项式（在乘法器结果被相加 之前）被存储在寄存器组221中。控制块223用于控制用以实现上 文所述功能的信号电压电平和时序。

因为由架构200执行的迭代的数目与校验子的数目相同，因此 一种用于产生架构200的并行分解的方式可以是存储多个校验子集 （每个校验子集均是母代码校验子数目的整数部分（integer  fraction）），并且依次对每个校验子集进行操作。这仍然会在等同于 母代码计算时间的总时间内执行所有错误定位多项式计算。然而， 在最差情况下，子代码延迟将与母代码延迟相同（至少通过处理流 水线这部分）而不是时间的整数部分。一种备选方法用于将伯利坎 普-梅西架构拆成如接下来解释的整数个并行核。

图3图示了根据一个布置用于基于里德-所罗门代码的伞型分解 从接收的码字的校验子值确定错误定位多项式的多核架构。虽然架 构300图示了两个并行核的情况，但是同一原理和技术可以用于设 计具有任意整数个并行核的架构，该整数等于母代码与对应的子代 码之间的分解因子。例如，在FPGA利用（n，k）母代码和（n/4， k/4）子代码的情况下，架构300可以基于这里所述的技术适用于包 括四个并行核。

如图3所示，架构300的两个核沿虚线350拆分。虽然引入第 二核要求附加的（即，第二）控制块，但是与逻辑相关联的控制块 324（或备选地，控制块323）与架构300中呈现的其他逻辑元件相 比在尺寸上相对较小。如与架构200的寄存器组201相比，架构300 包括两个单独的寄存器组（即，寄存器组380和寄存器组382），并 且包括附加多路复用器（即，多路复用器304）。多路复用器304包 括表示微量的附加逻辑（另外，在FPGA中，与寄存器相关联的逻 辑可以执行多路复用器304的功能使得不需要附加逻辑）。类似地， 鉴于架构200包括加法器组217、寄存器组219和寄存器组221，架 构300包括这些组件的分离版本，即，加法器组317和318、寄存器 组319和320以及寄存器组321和322。

继续与架构300相比，分解增量值计算所需的伽罗瓦域加法器 树。具体地，图3的加法器309和310（这在图2中具有对应的加法 器209和210）不向图2的加法器212馈送对应物（counterpart），而 是其相应加法器树的最终状态。这一关于架构200的改变将在每核 分解时最多利用一个附加多路复用器。另外，每个附加核分解利用 附加伽罗瓦域除法器（即，架构300包括除法器314和316，而架构 200仅包括单个此类除法器，即除法器214）以及相关联电路，即图 3中的加法器311和312以及寄存器313和315。

图4图示了根据一个布置用于执行钱氏搜索并且计算错误值的 架构。在一个布置中，架构400包括在钱氏搜索和错误计算模块150 中。出于说明的目的，图4图示了校验符号的数目n-k为8的情况。 因此，存在8个校验子值S₁,...,S₈。如图4所示，架构400采用度为 x+1的并行结构，其中x是伽罗瓦域乘法器409的根幂的指数。

由错误定位多项式模块140计算的错误定位多项式项被输入至 架构400，并且由乘法器组401中的乘法器移位至第一移位位置。第 一搜索位置由原根的幂移位。此值是域大小与码字中符号数目之间 的差。例如，由IEEE802.3指定的NRZ FEC标准具有n=528个总符 号、k=514个数据符号、每符号m=10个比特。因此，域大小为 2^m=1024，并且移位值为1024-528=496。另外，因为此根指数的倍数 大于该域大小，因此以域大小为模计算更高阶根指数。

备选地，在一个布置中，由乘法器组401的乘法器执行的移位 可以通过在向架构400发送每个错误定位多项式系数之前将该系数 乘以适当的移位值来由架构200的乘法器组220的乘法器代替执行。

考虑并行度为1（即，x=0）的情况。在此情况下，由乘法器组 401输出的移位错误定位多项式被输入至乘法器组403的乘法器。具 体地，乘法器组403中的每个乘法器是具有通过启用乘法器组402 的对应乘法器产生的系数指数中递增根幂（α¹,α²,α³,α⁴等）的常量 乘法器。乘法器继而被迭代用于测试的位置的数目，其总共为n个 符号。乘法器组403的输出由加法器404全部相加以检验错误定位 多项式的根，即，用于确定在指定符号位置是否存在错误。

备选地，在一个布置中，由乘法器组510和511的乘法器执行 的移位可以通过在向架构400发送每个错误定位多项式系数之前将 该系数乘以适当的移位值来由架构300的乘法器组307和308的乘 法器代替执行。

考虑并行度为x＞0的情况。在此情况下，针对乘法器组403中 乘法器的系数的根幂被乘以量x+1，其导致输出α^(x+1)、α^2(x+1)、α^3(x+1)、 α^4(x+1)等。这意味着由乘法器组403中的乘法器搜索的位置可以增加 x+1个位置。中间值继而可以被搜索而不需要使用错误定位多项式， 而是通过将乘法器组403的乘法器输出移位一个或多个（多达x个） 位置。这可以使用乘法器405、407和409执行。类似地，加法器406、 408和410继而可以将移位值相加以检验错误定位多项式的根。

图5图示了根据一个布置用于执行钱氏搜索并且计算错误值的、 基于里德-所罗门代码的伞型分解的架构。具体地，图5描绘了类似 于架构400但被分解成两个并行子结构的架构。具体地，架构500 描绘了母（n，k）里德-所罗门代码至两个（n/2，k/2）子里德-所罗 门代码的伞型分解。基于这里的公开和教导，本领域普通技术人员 容易理解虽然架构500图示了分解因子为二，但是同一原理和技术 可以用于设计等于母代码与对应的子代码之间的任意有效分解因子 的架构。

如与架构400相比，架构500要求附加的输入移位乘法器组510 和乘法器组523（为了清楚该组中仅绘制了一个乘法器）。乘法器组 511的乘法器用于将母代码错误定位多项式移位至第一搜索位置，并 且乘法器组510的乘法器用于将两个子代码多项式移位至其第一搜 索位置。因此，乘法器组511中的四个乘法器的移位值是不同的， 而乘法器组510中的四个乘法器的移位值表示相同移位值的两个集 合。

针对两个子代码搜索，乘法器组514中的四个乘法器被拆成两 组两个乘法器，其中每组搜索相应的子代码错误定位多项式。类似 地，乘法器组520中的四个乘法器和乘法器组517中的四个乘法器 各被拆成两组两个乘法器。具体地，乘法器组517和520中的每个 乘法器组内的每组乘法器将其相应子代码基础搜索值移位至与母代 码相同数目的并行位置。

如同架构400的情况一样（例如，参见加法器406、408和410 的输出），架构500不对分组中所有乘法器的输出相加。相反，在架 构500中，针对每个移位的搜索位置以及每个子代码仅对乘法器输 出的子集相加。例如，加法器521仅对乘法器541和542的输出相 加，并且加法器519仅对乘法器543和544的输出相加。此外，与 架构400的那些加法器406和408相同的加法器也存在于架构500， 但出于视觉上清楚从图5中省去。

注意，将t=2母代码拆成由架构500所示的两个t=1子代码的简 单情况仅是说明性的。在实践中，使用具有越大多项式长度的母代 码，节省越大。这是因为更大的多项式长度使得特定多项式项的移 位乘值更可能存在于乘以所有移位值的所有多项式项的矩阵中，因 此可以获得节省。

图6图示了根据一个布置对应于具有长度为16个系数的错误定 位多项式（即，能够纠正多达16个符号错误）、并且具有并行度为 21的里德-所罗门母代码的移位值的幂（即，移位值α^x中x的相应 值）。在表600中，每列对应于应用于将搜索位置的基础状态移位至 不同位置的移位值的幂。表600的20个列对应于每时钟周期搜索的 20个附加搜索位置（除基础位置外）。表600的值为可以被输入至对 应于图5的乘法器组517和520的乘法器组（或者，取决于里德-所 罗门代码的参数、那些乘法器组的适当修改版本）。具体地，架构500 中由表600描绘的里德-所罗门母代码的实现方式可以要求320个乘 法器，这是由于表600中存在320个条目。

图7图示了根据一个布置对应于图6的里德-所罗门母代码的两 个里德-所罗门子代码的移位系数。具体地，表725图示了应用于将 搜索位置的基础状态移位至与第一子代码相关联的八个乘法器中的 每个乘法器的不同位置的移位值的幂，并且表775图示了应用于将 搜索位置的基础状态移位至与第二子代码相关联的八个乘法器中的 每个乘法器的不同位置的移位值的幂。

实现表700的两个子代码所需的乘法器数目小于实现对应于表 600的母代码所需的320个乘法器。具体地，在一个布置中，第一子 代码使用160个乘法器的“全集”（对应于表725中的160个条目） 来实现。然而，给定此实现方式中，小于160个乘法器被需要用于 实现第二子代码。这是因为存在从第一子代码的实现可获得的母代 码和第二子代码的实现中计算的某些多项式项的移位版本。图6图 示了通过第二子代码的实现重用来自第一子代码和母代码的实现的 乘法器输出。具体地，表775中的下划线值表示乘（即，计算的乘 法运算值）针对第一子代码的实现中给定多项式项的电路中。由于 表775中存在27个下划线项，因此存在27个可以被重用的乘法器。 因此，对应于表700的两个子代码的实现需要总共仅293个乘法器 （而不是总共320个乘法器）。

图8图示了根据一个布置对应于图6的里德-所罗门母代码的四 个里德-所罗门子代码的移位值的幂。具体地，表820图示了应用于 将搜索位置的基础状态移位至与第一子代码相关联的四个乘法器中 的每个乘法器的不同位置的移位值的幂。类似地，表840、860和880 图示了应用于将搜索位置的基础状态移位至分别与第二子代码、第 三子代码和第四子代码相关联的四个乘法器中的每个乘法器的不同 位置的移位值的幂。

如表840和880中下划线条目所示，第二子代码和第四子代码 的实现可以重用来自母代码（图6）和第一子代码分解（图7）两者 的乘法器。图8的下划线中示出了经复制的乘。如表820和840中 所示，重用了51个乘，使得需要总共仅109个乘法器（而不是160 个乘法器）用于实现第一子代码和第二子代码。另外，如表860和 880中所示，第三子代码具有69个重用的乘，使得需要总共仅91 个乘法器（而不是160个乘法器）用于实现第三子代码和第四子代 码。通过类似方式，里德-所罗门母代码的实现可以被分解成八个里 德-所罗门子代码以达到更高的乘重用度。另外，在使用了16个里德 -所罗门子代码的情况下，所有乘的一半可以被重用，使得总共仅需 要160乘法器。注意，通常在解码器实现中并非需要母代码中的所 有子代码分解。具体地，给定实现方式可以仅支持里德-所罗门母代 码的可能里德-所罗门子代码分解的子集。

例如，在t=16代码被分解成两个t=8、四个t=4、八个t=2以及 十六个t=1的子代码的情况下，640个附加乘法器需要用于实现所有 硬件结构，并且在一个布置中，这可能是钱氏搜索电路（其已经是 高度并行解码器）区域的几乎三倍。相反，通过使用如上文所述的 优化系数矩阵，针对这些分解结构的每个分解结构，总共仅需要 133+109+91+80=413个附加乘法器。

图9比较并对比用于根据一个布置处理里德-所罗门母代码和里 德-所罗门子代码的对应子集的数据流。如图9所示，两个（n/2，k/2） 里德-所罗门子代码可以在与（n，k）里德-所罗门母代码近似相同的 时间量（时间Δ）内处理。另外，校验子计算所需的计算的数目与 n²–nk成比例，使得确定两个（n/2，k/2）里德-所罗门子代码的校 验子所需的计算复杂度与确定一个（n，k）里德-所罗门母代码的校 验子所需的计算复杂度近似相同。

另外，计算错误定位多项式所需的计算复杂度与(n-k)²成比例， 使得确定（n/2，k/2）里德-所罗门子代码两者的多项式所需的计算 复杂度与确定一个（n，k）里德-所罗门母代码的多项式所需的计算 复杂度近似相同。正如校验子计算，钱氏搜索的计算复杂度也与（n²–nk）成比例，但是如上文参考图6至图8所解释的，此逻辑的一般 大尺寸意味着需要逻辑重用。

应当理解，上文仅说明了本发明的原理，本领域技术人员可以 在不脱离本发明的范围和精神的前提下进行各种修改，并且本发明 仅受限于以下的权利要求书。