CN101142746B

CN101142746B - 纠错码

Info

Publication number: CN101142746B
Application number: CN200680002430.0A
Authority: CN
Inventors: 塞巴斯蒂安·安吉尔
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2005-01-18
Filing date: 2006-01-12
Publication date: 2011-07-20
Anticipated expiration: 2026-01-12
Also published as: JP2008527890A; EP1681770A1; WO2006077503A1; US20080282132A1; US7945843B2; EP1842290A1; CN101142746A

Abstract

保护码字u免受至少一个q-ary符号的错误影响的系统，其中，q＝2^r，r≥1；码字u包括信息符号u[0]，...，u[k-1]，k＞1，每个信息符号表示范围{0，...，2^w-1}内的整数，w＝n*r，n≥1；处理器包括整数处理器单元，在程序控制下计算奇偶校验符号u[k]，校验符号包括-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod M，M≥2n(k+1)(q-1)+1，乘法·和加法+是整数运算；在{0，...，M-1}中，选择常数a[0]，...，a[k-1]以使元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说是唯一的，-q＜d＜q，d≠0。

Description

纠错码

技术领域

本发明涉及纠错码，更具体地，涉及一种生成纠错码的方法、一种使用纠错码计算奇偶校验符号的方法、以及一种使用纠错码对所接收矢量中的错误进行校正的方法。本发明还涉及一种用于执行所述方法的软件和一种使用所述方法的系统。

背景技术

众所周知，纠错码用于存储或传输系统中，以能够对字的存储/读取或传输期间可能已发生的至少一个错误进行检测和校正。字(信息符号)典型包括多个比特，例如32比特。一个或多个符号组合在一起成为码字。纠错码生成通常称作奇偶校验符号的附加信息。然后，存储/传输整个码字(信息符号和奇偶校验符号)。高级纠错码基于有限域中的计算，如Galois域(例如，GF(2ⁿ))。熟知的纠错码是里德-所罗门码(Reed-Solomon code)。典型地，在存储/传输之前计算该码，并在读取/接收之后使用用于执行特定有限域计算的定制设计的硬件检查该码。在许多应用中，可以使用微控制器或数字信号处理器，然而这些处理器通常具有针对这种运算的硬件支持。实质上，如何使用传统处理器的其它运算来执行有限域计算是公知的，通常是通过表查找方法。由于使用整数运算执行传统有限域计算需要太多处理周期、因而很慢，所以对于大多数应用来说，这是不实际的。对于低成本应用，附加的专用软件的成本会成为问题。

发明内容

本发明的目的是提供一种纠错码，该纠错码可在整数处理单元上执行，并且能够对码字中的至少一个q-ary符号进行校正，其中，q是2的r次幂，r≥1，(q＝2^r)。具体地，本发明目的是要能够对4级存储单元(例如，通常用于NAND存储器中的存储单元)的4-ary符号(q＝2²)中的错误进行校正。

为了实现本发明的目的，提供了一种用于生成对至少一个q-ary符号进行校正的纠错码的方法，其中，q是2的r次幂，r≥1，(q＝2^r)；所述方法包括：

-将包括k个信息符号u[0]，...，u[k-1]，k>1和用于保护信息符号的奇偶校验符号u[k]的码字u用作纠错码(例如，u＝(u[0]，...，u[k-1]，u[k]))；每个信息符号表示范围{0，...，2^w-1}内的整数，其中，w＝n*r，n≥1；

-将项-(α[0]·u[0]+α[1]·u[1]+...+α[k-1]·u[k-1])mod M包括在奇偶校验符号u[k]中，其中，M≥2n(k+1)(q-1)+1，乘法·和加法+是可由整数处理单元执行的整数运算，以及α[0]，...，α[k-1]是{0，...，M-1}中的常数；以及

-选择常数α[0]，...，α[k-1]，以使元素α[i]·d·q^jmod M对于i∈{0，...，k-1}和j∈{0，...，n-1}来说是唯一的，-q<d<q，d≠0。

