用于检测和校正所接收的符号串中的定相突发差错、删除、符号差错和位差错的方法和系统

摘要

本发明的实施例包括基于ECC的编码和解码方案，其很好地适用于校正定相突发的差错或删除以及附加的符号差错和位差错。每个代表本发明的实施例的编码和解码方案是由两个或更多分量纠错码和映射函数f(·)构造的。除了单个位差错和符号差错之外，代表本发明的实施例的复合纠错码与单独的任何一个分量码相比能够分别校正更长的定相突发或更大数量的删除，并且比先前开发的用于校正与附加的位差错和符号差错结合的定相突发的符号差错和删除的基于ECC的编码和解码方案更高效。

说明书

技术领域

本发明涉及校正在通过差错和删除引入(error-and-erasure-introducing)信道的符号串中发生的差错或删除，包含对符号串的电子传输或将符号串存储在电子存储器中和从该电子存储器检索(retrieval)该符号串。

背景技术

纠错码(“ECC”)领域已经被仔细研究和探讨了50年以上。许多不同类型的基于纠错码的编码-解码方案已经被开发用于许多不同的问题领域。基于ECC的编码-解码方案一般涉及将冗余信息引入到编码的信息流中以允许随后在信息流中引入的各种类型的差错将被检测和校正。与大多数计算技术一样，存在多种与应用于任何特定问题领域的任何特定编码-解码方案相关联的优点、缺点、高效和低效。例如，随着添加到信息流的冗余信息量的增加，信息流内可被检测和校正的差错的数量和类型一般会增加，但是由于冗余信息的开销增加使得信息流的传输的信息效率或空间效率降低。空间低效也可能是由于需要创建和维持编码或解码所需的大量数据(比如下面所讨论的解码表)而造成的。作为另一个示例，符号高效码可能涉及复杂计算，并且因此可能是计算低效的或时间低效的。码的总效率与码的空间和时间效率的和相关，但是空间效率的获得通常是以时间效率为代价的，且反之亦然。某些类型的基于ECC的编码-解码方案更好地适合检测和校正某些类型的差错，并且可能不太适合用于检测和校正其他类型的差错。随着新问题领域被认识到或随着作为新类型的技术的发展结果而出现新问题领域，很好地适用于新近认识到的问题领域或新近发展的技术的新ECC和基于ECC的编码-解码方案的继续发展是需要的，以便提供高效和准确的差错检测和校正。

发明内容

本发明的实施例包括基于ECC的编码-解码方案，其很好地适合于校正定相突发(phased-burst)的差错或删除以及附加的符号差错和位差错。代表本发明的实施例的每个编码-解码方案是从两个或更多分量(component)纠错码和映射函数f(·)构造的。除了单个位差错(single-bit error)和符号差错之外，代表本发明的实施例的复合纠错码与单独的任何一个分量码相比可以分别校正更长的定相突发或更大数量的删除，并且比先前开发的用于校正与附加的位差错和符号差错结合的定相突发的符号差错和删除的基于ECC的编码-解码方案更高效。

根据本发明的一个实施例，将信息编码为复合码码字是通过接收K₁个信息符号并且通过第一分量码C₁编码器编码这K₁个信息符号以产生长度为N₁个符号的C₁码字u来实现的。然后，K₂个信息符号由第二分量码C₂编码器来编码以产生长度为N₂的码字v。通过将u的非恒等(non-identity)映射f(u)加到v而获得长度为N₂个符号的向量w。最后，复合码C码字通过将u和w级联在一起而生成。

根据本发明的一个实施例，复合码码字的解码是通过解码分量码码字来实现的。包含K₁个信息符号的长度为N₁的分量码C₁码字u和在编码期间从包含K₂个信息符号的分量码C₂码字v和非恒等映射函数f(·)生成的长度为N₂的修改的分量码C₂码字w＝v+f(u)(其中K＝K₁+K₂且N＝N₁+N₂)从复合码C码字中被提取。估计的分量码C₂码字和估计的差错字然后通过将C₂解码器应用到修改的分量码C₂码字而从修改的分量码C₂码字生成。若干类型的预期差错中的哪一个可能在对复合码C码字进行编码之后发生是根据差错字确定的。当超过第一阈值数量的删除和删除已经发生但小于第二阈值数量的差错已经发生时，所确定的差错被分配给分量码C₁码字或分配给修改的分量码C₂码字，并且当分配给分量码C₁码字时被校正。其他差错和删除的发生被标记。估计的分量码C₁码字是通过将C₁解码器应用到估计的分量码C₁码字而获得的。最后，K₁个信息符号从估计的分量码C₁码字中被提取，并且K₂个信息符号从估计的分量码C₂码字中被提取以产生K个提取的信息符号。

附图说明

图1示出基于ECC的编码-解码方案所应用到的基本问题。

图2示出数字编码信息流的各种不同视图。

图3A示出将信息编码为长度n的码字的系统线性块码(block code)所产生的所有可能的码字的向量空间V。

图3B示出图3A中所示的向量空间V的示范性码或向量子空间。

图4示出任意两个码字v和w之间的距离D(v，w)。

图5示出通过系统线性块码对k个信息位的向量u的编码和传输。

图6示出编码信息位向量u以产生码字v，如参照图5所讨论的。

图7A-B示出用于系统线性块码的示范性系统生成矩阵G和示范性系统奇偶校验矩阵H。

图8示出奇偶校验矩阵的转置H^T的属性。

图9示出用于系统线性块码的解码过程的一部分。

图10示出可以针对GF(2)上任何系统线性块码构造的解码表。

图11示出用于GF(2⁸)的元素的表的一部分。

图12示出代表本发明的一个实施例的复合码的基本特性。

图13示出本发明的实施例中所使用的符号到符号映射函数f(·)的特性。

图14示出符号到符号映射函数f(·)的两种不同的实现方式。

图15A提供用于将信息位编码为根据本发明的一个实施例的复合码码字的高级控制流程图。

图15B示出代表本发明的一个实施例的复合码C[72，66，5]的构造。

图16示出一种编码复合码码字的方法，该方法可以对信息符号的输入流重复执行以产生复合码码字的输出流。

图17A示出代表本发明的一个实施例的复合码的码字内的子块的概念。

图17B示出代表本发明的一个实施例的复合码被设计用于检测和校正的各种不同类型的差错。

图18提供用于解码代表本发明的一个实施例的复合码的高级控制流程图。

图19-20提供了示出用于代表本发明的实施例的复合码的解码过程的一个实施例的控制流程图。

图21示出用于代表本发明的一个实施例的复合码的解码方法的每个步骤所接收的信息。

图22示出其中可以使用本发明的实施例的物理存储设备的框图。

图23示出码字符号与DRAM单元组(bank)中的DRAM单元之间的映射，这些DRAM单元共同构成图22所示的物理存储设备的电子数据存储组件。

具体实施方式

本发明针对纠错码(“ECC”)和基于ECC的编码-解码方案，其很好地适用于在通过删除和差错引入信道的符号串中分别检测和校正定相突发的符号差错和/或删除以及附加的单个位差错和符号差错。下面在三个子部分中讨论本发明。在第一子部分，提供一个族的纠错码的概述。这些纠错码是可以用于构造代表本发明的实施例的复合ECC的分量ECC的示例，不过许多附加类型的ECC可以用作复合ECC的分量。在接下来的子部分中，提供对群和域的简要概括。最后，在第三子部分，描述本发明所针对的复合码和基于复合码的编码-解码方案，其中详细描述了用于一种公开的复合码的编码和解码方法。