为了实现本发明的目的，提供了一种用于保护码字u免受至少一个q-ary符号中的错误的系统，其中，q是2的r次幂，r≥1，(q＝2^r)；所述系统包括：

-用于接收包括k个信息符号u[0]，...，u[k-1]的码字u的装置，k>1，每个信息符号表示范围{0，...，2^w-1}范围内的整数，其中，w＝n*r，n≥1；

-处理器，包括整数处理器单元，用于在程序的控制下计算用于保护信息符号的奇偶校验符号u[k]，其中，奇偶校验符号包括-(α[0]·u[0]+α[1]·u[1]+...+α[k-1]·u[k-1])mod M，M≥2n(k+1)(q-1)+1，乘法·和加法+是整数运算，以及α[0]，...，α[k-1]是在{0，...，M-1}中选择的、以使元素α[i]·d·q^jmod M对于i∈{0，...，k-1}和j∈{0，...，n-1}来说是唯一的常数，-q<d<q，d≠0；以及

-用于在传输或存储所述码字之前将奇偶校验符号u[k]添加至码字u的装置。

所述码可以对一个或多个q-ary符号错误进行校正，并且只使用整数运算(加法、乘法和求模)。这样，可以在传统的整数硬件上容易地执行所述码。仅需要几个周期，从而所述码比较快速。

应当注意，由与所述关系相似的线性同余方程定义的码称为文献R.R.Varshamov：“A class of codes for asymmetric channels and a problemfrom the additive theory of numbers”.IEEE Transaction on informationTheory，Vol.IT-19，No.1，1973年1月中描述的Varshamov-Tenengolts码(1965)。对于该码的不对称错误(例如，可以将“0”映射至“1”，反之却不行)校正能力进行了研究。还应注意，Levenshtein观察到，这些码还具有对插入和删除进行校正的特性。然而，由于这些码较差的距离特性，还未考虑将它们用于对q-ary符号错误进行校正。由于信息符号可以超出由模M(2^w≥M)指定的范围，所以权利要求中要求保护的码进一步偏离上述传统码。

根据从属权利要求2的方法，形成表，以便对于所接收矢量中q-ary符号中的每个单个错误，能够检索到指示哪个q-ary符号出错、以及如何对它进行校正的信息。使用这种表，可以进行快速执行。该表可以存储于低成本存储器(如ROM)中。

如从属权利要求3的方法所限定的，优选地，模M选择为允许范围内的最大质数。这简化了适当常数的选择。

如从属权利要求4的方法所限定的，可以通过迭代地选择并测试随机选择的值，来发现适当常数。

如从属权利要求5的方法所限定的，尽量选择满足要求的小常数。使用小常数(例如，8比特值)提高了在简单处理器上的处理速度。

附图说明

从以下所描述的实施例中，本发明的这些和其它方面将变得显而易见，并且将参照以下所描述的实施例对本发明的这些和其它方面进行说明。

在附图中：

图1示出了根据本发明实施例的结构框图；

图2示出了根据本发明的处理步骤；以及

图3提供了数据结构的更多细节。

具体实施方式

图1示出了根据本发明的系统100的实施例结构框图。在本实施例中，所述系统包括用于执行纠错码的核心计算(即，在传输/存储码字之前计算奇偶校验符号以及/或者计算用于确定所接收/所读取码字中的错误的校正子)的处理器130。根据本发明的方法和系统设计为可以在传统的整数处理CPU内核上执行这些核心运算。在图1中，将这种内核示为I-proc 140。系统还包括I/O装置120，用于输出码字(包括奇偶校正符号)和/或接收包括可能受到一个或多个错误干扰的这种码字的矢量。典型地，在例如通过类似于局域网或广域网之类的通信系统传输码字时，或者在将码字存储在存储器(memory/storage)中时，使用错误校正。在传输期间或在读和/或写操作期间，码字的一个或多个比特可能会出错。纠错码有助于检测错误的发生，并有助于对一个或多个错误进行校正。常规上，I/O装置120本身依赖于传输或存储器(memory/storage)的类型。