系统线性块码

图1示出基于ECC的编码-解码方案被应用到的基本问题。在图1中，二进制编码信息流102被输入到呈现出差错引入信道105的特性的存储器、通信系统或其他电子设备、子系统或系统104。随后，从存储器、通信系统或其他电子设备、子系统或系统104提取106数字编码的信息流。期望的且一般必需的是，所提取的信息流106与原始输入的信息流102等同。为了实现输入到存储器、通信系统或其他电子设备、子系统或系统104的信息的无差错恢复，编码器108可以用于将冗余信息引入到信息流中并且解码器110可以用于使用该冗余信息来检测和校正由存储器、通信系统或其他电子设备、子系统或系统104的差错引入信道特性所引入的任何差错。在图1中，二进制编码的信息流在输入时以左到右的方向102表示而在提取106时以右到左的方向表示。然而，在对基于ECC的编码-解码方案的一般讨论中，编码的信息流一般以左到右的次序表示，而不管信息流是代表输入信息流还是代表所接收的信息流，条件是编码的信息一般顺序地、逐位、或逐字节传输且然后在接收时重新组合。

电子通信介质可能呈现出差错引入信道特性，所述电子通信介质比如在一端具有发射端口而在另一端具有接收端口的光纤电缆、具有包含在由该以太网链路连接的计算设备中的控制器和以太网端口的以太网链路，并且在其他常见的电子通信介质中可能呈现差错引入信道特性。可替代地，信息存储设备或组件可呈现出差错引入信道特性，该信息存储设备或组件包括不同类型的电存储器、大容量存储设备或物理数据存储介质(比如DVD或CD)。在通信介质的情况下，最初输入到发射端口的信息流随后可能被接收端口接收为被破坏的(corrupted)信息流，其中通过端口处理组件、传输介质中的噪声和其他这样的差错引入现象将差错引入到该信息流中。在存储介质的情况下，输入到存储介质的初始信息流随后可以以被破坏的形式从存储介质中被检索，其中通过存储组件控制器和其他处理组件、通过噪声和传输介质以及通过存储介质中的电子的、磁性的和/或光学的不稳定性将差错引入到信息流中。

存在各种类型的可以破坏编码的信息流的差错。随机位或符号差错可以导致信息流中的某些位和符号的位或符号值的变更，其中信息流中的位或符号具有已知的或可估计的破坏概率。突发差错导致连串的邻近位和/或符号的破坏。除了突发差错之外，许多不同类型的系统差错也可能发生。

图2示出数字编码的信息流的各种不同视图。数字编码的信息流可以被看作位值的有序序列，或换言之，信息流包括位值的长线性阵列。可替代地，相同的编码信息流可以被看作符号的有序序列，每个符号包括固定数量的位值。例如，在图2中，二进制编码信息流202可以可替代地被看作四位符号的有序序列204。图2所示的符号的有序序列中的第二符号206的值“9”对应于编码信息流202的位值表示中的位值208-211的有序集合。在又一个视图中，编码信息流可被看作块的有序序列212，每个块包含固定数量的符号的有序序列。最后，可以通过系统线性块码对信息流进行编码，从而包括冗余信息以允许随后检测和校正差错。编码信息流214包括块或码字的有序序列，每个码字对应于信息流中的块。例如，编码信息流的码字216对应于信息流的块视图212中的符号的块218。每个码字包括附加的符号220-222，在图2中由字符R′、R″和R″′表示。该额外符号代表一种类型的系统线性块码在信息流中包含的冗余信息。在可替代类型的线性块码中，每个码字可以包括第一选定数量的信息符号以及代表所添加的冗余信息的第二选定数量的附加符号，其中冗余信息符号与信息符号的比率一般与可被检测的差错或删除的数量和可被校正的差错或删除的数量相关。

一种常用类型的ECC是有限域GF(q)上的系统线性块码，其中q表示在其上定义码的域中的符号的数量。当q为2的幂，2^m时，该域的符号被表示为m元组。当m等于8时，符号被方便地表示为字节。记号“GF(2)”代表具有两个元素或符号“0”和“1”的二进制伽罗瓦域(Galois域)。给定由在GF(2)上的系统线性块码产生的每个编码的块或码字中固定数量的位，所有可能的码字一起构成向量空间。向量空间具有某些代数性质，包括加法的交换律、标量乘法的封闭性，并且向量空间关于向量加法和向量的标量乘法具有分配律和结合律。图3A示出在GF(2)上的长度为n的所有可能位向量的向量空间V。产生长度为n的码字的特定系统线性块码C是V的k维向量子空间，该向量子空间具有向量空间的所有性质。图3B示出图3A所示的向量空间V的示范性码或向量子空间。向量子空间中的每个k维向量代表来自信息流的k位信息。系统线性块码用r＝n-k个附加位补充该k位信息以产生码字。对于信息位的每个不同的可能的k维向量，存在一种特定模式(pattern)的r个附加位或奇偶校验位。因此，系统线性块码包括向量空间V的2^k个不同的n-位向量，其构成向量子空间。对于在GF(q)上的系统线性块码，每个向量包含n个符号而不是位，其中k个符号是信息符号且n-k个符号是用于检测和校正差错的冗余信息。包含GF(q)上的系统线性块码的码字的向量子空间包括q^k个向量。

ECC的重要特性是码的任意两个码字之间的最小距离d。图4示出GF(2)上的ECC的任意两个码字v和w之间的距离D(v，w)。向量v是12位码字402且w是第二12位码字404。通过模2减法从v减去w(相当于逐位XOR运算)产生v与w之间的差v-w，406。在GF(2)上的ECC的情况下，向量v-w 406中位值为“1”的位的数量等于v和w之间的距离D(v，w)。在GF(q)上的ECC的一般情况下，差向量v-w中非零位置的数量是这两个码字v和w之间的距离。任何特定的码字v的权重W(v)是该码字中非零位置的数量。因此，在图4中示出的示例中，D(v，w)＝W(v-w)＝3。

图5示出k个信息符号的向量u通过q-进制系统线性块码而进行的编码和传输。这k个信息符号被认为是k-维向量u 502。系统线性块码将由向量u表示的这k个信息符号编码为长度为k+r＝n的向量v 504。系统线性块码将r个校验符号或奇偶符号一起放置在向量v的长度为r的子向量中，该子向量一般处于向量v的开始处或末尾处。在图5所示的以及后续的图中继续示出的示例中，在向量v的开始部分示出奇偶符号p₀，p₁，…，p_r-1506，并且后面跟着k个信息符号508。码字v然后通过通信介质被传输或被存储到存储介质并且被从中检索以产生对应的接收的字x510。当在传输或存储过程中没有发生差错时，x＝v。然而，当发生随机传输或存储差错时，x≠v。在许多情况下，向量x的接收者无法将x与初始的、对应的向量v进行比较以便确定是否已经发生差错。因此，向量x的接收者假定x中的每个符号或位可能已经以某破坏概率被破坏。因此，在图5中x中的符号被加撇号(primed)以指示这些符号可能已经以已知的或可估计的破坏概率被破坏。因此，码字v中的符号p₀512对应于所接收的字x中的符号p₀′514。

图6示出对信息-位向量u进行编码以产生码字v，如参照图5所讨论的那样。对于给定的系统线性块码，可以找到kxn矩阵G 602，以生成对应于每个可能的信息符号向量u的唯一码字v。如图6所示，u 604乘以G 606以产生对应于u的码字v 608。矩阵G被称为用于系统线性块码的生成矩阵。矩阵G由系统线性块码C的k个线性独立的码字组成。因此，系统线性块码的码字容易地且机械地通过矩阵乘法从对应的信息符号块生成。实际上，每个矩阵G都定义了系统线性块码。