根据本发明的系统设计用于对至少一个q-ary符号进行校正，其中，q是2的r次幂，r≥1，(q＝2^r)。在优选实施例中，系统包括存储器110。优选地，存储器是NAND类型的，其中，使用四个相异等级(q＝4，r＝2)存储信息。因此，一个存储单元存储两个比特的信息。因而该单元中的缺陷或错误可能对存储于这个单元中的整个信息(即，整个q-ary符号)有影响。

在以下部分，将结合示例，以通用术语对纠错码的原理进行描述。

图2示出了根据本发明的处理步骤。在步骤210中，接收到需要保护的码字u。例如，处理器130可以在执行程序期间计算这种码字，或者可以从源(未示出)接收这种码字。图3示出了码字u300包括k个信息符号u[0]，...，u[k-1]，k≥1。以数字310来指示信息符号。每个信息符号表示范围{0，...，2^w-1}内的整数，其中，w＝n*r，n≥1。在图3示出的示例中，码字u300包括每32比特信息(因此，w＝32)中的16个信息符号u[0]，...，u[15](因此，k＝16)。将以索引i∈{0，...，k-1}来指示码字u300中的信息符号。在示例中，给定q＝4及r＝2，4-ary符号存储在一个存储单元中。因此，每个信息符号包括w/r＝32/2＝16个q-ary符号。对于一个信息符号，在图3中使用数字315来指示十六个q-ary符号。以索引j来指示信息符号u[i]内的q-ary符号。

在步骤220中，计算单个奇偶校验符号u[k]以保护信息符号。图3示出了使用数字312指示的奇偶校验符号。根据本发明，奇偶校验符号u[k]包括如下项：

-(α[0]·u[0]+α[1]·u[1]+...+α[k-1]·u[k-1])mod M，

其中，乘法·和加法+是可由整数处理单元(如图1的单元140)执行的整数运算。例如，

u[k]＝-(α[0]·u[0]+α[1]·u[1]+...+α[k-1]·u[k-1])mod M (1)

因此，所述方法通过添加单个奇偶校验符号而保护了k个信息符号u[0]，...，u[k-1]。因子α[0]，...，α[k-1]是{0，...，M-1}中的常数，以及M≥1。以如下所述的适合方式来选择该常数。如本领域技术人员的能力范围内将会理解的一样，针对奇偶校验符号使用项(α[0]·u[0]+α[1]·u[1]+...+α[k-1]·u[k-1])mod M便是完全等效的，只要以类似方式改变用于检查/校正码字的校正子。

图3中的步骤320示出了将奇偶校验符号312添加至信息符号。在这里所描述的示例中，假设奇偶校验符号是追加的并因而形成所编写的码字的最末符号。同样，这并不重要，本领域技术人员可以容易地将奇偶校验符号插入另一位置，或者使用其它适合的方式将奇偶校验符号的信息添加至信息符号，并以类似方式改变检查/校正码字的校正子。

在图2的步骤230和图3的步骤330中，向‘传输信道’发出组合码字。如上所述，这可以同样良好地用于至通信系统的实际传输或在存储器中的存储/检索。这完成了保护信息的步骤，即，‘发送方’的角色。

图2B和图3中的剩余部分示出了‘接收方’中的处理，即，用于检测和校正传输信道中可能发生的错误的步骤。所接收的码字将称为矢量x。假设传输信道将错误矢量e添加至所传输的码字u。将会理解，如果没有错误发生，则e为仅具有0分量的空矢量。因此，将所传输的码字u接收为矢量

x＝u+e＝(u[0]+e[0]，...，u[k-1]+e[k-1]，u[k]+e[k])，