图7A-B示出示范性系统生成矩阵G和用于系统线性块码的示范性系统奇偶校验矩阵H。如图7A所示的生成矩阵G 702可以在空间上划分成维度为kxr的奇偶校验位矩阵P 704和kxk单位矩阵I_k706。在矩阵乘法uxG期间，奇偶校验位矩阵P生成v的r个奇偶符号，并且单位矩阵I_k706生成码字v内的u的k个信息符号。

对于每个系统线性块码，存在对应于生成矩阵G的奇偶校验矩阵H。图7B示出奇偶校验矩阵H的形式。如从图7B中可以看出，奇偶校验矩阵是rxn矩阵，其可以在空间上划分为rxr单位矩阵-I_r710和奇偶校验矩阵的转置P^T712。任何特定系统线性块码完全由生成矩阵G或由对应于生成矩阵G的奇偶校验矩阵H指定。奇偶校验矩阵H本身是线性码的生成器，其中每个码字包括r个信息符号。由奇偶校验矩阵生成的线性码是由生成矩阵G生成的系统线性块码C的对偶码。图8示出奇偶校验矩阵的转置H^T的性质。如图8所示，奇偶校验矩阵的转置H^T802在被用于乘以系统线性块码C的码字v时，总是生成维度为r的全零向量0 806。换言之，对于系统线性块码C的每个码字v来说：

v·H^T＝0

图9示出用于系统线性块码的解码过程的一部分。如上所讨论的，所接收的字x902可以包含关于对应的初始传输或存储的码字v904的差错。如上所讨论的，在v和x这二者都已知的情况下，从x减去v产生冗余向量906，其中非加性恒等(non-additive-identity)符号(在GF(2)的情况下为″1″)出现在向量x和v不同的每个位置处。因此，x-v＝e，其中e被称为“差错向量”，其本质上是所发生的差错的图(map)。当然，一般地只有x是已知的。因此x等于v+e，其中v和e一般是未知的。所接收的字x908与奇偶校验矩阵的转置H^T，910相乘产生r-维向量s912，其被称为x的“校正子(syndrome)”。x的校正子等于e·H^T。因此：

s＝e·H^T＝xH^T

图10示出可以针对GF(q)上的任何系统线性块码构造的解码表。如图10所示，被称为“标准阵列”的q^rxq^k表1002可以针对任何系统线性块码构造。该标准阵列的第一行1004是码字的有序序列v₀，v₁，v₂，…，v_q^k_-1。码字v₀是全零符号码向量(0，0，…，0)。标准阵列的每列i可以被认为包含对应于该列的第一个元素中的码字v_i的所有可能的接收的字x_j。换言之，所有可能的接收的字的集合V具有qⁿ个元素，并且被划分为q^k个分区(partition)，每个分区对应于系统线性块码C的码字，其中任何接收的字x被认为对应于与x所属于的所有可能的码字的分区相关联的码字。例如，标准阵列的第一列1006的所有元素对应于在被加到全零码字v₀时产生被解码为该全零码字v₀的接收字的所有可能的差错向量。

如参照图9所讨论的那样，接收的字x与奇偶校验矩阵的转置H^T相乘产生等于e·H^T的校正子向量s。因此，针对标准阵列的每行中所有元素计算的校正子是相同的，其仅仅依赖于e和H^T。因此，为了解码的目的，标准阵列中所包含的信息可被压缩为解码表1008，该解码表示出每个识别(recognized)的差错模式e_i与对应于该差错模式的校正子e_iH^T之间的关联。系统线性块码的码字的解码与编码类似是通过概念上相对简单的过程来实现的：

然而，尽管在概念上简单，但是设计可被高效解码的码显然是繁琐的任务。例如，解码表对于具有中等的和大的参数q、r和/或n的码来说是不切实际的，因为解码表1008的大小与2(q^r)(n)成比例。因此，一般要进行大的努力来设计具有允许在空间和时间上都高效的解码算法的性质的码。

如在图10所示的标准阵列中可以看出，通过增加每个码字中所包含的奇偶符号的数量，可以识别更多数目的不同差错模式。然而，随着比率增加，编码的空间效率降低。一般地，由系统线性码所识别的差错模式被选择为最可能的差错模式。对于随机位差错，具有最小权重的差错向量一般地是最可能的差错模式。对于其他类型的差错，差错模式的不同集合会更有可能。

尽管上文已经讨论了GF(2)上的系统线性块码，但是类似地可以在任何域GF(q)上构造包含里德-所罗门(Reed-Solomon)码的系统线性块码。通常，在GF(2)的扩展域上构造系统线性块码是方便的，该扩展域一般被指定为GF(2^m)，其中m是大于1的整数。

群(group)和域(field)

在该子部分中，提供群和域的概述。群是元素的集合，在其上定义二进制运算*。该群在二进制运算*下是封闭的。换言之，对于群中任意两个元素a₁和a₂，a₁*a₂＝a_i，其中a_i也是该群中的元素。该二进制运算*满足结合律，使得：

(a₁*a₂)*a₃＝a₁*(a₂*a₃)

群具有唯一的单位元素e，使得对于群中的每个元素a_i，存在逆元素a_i^-1：

a_i*a_i^-1＝a_i^-1*a_i＝e

当对于任意一对元素a_i和a_j有：

a_i*a_j＝a_j*a_i

时，群满足交换律或群是阿贝尔群。

域是关于两种不同的二进制运算的可交换群。一种运算可以表示为“+”，其中运算+的单位元素e+等于0，并且另一种运算可以表示为“*”，其中运算*的单位元素e^*等于1。而且，运算*满足分配率：

a*(b+c)＝a*b+a*c

GF(2)是二进制域，其中+运算相当于模-2加法或二进制XOR运算，并且*运算相当于模-2乘法或布尔AND运算。GF(q)是在元素{0，1，…，q-1}上的域，其中q是素数。域GF(q^m)是GF(q)的扩展域，其中元素被定义为系数在GF(q)中的多项式。GF(2^m)是GF(2)的扩展域，其中元素是系数在GF(2)中的多项式。

当满足次数(degree)为m的多项式p(ξ)除尽ξⁿ+1的最小正整数n等于n＝2^m-1时多项式p(ξ)是本原多项式(primitive)。扩展域GF(2^m)可以被表示为多项式元素的域F，如下所述：

$\mathrm{GF}\left(2^m\right)=F=\{\mathrm{0,1},\alpha ,{\alpha }^2,···,{\alpha }^{2^m-2}\}$

其中α是除了1和0之外的第三符号；

p(α)＝0

${\alpha }^{2^m-1}=1;$且

${\alpha }^{2^m-1}+1=0$

对于在F中的运算*：

e_*＝1

${\left({\alpha }^i\right)}^{-1}={\alpha }^{2^m-i-1}$

对于在F中的运算+：

e₊＝0

-αⁱ＝αⁱ

除了将F中的元素表示为α的幂，F中的每个元素也可以被表示为具有二进制系数的多项式：

αⁱ＝a_i，0+a_i，1α+a_i，2α²+…+a_i，m-1α^m-1

F的元素的加法通过多项式加法来容易地实现，并且F的元素的乘法通过表示为α的幂的元素的指数相加来容易地实现。