其中，“+”表示真正的整数加法，元素e[i]是整数(正、负或零)。x的接收如在图2B的步骤250所示，在图3中块330和340之间的箭头旁边。在接下来的步骤(图2中的步骤260，图3中的步骤340)中，计算所接收矢量的校正子。将校正子定义为：

s(x)＝(α[0]·x[0]+α[1]·x[1]+...+α[k-1]·x[k-1]+x[k])mod M由于s(-)是在整数上是线性的，以及对于由(1)给出的任何码字，s(u)＝0，所以可得：

s(x)＝s(u)+s(e)＝s(e)＝(a[0]e[0]+...+a[k-1]e[k-1]+e[k])mod M。

因此，所接收矢量x的校正子s(x)并不依赖于信息；它仅依赖于加性错误矢量e。

根据本发明的方法和系统特别适合会引入q-ary符号错误的信道，如NAND闪存。考虑q-ary符号中确切的一个受到了信道修改的情况。则在{0..k}中确切地存在一个i，对于这个i，e[i]≠0。此外，确切地存在一个j，使x[i]的第j个q-ary数字与u[i]的第j个q-ary数字不同。由于该数字在{0，...，q-1}中，所以数字之差d是-q<d<q，d≠0(差为零表示没有错误)。这意味着e[i]的可能值位于{d·q^j|-q<d<q，d≠0}中。这示出了任何单个q-ary符号错误均产生以下形式的校正子：

s(e)＝α[i]·d·q^jmod M，i∈{0，...，k}，-q<d<q，d≠0 (2)

因此，如果所有这些校正子的所有元素均两两相异，则可以对错误进行解码。因而选择常数α[0]，...，α[k-1]，以使对于i∈{0，...，k}和j∈{0，...，n-1}，元素a[i]·d·q^jmod M两两相异，其中，-q<d<q，d≠0，a[k]＝1。

由于任何整数对M的求模均在范围{0，...，M-1}内，所以存在M个相异值mod M。此外，选择i∈{0，...，k}和j∈{0，...，n-1}的组合存在2n(k+1)(q-1)种可能方式，-q<d<q，d≠0。为了能够在这些组合与不存在错误的附加可能方式之间进行区分，M应当至少是2n(k+1)(q-1)+1。优选地，M应当选择为实质上大于2n(k+1)(q-1)+1。可以通过迭代地选择并测试随机选择的值，来找到适合的常数α[0]，...，α[k-1]，M越大，这越容易。

在优选实施例中，使用将s(e)与(i，j，d)相关联的表。例如，该表可以具有用于s(e)的每个可能值的行。该行将该值存储于第一字段中，并将i、j和d的值存储于该行的三个附加字段中。可以采用任何适合的方式进行表的查找。显而易见，优选的是表中没有用于实际上不可能出现的“s(e)”的值的行，因为如果有，则表会变得相当大。所以，优选的是不具有无效行。因此，s(e)的实际值不能用于对行号编制索引。用于在这种情况下对行进行有效定位的技术一般是公知的，例如，使用散列或通过折半查找。如果需要，可以使用由整个范围{0，...，M-1}进行了索引编制的表。

因此，首先针对所接收矢量x，计算校正子。如果校正子的结果为零，则不存在错误，矢量x实际上就是码字u。去除奇偶校验符号u[k]并作出x0]，...，x[k-1]＝u[0]，...，u[k-1]的结果就足够了。如果校正子值非零，则存在错误。优选地，使用上述将校正子的每个可能结果与各个组(i，j，d)相关联的表T。这在图2B的步骤270和图3的步骤350中示出。则这给出了i、j和d的值。利用该信息，基于值d来对第I个信息符号x[i]中的第j个q-ary符号进行校正。如上所述，d是由传输信道中的错误引起的差。通过从所识别的q-ary符号中减去d来对错误进行校正。将会理解，同样可以定义其中以另一方式(如加上d)来对错误进行校正的系统。

本领域技术人员可以容易地看出，相同的原理还可以应用于两个或多个q-ary符号错误。然而，校正子值的表以错误个数的指数倍增长。所以这限制了对于多个q-ary符号错误的实际使用。

实际设计示例

通过也适于与NAND闪存一起使用的示例来进一步示出根据本发明的方法和系统。可用存储设备是以要由16个字节的奇偶校验符号保护的512字节信息的页面形式而组织的。

存储单元使用q＝4个等级。用于执行错误校正方法的处理器是具有w＝32位结构的ARM720T型处理器。

在第一设计步骤中，将存储页面划分为八个相同的ECC块，每个ECC块包含由两字节的奇偶校验符号保护的64字节的信息。64字节等于每个是w＝32位的k＝16个字。在本例中，码用于对最多一个4-ary符号错误进行校正。所给出的划分使可以校正的总错误个数最大化。

在第二步骤中，选择模数为M＝65521，这是不超过2¹⁶(＝两个奇偶校验字节的范围)的最大质数。通常，模数不必是质数，但是选择质数简化了系数的设计。

在第三步骤中，在{1，...，M}中选择系数α[0]，...，α[15]，以使(2)中的可能校正子两两相异并且非零。在优选实施例中，通过尝试随机值来选择系数。如果找到满足需求的一组值，则找到了有效的纠错码。

在优选实施例中，还可以选择由所选整数处理器相对较快执行的常数。如果常数值是8比特值(使用8×32位乘法)，则相比于常数是32比特值(给出了16×32位乘法)，所述ARM处理器可以更加快速地执行(1)中的乘法。优选地，通过开始于针对常数值A的上界，来选择可快速执行的常数，其中，最初A＝M。如果对于边界A，找到一组常数，则降低界限A，直至在进行了合理次数(例如，10⁴)的随机试验之后，不再有解为止。

使用以上技术，用于所述系统的一个特定解是：

α＝(26，42，53，55，74，77，99,119，140，149，162，197，201，204，223，233；1)。因而，α[0]＝26，α[1]＝42等。使用这种方法，给出了支持非常快速的乘法的8比特宽度的系数。

在以上示例中，优选地，归约(reduction)是以65521(不超过2¹⁶的最大质数)为模数的求模(mod 65521)。还可以在传统整数处理器的软件中快速执行该归约。将观察到，M＝2¹⁶-15＝65521。在以M为模的归约之前，s(x)的表达式产生范围{0，...，16*255*(2³²-1)+M-1}内的值，这包含在{0..2⁴⁴-1}内。因此，s(x)可以写为：

s(x)＝s0+s1 2¹⁶+s2 2³²，其中，s0、s1、s2在{0..2¹⁶-1}内。

现在可以使用移位和加法来计算该表达式以M为模的归约。在描述中，注释(x<<k)表示x左移k比特，即(x<<k)＝x*2^k，以及(x>>k)表示x右移k比特。

然后，可以如下计算该归约：

t1＝(s1<<4)-s1； t1＝15*s1，与s 2＾16 mod M同余

t2＝(s2<<8)-(s2<<5)+s2； t2＝225*s1，与s2 2＾32 mod M同余

t＝s0+t1+t2； t在{0...1966560}内，与s(x)mod M同余

u0+u1 2^16＝t； u0，u1是t的高16位和低16位

v＝u0+(u1<<4)-u1； v<2*M

如果v>＝65521 则s(x)＝v-65521

否则s(x)＝v。

这总共花费了4次移位、至多八次加法和一次带有比较的IF步骤。