对于扩展域，比如GF(2⁸)，可以针对GF(2⁸)中的每个元素来构造表，表中的每个条目示出元素的幂表示、元素的多项式表示和包括元素的多项式表示的系数的二进制值的元组。图11示出针对GF(2⁸)的元素的表的一部分。表1100的第一列1102示出GF(2⁸)的元素的幂表示，中间列1103提供了元素的多项式表示，以及最后一列1104示出每个元素的8-位二进制-系数-元组表示。可以针对乘法和加法运算构造附加表。因此，域GF(2⁸)可以被表示为256个元素的集合，每个元素是8-位元组，其中乘法、加法和减法运算由基于对底层多项式执行的运算的表来指定。重要的是，注意到针对GF(2⁸)的8-位元素的乘法、减法和加法运算不相当于电子计算机所支持的熟悉的二进制算术运算。作为一个示例，在二进制算术中：

00100000+10111000＝11011000

而在GF(2⁸)加法中：

α²＝00100000＝α²

α⁸＝10111000＝1+α²+α³+α⁴

α²+α⁸＝α¹⁹³＝1+α³+α⁴＝10011000

提供了GF(2⁸)的示例，因为在本发明的一个公开的实施例中，在GF(2⁸)上的复合码是根据在GF(2⁸)上的两个分量码构造的。码字中的每个符号可以被看作代表GF(2⁸)的元素的8-位元组。注意到，在GF(2⁸)中存在256个元素。因此，每个可能的8-位元组是GF(2⁸)的元素。一般地，为了编码和解码的目的，信息字节被认为是GF(2⁸)中的符号，但是在编码之前和解码之后，该信息字节被看作标准的二进制编码字节。在下面对本发明的讨论中，讨论了GF(2⁸)上的示例码，但是本发明的方法可以用于创建任意域GF(q)上的复合码。对于计算效率已经证明，对于符号表示方面的效率和计算操作方面的效率来说，在GF(2^m)上的复合码是所期望的。

本发明的实施例

本发明针对一族复合纠错码，所述复合纠错码是使用至少两个分量码和下面所描述的函数f(·)构造的，该函数将其上定义复合码的域的符号映射到该域的其他符号。在下面的讨论中，讨论来自代表本发明的实施例的该族复合码的一个特定复合码。所讨论的复合码是在扩展域GF(2⁸)的8-位符号上的码。然而，可以使用针对任意域的符号构造的分量码来类似地针对任意域GF(q)或GF(q^m)的符号来构造复合码。

图12示出代表本发明的一个实施例的复合码的基本特性。复合码是在GF(2⁸)上构造的并且产生长度为N＝72的码字，其中N是以8-位符号计长度。图12中示出了示范性码字1202。该码字包含K＝66个信息符号和R＝6个奇偶校验符号。码字之间的最小距离是D＝5个符号。复合码也可以被看作GF(2)上的码。图12中也示出GF(2)1210上的复合码的示范性码字。当被看作是GF(2)上的码时，每个码字具有n＝576位，其中k＝528位1212是信息位且r＝48位1214是奇偶校验位。码字之间的最小距离处于5≤d≤40的范围内，这依赖于用于构造该码的特定分量码的本性。具有特性N＝72、K＝66和D＝5的线性块码将预期能够检测并校正(D-1)/2＝2个符号差错或4个符号删除。然而，代表本发明的实施例的复合码可以校正更大数量的符号差错(在它们以突发发生时)、更大数量的删除和除了差错突发和删除之外的更大数量的符号差错和位差错。

代表本发明的实施例的复合码的编码和解码方法依赖于符号-到-符号的映射函数f(·)。图13示出本发明的实施例中所使用的符号-到-符号的映射函数f(·)的特性。在图13中，代表GF(2⁸)1302的256个元素的256个8-位符号的序列被部分示出。GF(2⁸)的第二到第九个符号被称为集合“M”1304，包括具有8-位元组表示的那些符号，每个符号仅仅包含单个位值为“1”的位。集合M中的这些8-位向量对应于图11中所示的GF(2⁸)表示中的GF(2⁸)元素{1，α¹，α²，…，α⁷}。将GF(2⁸)的符号映射到GF(2⁸)的其他符号的任何函数f(·)可被用于编码和解码代表本发明的实施例的复合码，只要该函数f(·)是线性的、具有严格的反函数f(·)^-1并且将集合M的任意一个符号映射到GF(2⁸)的不在集合M中的符号：

$f(u\in M)\to u^{\prime }\notin M$

$\exists f^{-1}\left(u\right):f^{-1}\left(f\left(u\right)\right)=u$

图14示出符号-到-符号映射函数f(·)的两种不同的实现方式。在一种实现方式中，f(u)可以被实现为符号的位向量表示u与mxm矩阵1402的乘法，其中m是其上构造所述码的二进制扩展域GF(2^m)的m，在当前情况下为8。在可替代实施例中，可以准备查找表1404以提供针对每个可能的符号u的f(u)的值。在GF(2⁸)符号的情况下，由位向量u表示的符号可以用作数值字节值以为该查找表编索引。

在可替代实施例中，映射函数f(·)可以是不同的函数。一般地，函数f(·)的目的是将某种类型的差错-字符号映射到可替代的符号值，以允许该类型的差错的发生将被分配给估计的C₂码字或分配给在解码期间从复合码码字提取的C₁码字。本发明的所有实施例使用非恒等映射函数f(·)。

如上所讨论的那样，函数f(·)可以应用于符号，或可以应用到符号的向量。例如，函数f(·)可以应用于整个码字u以产生修改的码字f(u)，其中符号函数f(·)应用于码字的每个符号以生成修改的码字的每个对应的符号。

图15A提供了根据本发明的一个实施例的用于将信息位编码成复合码字的高级控制流程图。在步骤1502中，K₁个信息符号被接收。在步骤1503中，通过第一分量码C₁编码器对K₁个信息符号进行编码以产生长度为N₁个符号的C₁码字u。在步骤1504中，通过第二分量码C₂编码器对K₂个信息符号进行编码以产生长度为N₂个符号的码字v。在步骤1505中，通过将u的非恒等映射f(u)加到v，获得长度为N₂个符号的向量w。最后，在步骤1506中，通过将u和v连接在一起来生成复合码C码字，该复合码C码字具有长度N＝N₁+N₂并且包含K＝K₁+K₂个信息符号。

图15B示出代表本发明的一个实施例的复合码C[72，66，5]的构造。如上所讨论，复合码依赖于两个分量码。分量码可以是Reed-Solomon码，GF(q)上定义的系统线性块码、二进制系统线性块码或其他类型的码。在所公开的实施例中，第一分量码C₁产生N₁＝36、K₁＝34和D₁＝3的码字并且第二分量C₂具有特性N₂＝36、K₂＝32和D₂＝5。假设，C₁能够检测和校正s1个符号删除和t1个符号差错，其中s1+2t1＜D₁，并且C₂能够检测和校正s2个符号删除和t2个符号差错，其中s2+2t2＜D₂。实际上，这样的码是众所周知的。