将会理解，本发明还扩展到适于将本发明投入实际应用中的计算机程序，尤其是在载体上或内的计算机程序。该程序可以是源代码、目标代码、诸如部分编译形式的代码中间源(code intermediate source)和目标代码的形式，或者是适于实现根据本发明的方法的任何其它形式。载体可以是能够承载该程序的任何实体或设备。例如，载体可以包括存储介质，如ROM，例如CD ROM或半导体ROM，或者磁记录介质，例如软盘或硬盘。此外载体可以是可传输的载体，如可以经由电或光缆或通过无线电或其它手段传递的电或光信号。当将程序具体实现在这种信号中时，可以通过这种缆线或其它设备或装置来形成载体。可选地，载体可以是嵌入有该程序的集成电路，该集成电路适于执行相关方法或用于相关方法的执行。

应当注意，上述实施例说明本发明，而非限制本发明，本领域技术人员能够在不背离所附权利要求范围的情况下设计可选实施例。在权利要求中，括号内的任何附图标记不应该视为限制该权利要求。动词“包括”的使用及其变体并不排除权利要求中所述的元件或步骤之外的元件或步骤的存在。元件之前的不定冠词(“a”或“an”)并不排除多个这种元件的存在。本发明可以由包括多个相异元件的硬件装置、以及经过适当编程的计算机来实现。在列举了多个装置的设备权利要求中，这些装置中的多个可以由同一项硬件来具体实现。在相互不同的从属权利要求中描述特定措施这一事实并不表示不能有利地使用这些措施的组合。

Claims

1.一种用于生成纠错码的方法，所述纠错码能够对至少一个q-ary符号进行校正，其中，q是2的r次幂，r≥1；所述方法包括：

-将包括k个信息符号(310)u[0]，...，u[k-1]，k≥1和用于保护信息符号的奇偶校验符号(312)u[k]的码字u用作纠错码；每个信息符号表示范围{0，...，2^w-1}内的整数，其中，w＝n*r，n≥1；

-将项-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod M包括在奇偶校验符号u[k]中，其中，M≥2n(k+1)(q-1)+1，乘法·和加法+是可由整数处理单元执行的整数运算，a[0]，...，a[k-1]是{0，...，M-1}中的常数；以及

-选择常数a[0]，...，a[k-1]，以使元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说是唯一的，-q＜d＜q，d≠0。

2.如权利要求1所述的方法，包括形成表T，所述表T用于对包括码字u和错误矢量e的所接收矢量x的q-ary符号中的单个错误进行校正，其中，x＝u+e＝(u[0]+e[0]，...，u[k-1]+e[k-1]，u[k]+e[k])，加法+是可由整数处理单元执行的整数运算；所述表将校正子s(x)＝(a[0]·x[0]+a[1]·x[1]+...+a[k-1]·x[k-1]+x[k])mod M的所有可能结果与各个组(i，j，d)相关联，以能够基于值d对第i个信息符号x[i]中的第j个q-ary符号进行校正。

3.如权利要求1所述的方法，其中w＞1，所述方法包括：将小于2w的最大质数选择为模数M。

4.如权利要求1所述的方法，包括如下选择常数a[0]，...，a[k-1]：随机选择常数a[0]，...，a[k-1]的值，直至找到至少一组常数，对于所述至少一组常数，元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说是两两相异的，-q＜d＜q，d≠0。

5.如权利要求4所述的方法，包括：

-针对常数a[0]，...，a[k-1]中每一个，选择初始上界A＝M；

-随机选择常数a[0]，...，a[k-1]的值；

-验证元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说是否是两两相异的，-q＜d＜q，d≠0。

-当验证结果为肯定时，降低边界A并重复所述选择和验证，当预定次数的连续验证的结果均为否定时，针对所述常数使用给出最后的肯定验证结果的随机选择值。

6.一种保护码字u免受至少一个q-ary符号中的错误的影响的方法，其中，q是2的r次幂，r≥1，所述方法包括：

-接收(210)包括信息符号u[0]，...，u[k-1]，k≥1的码字u，每个信息符号表示范围{0，...，2^w-1}内的整数，其中，w＝n*r，n≥1；