如图15B所示，C₁编码K₁＝34个信息符号1512以产生36-符号C₁码字u1516并且C₂编码K₂＝32个信息符号1514以产生36-符号C₂码字v1518。这些码字被组合以创建代表本发明的一个实施例的复合码C[72，66，5]的码字。因此，K₁+K₂＝32+34＝66个信息符号被编码为代表本发明的一个实施例的复合码的每个72-符号码字。C₁码字u和C₂码字v都具有N＝36个符号。函数f(·)被依次应用于u中的每个符号以产生向量f(u)1520。向量f(u)然后被加到C₂码字v1522以产生向量w＝f(u)+v1524。然后，码字u1516与w＝f(u)+v级联以产生代表本发明的一个实施例的复合码的N＝72的码字1526。当该码字的符号被传输或存储时，来自u和w的符号在传输的符号中交替，如在传输的符号的序列1528中所示，其中首先传输符号u₀1530、最后传输符号1532。图16示出编码复合码码字的方法，该方法能够对信息符号的输入流重复执行以产生复合码码字的输出流。在步骤1602中，K₁+K₂个信息符号被接收以用于编码。在步骤1604中，开头的K₁个信息符号通过C₁编码器编码以产生C₁码字u。在步骤1606中，接下来的K₂个信息符号通过C₂编码器来编码以产生C₂码字v。在步骤1608中，使用符号到符号映射函数f(·)从u和v生成向量w＝f(u)+v。最后，在步骤1610中，将u和w级联在一起以产生复合码码字。通过图16所示的方法对复合码码字的编码可以对信息符号的输入流重复执行以产生复合码码字的输出流。