-计算(220)用于保护所述信息符号的奇偶校验符号u[k]，其中，奇偶校验符号包括-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod M，M≥2n(k+1)(q-1)+1，乘法·和加法+是可由整数处理单元执行的整数运算，a[0]，...，a[k-1]在{0，...，M-1}中选择以使元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说两两相异的常数，-q＜d＜q，d≠0；

-在传输或存储码字u之前，将奇偶校验符号u[k]添加至码字u。

7.一种用于对所接收矢量x的q-ary符号中的单个错误进行校正的方法，所接收矢量x包括码字u和错误矢量e，其中，x＝u+e＝(u[0]+e[0]，...，u[k-1]+e[k-1]，u[k]+e[k])，加法+是可由整数处理单元执行的整数运算；码字u包括信息符号u[0]，...，u[k-1]，k≥1和用于保护信息符号的奇偶校验符号u[k]；每个信息符号表示范围{0，...，2^w-1}内的整数，其中，w＝n*r，n≥1，奇偶校验符号包括-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod M，其中M≥2n(k+1)(q-1)+1，乘法·和加法+是可由整数处理单元执行的整数运算，a[0]，...，a[k-1]是在{0，...，M-1}中选择以使元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说两两相异的常数，-q＜d＜q，d≠0，a[k]＝1；

所述方法包括：

-计算(260)校正子s(x)＝(a[0]·x[0]+a[1]·x[1]+...+a[k-1]·x[k-1]+x[k])mod M；以及

-如果所述校正子的结果非零：

-使用将所述校正子的每个可能结果与各个组(i，j，d)相关联的表T，以确定针对所计算的校正子的值(i，j，d)；以及

-基于值d对第i个信息符号x[i]中的第j个q-ary符号进行校正(280)。

8.一种用于保护码字u免受至少一个q-ary符号中的错误的影响的系统，其中，q是2的r次幂，r≥1，所述系统包括：

-用于接收包括k个信息符号u[0]，...，u[k-1]的码字u的装置，k＞1，每个信息符号表示范围{0，...，2^w-1}范围内的整数，其中，w＝n*r，n≥1；

-处理器(130)，包括整数处理器单元(140)，用于在程序的控制下，计算用于保护信息符号的奇偶校验符号u[k]，其中，所述奇偶校验符号包括-(a[0]·u[0]+a[1]·u[1]+...+a[k-1]·u[k-1])mod M，M≥2n(k+1)(q-1)+1，乘法·和加法+是整数运算，a[0]，...，a[k-1]是在{0，...，M-1}中选择以使元素a[i]·d·q^j mod M对于i∈{0，...，k}和j∈{0，...，n-1}来说两两相异的常数，-q＜d＜q，d≠0；以及

-用于在传输或存储码字u之前将奇偶校验符号u[k]添加至码字u的装置。

9.如权利要求8所述的系统，其中，所述系统包括：

用于接收或读取包括码字u和错误矢量e的矢量x的装置，其中，x＝u+e＝(u[0]+e[0]，...，u[k-1]+e[k-1]，u[k]+e[k])，加法+是整数运算；

-所述处理器操作用于在程序的控制下，通过以下操作来对所接收矢量x的q-ary符号中的单个错误进行校正：

-计算校正子s(x)＝(a[0]·x[0]+a[1]·x[1]+...+a[k-1]·x[k-1]+x[k])mod M；以及

-如果校正子的结果非零：

-使用将校正子的每个可能结果与各个组(i，j，d)相关联的表T，以确定针对所计算的校正子的值(i，j，d)；以及

-基于值d对第i个信息符号x[i]中的第j个q-ary符号进行校正。

10.如权利要求8所述的系统，其中，所述系统包括：存储器(110)，用于存储码字u，其中，所述存储器的单独存储单元在物理上设置为存储单个q-ary符号，其中q＞2。

11.如权利要求10所述的系统，其中，所述存储器是NAND闪存类型。