计算向量w的上述方法生成非系统码C。系统码C可以通过预编码获得。预编码是通过从f(u)提取长度为K₂的前缀(prefix)，prefix((f(u))并且创建包含来自输入流的接下来K₂个信息符号的向量a来执行的。然后字v′被产生为：v′＝a-prefix(f(u))。最后，v′被用作被编码为C₂码字v″的K₂个信息符号，并且v″然后被用于通过：w＝f(u)+v″来计算向量w。

在本发明的可替代实施例中，复合码码字可以通过其他方法来产生。使用分量码编码的次序可以不同，分量码可以不同，并且可以使用不同的符号到符号映射函数。代表本发明的实施例的复合码族内的可替代的复合码可以具有不同的特性N、K和D，这依赖于分量码C₁和C₂的底层码特性。在本发明的可替代实施例中，每个分量码本身可以从两个或更多的底层(underlying)分量码生成。

图17A示出代表本发明的一个实施例的复合码的码字内的子块的概念。如图17所示，复合码码字1702可被视为包含8-位符号，比如符号1704，其可替代地被示出为扩展到8-位符号向量1706。每对符号，比如符号对1708-1709，可以一起被视为子块1710。因此，复合码码字可替代地可被视为位的有序序列、8-位符号的有序序列或视为子块的有序序列。

图17B示出代表本发明的一个实施例的复合码被设计以成检测并和校正的各种不同类型的差错。复合码的重要附加参数是参数L，其是小于D/2的最大整数。对于各种类型的可替代的复合码，值L可以固定在的整数范围内。第一类型的差错被称为“定相突发”差错。图17B中所示的第一字1712中示出了定相突发差错。定相突发差错是包括L个子块的相邻符号的块内的任意数量的被破坏的符号。如图17B中的字1712中所示，用剖面线示出的四个符号1714-1717被破坏，并且所有这四个符号落入包含子块4和5的块内。假设包含定相突发差错的码字不包括任何子块删除。在定相突发差错的情况下，当块内的所有四个符号都被破坏时，存在复合码可能不能够校正这些差错的小概率。然而，该小概率比具有等效冗余的Reed-Solomon码不能校正这些差错的概率更小，并且本发明的复合码比具有等效冗余的Reed-Solomon码更具有时间效率。当所述块内少于四个符号被破坏时，所有这些破坏的符号都能够被校正。

图17B中所示的第二码字1730中示出了tS差错类型。该tS差错类型包含高达L-t个子块删除和t个破坏的符号。在图17B所示的示例中，存在单个子块删除1722和单个附加的被破坏符号1724，从而t＝1且L-t＝1个删除的子块。可替代地，可以存在两个删除的子块且没有附加的被破坏的符号或有两个被破坏的符号且没有附加的删除的子块。本发明的复合码针对的第三类型的差错条件是1R差错，其中高达L个子块被删除并且一个附加的1-位差错已经发生。图17B中的第三码字1736示出1R差错，其中两个子块1738-1739被删除并且单个位差错1740发生在符号1742中。

开发代表本发明的实施例的复合码的一个动机是为了对新近开发类型的电子存储器进行差错校正。因为该存储器的构造，预期的大多数差错包括定相突发差错、tS-型差错和1R-型差错。差错校正在这些电子存储器系统中以硬件实现，并且因此差错校正组件代表显著的设计和制造开销。为此，设计者和制造者希望使用尽可能高效的码来检测和校正预期的定相突发、tS和1R差错。对于相等数量的信息符号，代表本发明的实施例的复合码使用比常规的Reed-Solomon码所需的奇偶校验符号更少的奇偶校验符号来成功检测并校正这些预期的差错类型。

图18提供用于对代表本发明的一个实施例的复合码进行解码的高级控制流程图。在步骤1802中，接收包含K个信息符号的长度为N的复合码-C码字。在步骤1804-1806中，包含K₁个信息符号的长度为N₁的分量码-C₁码字u和长度为N₂的修改的分量码-C₂码字w＝v+f(u)被从复合码-C码字提取并且通过将C₂解码器应用到修改的分量码-C₂码字而从修改的分量码-C₂码字生成估计的分量码-C₂码字和估计的差错字其中修改的分量码-C₂码字是在编码期间从包含K₂个信息符号的分量码-C₂码字v和非恒等映射函数f(·)生成的，其中K＝K₁+K₂且N＝N₁+N₂。在步骤1808中，根据差错字确定若干类型的预期差错中哪些在对复合码-C码字进行编码之后发生。当大于第一阈值数量的删除和删除已经发生，但是小于第二阈值数量的差错已经发生时，如步骤1816所确定的，所确定的差错被分配给分量码-C₁码字或分配给修改的分量码C₂-码字，并且当被分配给分量码-C₁码字时，在步骤1818和1820中被校正。在步骤1810、1812和1814中，注意其他差错和删除的发生。在步骤1822中，通过将C₁解码器应用到估计的分量码-C₁码字来获得估计的分量码-C₂码字最后，在步骤1824中，从估计的分量码-C₂码字提取K₁个信息符号，并且从估计的分量码-C₂码字提取K₂个信息符号以产生K个提取的信息符号。

接下来，讨论对接收的复合码码字进行解码。图19-20提供了示出对代表本发明的实施例的复合码进行解码的过程的一个实施例的控制流程图。首先，在步骤1902中，接收复合码C码字。所接收的字可被视为两部分：

[u_r|w_r]

其中u_r是接收到的u，或u+e₁

w_r是接收到的w，或f(u)+v+e₂

接下来，在步骤1903中，在编码期间f(u)与v或v″的相加通过下式被反转(reverse)：

v_r＝-f(u_r)+w_r

接下来，在步骤1904中，使用C₂解码器解码所计算的字v_r以产生估计的码字和估计的差错字

其中$\hat{e}=-f\left(e_1\right)+e_2$

其中类似函数的符号表示由用于分量码C₂的解码器所进行的解码。

如果v_r的C₂解码失败，如步骤1905中所确定的，则复合码码字的解码失败。接下来，在一系列条件步骤中，表示定相突发(″PB″)、tS和1R差错的布尔标志被设置以指示这些类型的差错是否看来似乎已经在所接收的字内发生。注意到，标记“_1R”在下面被用于1R标志，以与稍后讨论的伪代码一致。应当注意，删除的子块的存在一般由不是所接收的字的一部分的分离的、带外删除指示来表示。当没有发生删除时并且当所有符号差错已经在与块边界对齐(line with)的L个相邻子块内发生时，如在步骤1906中确定的且如以上参照图17B所讨论的，则标志PB在步骤1908中被设置为TRUE(真)。否则，在步骤1910中，标志PB被设置为FALSE(假)。当标志PB包含值FALSE时且当删除的子块的数量和估计的差错向量中任何附加的非零符号的数量相加的值小于或等于L时，如在步骤1912中所确定的，则标志tS在步骤1914中被设置为TRUE。否则标志tS在步骤1916中被设置为FALSE。当PB和tS二者都包含布尔值FALSE，并且当删除的子块的数量小于或等于L并且至多只有一个附加的1-位符号差错已经在差错向量中被发现时，如在步骤1917B中所确定的，则标志_1R在步骤1919中被设置为TRUE。否则标志_1R在步骤1920中被设置为FALSE。当估计的差错向量中的非零符号s是集合M的元素或-s被符号到符号函数f^-1()映射到集合M时，可替代地表示为：

s∈M或f^-1(-s)∈M

检测到1-位差错。因此，f(·)将u_r中发生的单个位差错映射到具有超过两个位值为“1”的位的符号，使得u_r中的单个位差错可以与v_r中的单个位差错区分开。编码在图20的流程控制图中继续。如果这三个布尔标志PB、tS和_1R都未被设置为TRUE，如步骤2002中所确定的，则在步骤2004中解码器返回FALSE值。否则，在步骤2006中向量u′被设置为所接收的C码字u_r的前一半。如果标志_1R被设置为TRUE，如步骤2008中所确定的，则如果单个非零符号s_γ在估计的差错向量中在位置γ处被找到并且s_γ不是集合M的元素，如在步骤2010中所确定的，则u′中在相同位置γ处的符号被原始符号取代，在步骤2012中通过GF(2⁸)减法从原始符号减去逆映射的负差错符号。步骤2008、2010和2012允许对除了L个子块删除之外的单个位差错进行检测。当非零符号s_γ是M的元素时，则在所接收的字的后一半中(或换言之在v_r中)发生单个位差错。然而，当s_γ可以通过F^-1(-s_γ)而被映射到M时，在C码字的第一部分中发生单个位差错。在这种情况下，在步骤2012中校正该差错。接下来，如果布尔标志PB包含值TRUE，如步骤2014中所确定的，并且如果在中存在非零符号，如在步骤2016中所确定的，则在步骤2018中包含差错的块中的符号被标记为删除。如果标志tS包含布尔值TRUE，如步骤2020所确定的，并且如果在任何检测到的删除之外在中存在任何非零符号，如步骤2022中所确定的，则在步骤2024中那些附加符号差错被标记为删除。在步骤2026中，C₁解码器被应用于u′以产生估计的原始向量如果C₁解码器失败，如步骤2027中所确定的，则复合码解码失败。否则在步骤2028中，从中提取K₁个符号并且从中提取K₂个符号，它们一起形成在步骤2030中返回的K个解码信息符号的序列。如在步骤1904的情况下那样，如果在步骤2026中C₁解码器失败，则解码失败。

接下来，提供用于解码上述代表本发明一个实施例的复合码的解码方法的类C++伪代码实现方式。图21示出用于代表本发明的一个实施例的复合码的解码方法的每个步骤所接收的信息。所接收的信息包括删除图2102，其中码字中每个符号各有单个位来指示该符号是否已被删除。所接收的信息包括：删除图2102，其包括针对所接收的字的每个符号的指示该符号是否已经被删除的位标志；和所接收的字2104，其如上所讨论的包括：第一部分2106u_r，其等于u+e₁，不过u和e₁是未知的；和第二部分2108v_r，其等于F(u)+v+e₂，不过u、v和e₂是未知的。

所述伪代码实现方式首先包括许多常整数的声明：

1const int C1K＝34；

2const int C2K＝32；

3const int CK＝C1K+C2K；

4const int C1R＝2；

5const int C2R＝4；

6const int CR＝C1R+C2R；

7const int C1D＝3；

7const int C2D＝5；

8const int CD＝2*C1D＞C2D？C2D:2*C1D；

9const int N＝CR+CK；

10const int L＝floor((CD-1)/2)；

11const int symPSubBlk＝2；

12const int Nsub＝N/symPSubBlk；

13const int N2＝N/2；

14const int blkPlus＝N2/symPSubBlk；

15const int b ＝8；

这些常数包括用于上面所讨论的复合码C和分量码C1和C2的基本参数，包括：(1)C1K、C2K和CK，分别为C1、C2和C的码字中信息符号的数量；(2)C1R、C2R和CR，分别为C1、C2和C的码字中奇偶校验符号的数量；(3)分别针对C1、C2和C的码字的码字之间的最小距离C1D、C2D和CD；(4)常数N，其为复合码C的码字中符号的数量；(5)数量L，如上所讨论地在公开的实现方式中等于比(CD-1)/2小的最大整数；(6)N2，分量码C1和C2的码字中符号的数量，其中N2＝N/2；symPSubBlk，每子块的符号的数量；(7)blkPlus，其在被加到复合码字的第一部分中的块的子块索引时生成复合码字的第二部分的对应子块的子块索引；以及(8)常数b，符号中位的数量或等价地为等于在其上构造复合码C的域的表达式GF(2^m)中的m的数字。

接下来，为(1)码字符号；(2)C、C1和C2码字；和(3)C、C1和C2码字的删除图而提供类型定义；

1typedef unsigned char symbol；//仅b＜＝8

2typedet symbol C_WORD[N]；

3typedef symbol C1_WORD[N2]；

4typedef symbol C2_WORD[N2]；

5typedef bool C_ERASURE_WORD[N]；

6typedef bool C1_ERASURE_WORD[N2]；

7typedef bool C2_ERASURE_WORD[N2]；

应当注意，仅当常数b小于或等于8时，C++类型″unsigned char″才能用于表示符号。当b＝8时，unsigned-char数据类型(也被称为“字节”)恰好是表示表达为二进制系数的元组的每个符号所需的大小，并且因此对于计算效率而言，GF(2⁸)是其上构造码的最便利的域。

接下来，提供针对集合M的声明，该集合包括具有仅仅包含单个位值为“1”的位的8-位-元组表示的所有符号。该声明使用了这样的事实：集合M中的元组对应于字节，在正常的二进制字节-值表示中对应于2的幂：

1const symbol M[b]＝{1，2，4，8，16，32，64，128}；//具有单个位元组表

                                           //示的GF(2^b)的元素

接下来，提供针对五个函数的声明：

1bool C1(C1_WORD c1Word，C1_ERASURE_WORD erasures，

2        C1_WORD decodedC1Word，C1_WORD errors)；

3bool C2(C2_WORD c2Word，C2_ERASURE_WORD erasures，

4        C2_WORD decodedC2Word，C2_WORD errors)；

5symbol f(symbol a)；

6symbol flnverse(symbol a)；

7symbol GF2bSubtraction(symbol y，symbol z)；

前两个函数是用于分量码C1和C2的解码器。这两个函数接收码字和删除图并返回解码的码字和差错字，如上所述。上面讨论的函数f(·)和函数f^-1(·)在上面的代码块的第5行和第6行声明。最后，在第7行，提供了用于从GF(2⁸)符号y减去GF(2⁸)符号z的GF(2⁸)减法函数。如上所讨论的，假设分量码C1和C2存在，并且编码器和解码器可用于这些分量码。没有提供针对上述五个函数的实现方式，这是因为解码器的实现方式依赖于被选择用于构造复合码的特定分量码，因为函数f(·)和f^-1(·)被直接实现(该实现方式依赖于其上定义复合码的域)、以及因为GF(2^b)减法是众所周知的。

接下来，提供多个类声明。首先，提供表示输入符号流、输入删除流和输出符号流的三个类：

1class symbolStream

2{

3    public:

4           bool start()；

5           bool getNext(int num，symbol*buffer)；

6}；

1class erasureStream

2{

3    public:

4           bool start()；

5           bool getNext(int num，bool*buffer)；

6}；

1class outputStream

2{

3    public:

4           bool start()；

5           void outputNext(int num，symbol*buffer)；

6           void finish()；

7}；

各种流可被启动并且然后被访问以便输入或输出指定数量的符号。没有提供针对这些类的实现方式，因为流输入和输出二者都是众所周知的、操作系统相关的且可能是硬件平台相关的。

接下来，提供类“C-decoder”的类声明：

1class C_decoder

2{

3    private:

4            symbolStream s；

5            erasureStream Er；

6            outputStream out；

7

8            void deInterleave(C_WORD c，C_ERASURE_WORD er)；

9            bool decodeNextBlock(C_WORD c，C_ERASURE_WORD er，

10                                symbol*buffer)；

11

12    public:

13           bool decode()；

14}；

类“C_decoder”包括三个私有数据成员s、Er和out，它们分别代表符号流、删除流和输出流类的实例(instance)。类“C_decoder”包括两个在第8-10行声明的私有函数成员。第一私有函数成员“deInterleave”通过对交织的符号解交织而将从输入流中接收的n个符号转换为C码字，如参照图15(特别是图15中的1518)所讨论的。私有函数成员“decodeNextBlock”接收C码字和对应的删除图并且输出K个解码的信息符号到输出流。第13行声明的单个公有函数成员“decode”连续地对来自输入流的符号进行解码并输出对应的解码的信息符号到输出流。

接下来提供了函数成员“decode”的实现方式：

1bool C_decoder::decode()

2{

3    s.start()；

4    Er.start()；

5    out.start()；

6    C_WORD c；

7    C_ERASURE_WORD er；

8    symbol buffer[CK]；

9

10   while(s.getNext(N，c)&&Er.getNext(N，er))

11   {

12          deInterleave(c，er)；

13          if(！decodeNextBlock(c，er，buffer))return false；

14          out.outputNext(CK，buffer)；

15   }

16   return(true)；

17}；

在第10-15行的while循环中，函数成员“decode”从输入流c和Er提取下一个码字和对应的删除图、在第12行对输入符号进行解交织、在第13行对码字进行解码以及在第14行输出对应的解码的信息符号。该循环持续进行直到第13行的解码失败为止或直到如第10行确定的没有来自信息流的可用的附加编码符号为止。

接下来，提供函数成员“decodeNextBlock”的实现方式：

1bool C_decoder::decodeNextBlock(C_WORD c，C_ERASURE_WORD er，

2                            symbol*buffer)

3{

4   symbol*ur＝&(c[0])；

5   symbol*wr＝&(c[N2])；

6

7   bool*er1＝&(er[0])；

8   bool*er2＝&(er[N2])；

9

10  C1_WORD uHat，uPrime，e1Hat；

11  C2_WORD vHat，vr，e2Hat；

12

13  bool PB，tS，_1R，erased；

14

15  symbol gamma；

16

17  int i，j，blkIndex，gammaIndex；

18  int erasures[L]；

19  int numErasures＝0；

20  int nonZeroSymbols[L]；

21  int numNonZeroSymbols＝0；

22

23  for(i＝0；i＜N2；i++)

24         vr[i]＝-f(ur[i])+wr[i]；//vr＝v+-f(e1)+e2

25

26  if(！C2(vr，er2，vHat，e2Hat))return false；

27

28  for(i＝0；i＜N；i++)

29  {

30         if(er[i])

31         {

32               blkIndex＝(i/symPSubBlk)*symPSubBlk；

33               if((i！＝blkIndex)&&er[blkIndex])continue；

34               if(numErasures＝＝L)return false；

35               else erasures[numErasures++]＝blkIndex；

36         }

37   }

38

39   for(i＝0；i＜N2；i++)

40   {

41    erased＝false；

42    blkIndex＝(i/symPSubBlk)*symPSubBlk；

43    for(j＝0；j＜numErasures；j++)

44    {

45      if(erasures[j]＝＝blkIndex‖erasures[j]＝＝blkIndex+blkPlus)

46           erased＝true；break；

47    }

48    if(erased)

49           i＝((blkIndex+1)*symPSubBlk)-1；

50    else

51           {

52               if(e2Hat[i]！＝0)

53               {

54                    if(numNonZeroSymbols＝＝L)return false；

55                    else nonZeroSymbols[numNonZeroSymbols++]＝i；

56               }

57           }

58   }

59

60   if(numErasures＝＝0)

61   {

62      if(numNonZeroSymbols＝＝0)PB＝true；

63           else if(nonZeroSymbols[numNonZeroSymbols-1]-

64                    nonZeroSymbols[0]＜＝L)

65              PB＝true；

66           else PB＝false；

67   }

68

69   if(！PB && numNonZeroSymbols+numErasures＜L)tS＝true；

70   else tS＝false；

71

72   if(！PB &&！tS && numNonZeroSymbols＝＝1)

73   {

74           gammaIndex＝nonZeroSymbols[0]；

75           gamma＝0；

76           if(e2Hat[gammaIndex]＝＝0)_1R＝true；

77           else

78           {

79                 _1R＝false；

80                 for(i＝0；i＜b；i++)

81                 {

82                      if((e2Hat[gammaIndex]＝＝M[i]))

83                    {

84                          _1R＝true；

85                          break；

86                    }

87                    gamma＝flnverse(-e2Hat[gammaIndex])；

88                    if(gamma＝M[i])

89                    {

90                           _1R＝true；

91                           break；

92                     }

93                     gamma＝0；

94               }

95         }

96   }

97

98   if(！PB &&！tS &&！_1R)return false；

99

100  for(i＝0；i＜N2；i++)uPrime[i]＝ur[i]；

101

102  if(PB)

103        for(i＝0；i＜numErasures；i++)

104               for(j＝0；j＜symPSubBlk；j++)

105                      er1[i+j]＝true；

106

107  if(tS)

108        for(i＝0；i＜numNonZeroSymbols；i++)

109               er1[nonZeroSymbols[i]]＝true；

110

111  uPrime[i]＝GF2bSubtraction(uPrime[i]，gamma)；

112

113  if(！C1(uPrime，er1，uHat，e1Hat))return false；

114

115  for(i＝0；i＜C1K；i++)*buffer++＝uPrime[i]；

116  for(i＝0；i＜C2K；i++)*buffer++＝vHat[i]；

117  return true；

118}

函数成员“decodeNextBlock”接收复合码码字c、对应的删除图er和其中放置对应于接收字c的解码的信息符号的符号缓冲器。在第4-5行，符号指针ur和wr被声明为指向所接收的字C的前一半和后一半。这些符号指针ur和wr对应于图21中的u_r和w_r。相似地，在第7-8行，删除-映射指针er1和er2被声明为分别指向所接收的删除字er的对应于所接收的字C的前一半和后一半的部分。

在第10-21行，声明了多个局部变量。这些局部变量具有对应于上述讨论复合码、分量码、复合码编码和复合码解码中使用的标记的名称。例如，在第11行声明的变量vHat代表上面讨论的估计的解码的码字分别在第18和20行声明的数组“erasures”和“nonZerosymbols”分别包括在删除图和估计的差错向量e2Hat中检测到的附加差错的索引和删除的子块的索引。这些局部变量的使用是通过下面描述的它们在函数成员“decodeNextBlock”中的使用来阐明的。

在第23-24行，向量“vr”被计算为vr＝wr-f(ur)。在第26行，vr被解码以产生和其在所述码中分别被称为“vHat”和“e2Hat”。在第28-37行的for循环中，所有删除的子块的索引被确定并存储在数组“erasures”中。注意到，如果子块删除的数量大于L，则解码例程(routine)失败，因为只限L个删除能够通过以伪代码实现的复合码来检测和校正。还注意到，如果第26行调用的C2解码器失败，则解码失败。接下来，在第39-58行的for循环中，除了任何检测到的删除的子块之外，记录了(note)由非零符号表示的中的任何差错，并且对应于这些差错的非零符号的索引被存储在数组“nonZerosymbols”中。

在第60-67行，布尔标志PB被设置为TRUE或FALSE，这依赖于在码字中是否检测到定相突发差错。当不存在删除时并且当不存在附加的差错符号或所有的差错符号发生在由L个相邻子块组成的单个块内时，PB被设置为TRUE。回想起(recall)，如果存在超过L个的删除子块，则函数成员“decodeNextBlock”将已经失败。接下来，在第69-70行，布尔标志tS被设置为TRUE或FALSE，这依赖于在接收的字中是否检测到tS-型差错。当PB为FALSE并且加到附加的差错符号的数量的删除子块的数量产生小于或等于L的和时，标志tS被设置为TRUE。

接下来，在第72-96行，布尔标志_1R被设置为TRUE或FALSE。当存在单个附加的1-位差错或没有附加差错，并且存在多达L个删除的子块时，布尔标志_1R被设置为TRUE。注意到，在第34行，如果检测到超过L个删除的子块，则解码已经失败。当差错符号是集合M的成员时，如第81行所确定的，或由f^-1(·)进行的差错符号的符号值的GF(2^b)-加性逆元的逆映射映射到M时，如第88行所确定的，则差错符号代表1-位差错。

当所有布尔标志为FALSE时，如第98行上所确定的，则解码失败。否则，在第100行上uPrime被设置为所接收的字c的第一部分。当PB为TRUE时，在第102-105行上所有包含差错的子块的所有符号被标记为删除。当tS为TRUE时，则在第107-109行上所有附加的差错符号被标记为删除。当在第88行接着在第109行在码字的第一部分中检测到1-位附加差错时，则在第111行上通过从uPrime减去逆映射逆符号值来改变uPrime以从而校正所述区域。最后，在第113行上，通过C1解码器对uPrime进行解码。如果C1解码器失败，则解码失败。否则，uPrime和vHat中的信息符号被放置在缓冲器中以返回到成员函数“decode”。

如上所述，代表本发明的实施例的复合码可被构造为有高效地检测和校正特定类型的差错和删除模式及发生。例如，假设期望检测并校正符号中多达L个删除的子块和t个附加的随机单个位差错。在上面讨论的复合码的情况下，当L＜D1且L+2t＜D2时，并且当GF(2)上的线性码C′存在且C′N等于2*b，维数度K′＝b且最小码字距离D′≥2*t+1时，其中C′C由奇偶校验矩阵H′＝[I_b|-A]定义，并且其中-A是可逆的，则在上面讨论的复合码的情况下，上面描述的复合码可以用于检测多达L＝2个删除的子块和t＝2个附加的随机单个位差错。注意到，-A是GF(2)上的bxb矩阵。在这种情况下，符号到符号映射函数f(·)被定义为：f(·)＝u_i·A^T，其中在上面讨论的复合码的情况下，u_i是GF(2⁸)的符号。条件“L＜D1且L+2t＜D2”确保了C2解码器能够成功地解码。与线性码C′相关的条件确保了f(·)将成功地把具有一个或两个随机位差错的符号u_i映射到与一个-或-两个-随机-位-差错破坏的符号可区别的不同符号，从而使得复合码解码器能够确定码字的两半中哪一半发生了一个-或-两个-随机-位破坏。在当前的情况下，C2差错字中的非零符号可以用于生成C′的校正子并且校正子s然后可以用于选择包含和的级联的对应的C′差错字e′。因此，中的随机两位差错破坏的符号可以归因于复合码码字的前一半或后一半。

图22示出本发明的实施例可以应用于其中的物理存储设备的框图。存储器2202包括一组单独的DRAM组件存储器2204-2208、用于接收和传送数据的总线控制器和逻辑2210、用于在存储在存储器之前将复合码应用到数据值的编码器2212和用于对从存储器检索的编码值进行解码的解码器2214。存储器操作包括将通过地址和大小(以字计)2218所标识的数据字的块2216存储到存储器中，以及从该存储器中检索通过地址和大小(以字计)2222所标识的字块2220。

图23示出在码字符号与共同构成图22所示的物理存储设备的电子数据存储组件的DRAM单元组中的DRAM单元之间的映射。在一个实施例中，通过存储器中的编码器组件(图22中的2212)将接收的用于存储在存储器中的每个字编码为复合码码字2303，其可被视为块(比如块2304)的阵列，每个块包括若干子块，比如子块2306。每个块被映射到对应的DRAM中，如由图23中的双头箭头2308-2313所示。因此，例如，DRAM故障将导致跨越码字块的定相突发差错。本发明的复合码被设计成校正存储器的最可能的故障模式。例如，上面讨论的复合码可以校正单个DRAM故障、数个DRAM中的数个子块和符号故障。通过使用复合码，存储器差错的概率(由于存储器组件差错的低概率而已经相当低)通过对任何最可能的组件差错进行校正而显著降低。

尽管已经依照特定实施例描述了本发明，但是本发明并不打算限于这些实施例。在本发明的精神内的修改对于本领域技术人员来说将是显而易见的。例如，如上所讨论的，任意数量的不同分量码可以被组合以创建复合码，只要合适的符号到符号映射函数f(·)可以被找到以将某些差错映射到经过分量码编码的对应符号。用于复合码的编码和解码方法可以以软件、固件、硬件或软件、固件和硬件中两种或更多种的组合来实现。软件实现方式可以使用多种不同的编程语言、模块组织、控制结构、数据结构中任意一种，并且可以通过许多其他这样的编程参数中任意一种而改变。本发明的复合码可以设计用于高效检测和校正许多不同类型的差错和删除模式及发生。在本发明的可替代实施例中，不同的符号到符号映射函数可以用于确定复合码码字中某些类型的差错的位置。在本发明的又一些可替代实施例中，映射函数f(·)可以将符号对映射到其他符号对或者可以将码字的其他部分映射到不同的值。

为了解释的目的，前面的描述使用特定的术语来提供对本发明的全面理解。然而，本领域技术人员应该清楚，为了实践本发明，特定的细节是不需要的。本发明的特定实施例的前述描述是为了说明和描述的目的而给出的。它们的意图不是详尽说明或将本发明限制于公开的确切形式。鉴于上述教导，许多修改和变形是可能的。所述实施例被示出和描述，以便最佳地解释本发明的原理和其实际应用，以便由此使得本领域其他技术人员能够最佳地利用本发明和带有如适合于预期的特定用途的各种修改的各种实施例。本发明的范围意欲由下面的权利要求及其等效物定义。