CN102017425A - 用于执行级联纠错的方法和系统 - Google Patents

Abstract

提供了一种用于执行级联纠错的系统和方法。在一个实现中，一种用于编码数据的装置包括用于生成对应于所接收的输入数据的码字的外部编码器以及用于计算数据的逻辑单元的奇偶校验位的奇偶校验位电路，数据的逻辑单元从码字获得并且具有第一逻辑单元。该装置还包括内部编码器，用于根据对应于第一逻辑单元的第一奇偶校验位生成第一逻辑单元的纠错位，并且将纠错位插入到第一逻辑单元中。

Description

用于执行级联纠错的方法和系统

相关申请

本申请要求于2008年2月20日提交的标题为“Asymmetric ErrorCorrection Codes for Flash Memory”的第61/030,070号美国临时申请以及于2009年1月28日提交的标题为“Systems and Methods For PerformingConcatenated Error Correction”的第12/361,327号美国专利申请的优先权的利益，这二者的全部内容将通过引用并入本文。

背景

技术领域

本文中公开的系统和方法涉及执行纠错的领域，以及更具体地，涉及对存储在非易失性存储器中的数据执行级联纠错的系统和方法。

背景技术

诸如flash EEPROM存储器和/或NAND flash存储器的非易失性存储器被用于各种电子设备中。例如，非易失性存储器可用于蜂窝电话、个人数字助理、无线电设备、个人电脑、笔记本电脑、工作站、照相机、音频播放器、全球定位装置、服务器和其他设备。非易失性存储器可包括不同级别的多个单元，其中这些单元可以被编程以将信息存储为一系列二进制数字(0和1)或“比特”。

如同大多数电子器件一样，非易失性存储器器件容易受到缺陷和错误的影响。错误可能由一些因素产生，这些因素包括由于存储器件的正常操作(包括写/编程、擦除和/或读取操作)产生的存储器状态的门限电平的转换。例如，在程序操作期间，可添加电子以为单元充电来反映特定的状态。

在存储单元的编程期间，将电荷的多个离散单元(电子)传输到存储单元比简单地将存储单元完全充电或放电更加困难。并且，一旦编程操作开始以及电子被添加，则难以在没有执行擦除功能的情况下移除电荷。这种方法可导致单元被错误地编程并且可产生“过调”错误，即，与正在被编程的单元相邻的单元可接收本应已经添加到正在充电的单元的额外的电子。由于电子不可被轻易地移除，因此由过调导致的错误可以被称为“不对称错误”或者“单方向错误”，并且，纠错码(ECC)技术可用于纠正这些错误。

在传统的系统中，ECC技术包括在程序操作期间生成添加到数据串的末端的冗余位(校验位)。然后，当从非易失性存储器读出数据时，这些冗余位可被用于检测并纠正错误。然而，传统技术包括使用不对称错误代码，其中由不对称纠错码组成的码字可以被包含于数据串的末端。传统系统中使用的非对称纠错码通常只纠正单方向的错误类型。

在实际的系统中，错误不是严格的单方向，致使这种代码几乎没有实际价值。

发明内容

在根据所要求权利的本发明的一个实施方式中，提供了一种用于编码数据的装置。该装置包括：外部编码器，用于生成对应于所接收的输入数据的码字；奇偶校验位电路，用于计算数据的逻辑单元的奇偶校验位，数据的逻辑单元从码字中获得并且具有第一逻辑单元；以及内部编码器，用于根据对应于第一逻辑单元的第一奇偶校验位生成针对第一逻辑单元的纠错位，并且将纠错位插入到第一逻辑单元中。

根据所要求权利的本发明的另一实施方式，提供了一种用于通过使用编码器编码数据的方法，该方法包括：生成对应于接收的输入数据的码字；将码字分割到具有第一逻辑单元的数据的逻辑单元中；计算第一逻辑单元的第一奇偶校验位；根据第一奇偶校验位生成第一逻辑单元的纠错位；将纠错位插入到第一逻辑单元中；以及复用并输出具有纠错位的数据的逻辑单元。

在根据所要求权利的本发明的另一实施方式中，提供了一种用于执行级联纠错的方法。该方法包括：计算对应于数据的逻辑单元的奇偶校验位；解码奇偶校验位；检测奇偶校验位中的错误；根据检测的错误执行不对称纠错以纠正数据的逻辑单元中的一个逻辑单元中的数据位；以及，当检测的错误被纠正时，对数据的逻辑单元执行纠错。

应理解的是，以上概述和以下详细描述都只是示例性的和说明性的，并且不限制所要求权利的本发明。

附图说明

并入本说明书并组成本说明书的一部分的附图示出了多个实施方式。图中：

图1是示出了一种根据所要求权利的本发明的一个实施方式的用于编码和解码数据的系统的框图；

图2是示出了一种根据所要求权利的本发明的一个实施方式的编码器的框图；

图3是示出了一种根据所要求权利的本发明的一个实施方式的解码器的框图；

图4是示出了一种根据所要求权利的本发明的一个实施方式的编码序列的流程图；

图5是示出了一种根据所要求权利的本发明的一个实施方式的解码和级联纠错序列的流程图；以及

图6是示出了一种根据所要求权利的本发明的一个实施方式的不对称纠错的序列的流程图。

具体实施方式

在以下的描述中，为了解释而非限制的目的，详细说明了具体的技术和实施方式，诸如步骤的具体序列、接口和配置，以提供本文中所述的技术的深入的理解。虽然将主要结合附图描述这些技术和实施方式，但是本领域的技术人员应进一步认识到，这些技术和实施方式还可以用于其它电子设备和系统。

现在将详细参考所要求权利的本发明的示例性的实施方式，在附图中示出了实施方式的实例。在可能的地方，相同的参考数字将用于整个图示，以表示相同或相似的部分。

图1示出了一种根据所要求权利的本发明的一个实施方式的用于编码和解码数据的系统100。系统100可被集成为一个电子设备中的一个单元或者可以在执行协调处理任务的多个不同的电子设备上被实现。例如，系统100可以在诸如蜂窝电话、个人数字助理、无线电设备、个人电脑、笔记本电脑、工作站、照相机、音频播放器、全球定位装置、服务器、通信系统的节点的设备和其他设备中或其上实现。

系统100可以包括编码器102、存储器件104和/或解码器106。编码器102可以接收和/或取回要写入存储器件104中的数据。该数据可以被从系统100的不同组件(未示出)和/或另一系统(未示出)中接收和/或取回。如以下进一步的细节中所述，编码器102可以采用多种编码技术来处理和编码数据。例如，编码器102可以通过包含诸如Hamming码、BCH码、Reed-Muller码、Array码、Reed-Solomon(RS)码、低密度校验码(LDPC)、turbo码、卷积码和/或对本领域的技术人员明显的其他纠错码来在编码数据中包括不对称纠错码和对称纠错码。

然后，编码数据可以被写入存储器件104的存储单元。编码数据可以具有级联码结构，级联码结构包括外码的层和内码的层，内码是根据单元二进制数据的奇偶校验位的不对称纠错码，以及外码是根据可与存储器件104的单元边界一致的符号边界的对称纠错码。

存储器件104可以是对于本领域的技术人员明显的多层固态非易失性存储器诸如flash存储器、EEPROM或任意其他非易失性存储器。存储器件104可以包括一个或多个存储单元阵列和读写(程序)电路。在存储器件104用编码数据编程之后，解码器106可以读取和/或取回存储的数据。在读取操作期间，解码器106可以实现基于门限的方法，其中通过确定与具体单元相关联的电压值是低于还是高于一个或多个门限值来读出数据。

如以下进一步的细节所述，解码器106可以解码数据并使用由编码器102包含于编码数据中的纠错码来检测并纠正错误。解码序列可以是与编码序列相反的序列，其中可以首先解码不对称和/或内纠错码，以及然后解码对称和/或外纠错码。然后，可以使用解码和纠正数据在系统100中执行多个处理任务。

虽然未示出，系统100可以包括一个或多个应用程序和/或硬件组件的组合。例如，应用程序可以包括软件模块、指令的序列、程序、数据结构、显示界面和/或可以在计算机可读存储介质的处理器上执行的另一类型的结构，以执行所要求权利的本发明的操作。进一步地，硬件组件可以包括中央处理单元(CPU)、总线、存储器件、存储单元、数据处理器、控制装置、模拟数字转换器、数字模拟转换器、调制器、发射器、接收器、天线、收发器、输入设备、输出设备、网络接口设备和/或对于本领域的技术人员明显的另一类型的组件的组合。

现参照图2，示出了编码器200的示例性的实施方式。编码器200可以对应于系统100的编码器102，以及可以执行根据本发明的一个实施方式的编码任务。编码器200可以包括外部编码器202、解复用器(De-MUX)204、奇偶校验位电路206、内部编码器208、格雷码映射电路210和/或复用器(MUX)212。对于本领域的技术人员将明显的是，编码器200可以不需要全部组件202、204、206、208、210和212来编码根据本发明的输入数据，并且可以在输入数据的编码期间通过单个组件执行一个或多个处理任务。

编码器200可以接收需要被写入和/或编程入存储器件的输入数据。输出数据可以被发送到外部编码器202，外部编码器202可以通过使用Reed-Solomon编码器实现。外部编码器202可以通过生成码字执行对称码编码，码字可以包括对应于将被写入数据的存储器件的单元边界的符号边界。由于编码器200实施级联纠错码结构，因此外部编码器202可以在生成码字时使用较低的资源密集型技术并且可以包含较不强健的纠错码。

然后，生成的码字可以被输入De-MUX 204，其中需要将码字分割到数据的多个子部分中。De-MUX 204可以根据要写入输入数据的存储单元的存储能力将码字分割到数据的子部分中。例如，如果存储器件的存储单元具有存储四位数据的能力，则De-MUX 204可以将码字分割到四位数据和/或三位数据的子部分中，其中子部分可被分割到三位数据中以释放空间用于内部编码器208，以插入诸如BCH冗余位的纠错码。

然后，可将数据位的子部分输入到奇偶校验位电路208中，其中可以将子部分进一步分割到数据的逻辑单元组中并且可计算数据的逻辑单元组的奇偶校验位。然后，可将生成的奇偶校验位输入到内部编码器208，其中可以通过使用BCH编码器实现内部编码器。内部编码器208可以生成诸如BCH冗余位的额外的纠错码，并且可以用逻辑单元来编码奇偶校验位和BCH冗余位。然后，将编码数据输入到格雷码映射电路210，其中可以将编码数据映射到对应于要被写入编码数据的存储器件的存储单元的信号电平。然后，映射的信号可被MUX 212复用，并且然后可以被写入和/或编程到存储器件的存储单元中。

图3是示出了一种根据本发明的一个实施方式的解码器300的示例性的实施方式。解码器300可以对应于解码器106，并且执行系统100中的解码任务。解码器300可以包括奇偶校验位电路302、内部解码器304、不对称纠错电路306、外部解码器和复用器(MUX)310。对于本领域的技术人员明显的是，解码器300可以无需全部组件302、304、306、308和310来解码取回的数据，并且在输入数据的解码过程中可以由单个组件执行一个或多个处理任务。

解码器300可以读取和/或取回存储器件的存储单元中编程的数据。取回的数据可以被发送到奇偶校验位电路302，其中可以将取回的数据分割到数据组中并且计算数据组的奇偶校验位。然后，将数据组和奇偶校验位输入到内部解码器304中，其中奇偶校验位可以被解码并且奇偶校验位错误可以被检测。一旦奇偶校验位错误检测完成，不对称纠错电路306可以纠正错误。在纠错期间，不对称纠错电路306可以假定错误是单方向的并且错误是最短距离错误，即，逻辑单元中的错误是由于到位于初始期望程序状态的一侧(例如左侧)的相邻状态的转换产生的。

一旦错误被不对称纠错电路306纠正，则纠正的数据可以被输入外部解码器308，其中可以纠正任何残余误差。外部解码器308可以纠正可能不是单方向的和/或不是最短距离错误事件的错误。然后，纠正的数据可被输入到MUX 310，MUX 310可以将纠正的数据组复用到数据流并且将其输出用于执行处理任务。

现参照图4，提供了一种根据本发明的一个实施方式的用于将编码数据写入存储器件的方法400的流程图。可以通过使用编码器200实现方法400。提供方法400的步骤402-416，用于说明而非限制的目的。该方法开始于步骤402，其中可以接收要被编码和写入存储器件的存储单元的输入数据。然后，在步骤404中，可以对所接收的输入数据执行外部编码并且生成码字。可以由诸如编码器200中的外部编码器202执行步骤404，并且生成的码字可以由诸如0010010111011111001011110的多个二进制数据位组成。

然后，在步骤406中，可以根据其中可被写入二进制数据的存储单元的存储能力，将编码数据分组到多个逻辑单元中。可以由诸如编码器200中的De-MUX 204执行步骤406，并且如果存储单元的存储能力只可以存储四位数据时，多个二进制数据组可以包括四位或三位二进制数据。如图4中所示，该组可以包括：第一组，包括二进制数据位0010；第二组，包括二进制数据位0101；第三组，包括二进制数据位1101；第四组，包括二进制数据位1111；第五组，包括二进制数据位001；第六组，包括二进制数据位011；以及第七组，包括二进制数据位110。第五、六和七组可以只包括三位，以释放空间用于为了纠错目的而可以被插入的额外的位的插入。

然后，该方法移至步骤408，其中可以计算逻辑单元组的奇偶校验位。可以由诸如编码器200中的奇偶校验位电路206执行步骤408，并且如图4中所示，计算的奇偶校验位可以是第一组的1、第二组的0、第三组的1、第四组的0、第五组的1、第六组的0以及第七组的0。然后，在步骤410中，可以用奇偶校验位执行内部编码。例如，可以由编码器200中的内部编码器208执行步骤410，其中根据前四组的奇偶校验位(1、0、1、0)生成三个奇偶校验位(0、0和1)。

然后，在步骤412中，可以在步骤408中计算的奇偶校验位与步骤410中计算的冗余位之间执行排他OR(XOR)函数，用于具有三位数据的数据组。然后，可将从XOR函数生成的位插入到只具有三位数据的逻辑单元中(步骤414)。还可以由诸如编码器200中的内部编码器208执行步骤412和414，其中位1、0和1可以分别被插入到第五、六和七组中。步骤412和414可以被称为“奇偶校验位隐藏(parity hiding)”。在步骤416中，可以根据存储器件的相应的存储单元格雷映射编码数据组，从而该方法可以在数据组被写入存储单元之后结束。

图5示出了一种根据本发明的一个实施方式的用于对写入存储器件的数据执行级联纠错的方法500的流程图。可以通过使用解码器300实现方法500。提供方法500的步骤502-514用于说明而非限制的目的。该方法开始于步骤502，其中可以读取和/或取回存储在存储器件的存储单元中的数据。然后，在步骤504中，将取回数据分组到数据的逻辑单元的七个组中，其中数据的第二组具有需要纠正的错误。例如，当纠正值应为0时，逻辑单元的第二组中的第一位可以是1。

然后，在步骤506中，可以计算对应于逻辑单元的组的奇偶校验位。可以由诸如解码器300中的奇偶校验位电路302执行步骤506，并且计算的奇偶校验位可以是第一组的1、第二组的1、第三组的1、第四组的0、第五组的0、第六组的0以及第七组的1。然后，在步骤508中，可以执行内部解码以解码奇偶校验位并且检测奇偶校验位中的错误。可以由诸如解码器300中的内部解码器304执行步骤508，并且执行BCH解码以检测对应于第二组的奇偶校验位1可能是由于错误而产生。

然后，根据奇偶校验位错误执行不对称纠错(步骤510)。例如，可以由不对称纠错电路执行步骤510，其中可以检测第二组的奇偶校验位中的错误并且可以将第二组中的第一位从1纠正为0。虽然在步骤510中未示出，但是假定奇偶校验位错误是单方向的错误和最短距离错误事件。

例如，图6示出了当使用格雷映射时的不对称纠错的序列600。可以以1111、0111、0011、1011、1001、0001、0101、1101、1100、0100、0000、1000、1010、0010、0110和1110的形式从最低状态到最高状态列出序列。所接收的单元数据(第二组)可以是1101，并且可以在错误中由内部代码解码器指示。通过假设，错误主要是由于单元的从其左相邻状态0101到1101的门限电压转换。从而，不对称纠错单元将单元的位(第二组)从1101纠正为0101。

现返回图5，在步骤512中，可以对数据的逻辑单元组执行外部解码和残余纠错。可以由诸如解码器300中的外部解码器308执行步骤512，以及该纠错可以被称为对称纠错。然后，纠正的数据可以被复用和输出，以及该方法结束(步骤514)。

已经示出了用于说明目的的以上描述。它不是详尽的并且不将本发明限制为精确的形式或者公开的实施方式。可以根据对本说明书的理解和本发明的公开的实施方式的实践对本发明进行修改和调整。例如，可以以不同的顺序或者同时执行以上所述的方法的一个或多个步骤，并仍可达到期望的结果。

通过本说明书的理解以及本文中公开的本发明的实践，本发明的其他实施方式对于本领域的技术人员将是明显的。这意味着本说明书和实例只被认为是示例性的，而本发明的真实范围由以下的权利要求所指示。

Claims (19)

1.一种用于编码数据的装置，所述装置包括：

外部编码器，用于生成对应于所接收的输入数据的码字；

奇偶校验位电路，用于计算数据的逻辑单元的奇偶校验位，所述数据的逻辑单元从所述码字中获得并且具有第一逻辑单元；以及

内部编码器，用于根据对应于所述第一逻辑单元的第一奇偶校验位生成所述第一逻辑单元的纠错位，并且将所述纠错位插入到所述第一逻辑单元中。

2.根据权利要求1所述的装置，还包括复用器，用于复用并输出具有所述纠错位的所述数据的逻辑单元。

3.根据权利要求2所述的装置，还包括解复用器，用于根据用来存储所输出的所述数据的逻辑单元的存储单元的存储能力，通过将所述码字分割到所述逻辑单元中来生成所述数据的逻辑单元。

4.根据权利要求2所述的装置，还包括格雷码映射电路，用于确定存储单元与所输出的数据的逻辑单元之间的对应，其中所述格雷码映射电路将所输出的数据的逻辑单元映射到对应的存储单元的信号电平，并且所述复用器使用所述信号电平将所述数据的逻辑单元写入所述对应的存储单元中。

5.根据权利要求3所述的装置，其中所述解复用器通过在所述数据的第一逻辑单元中分配用于插入所述纠错位的空间来生成所述第一逻辑单元。

6.根据权利要求1所述的装置，其中所述内部编码器编码从所述数据的逻辑单元计算的所述奇偶校验位。

7.根据权利要求1所述的装置，其中：

所述外部编码器通过编码所接收的数据序列生成所述码字；以及

所述码字中的编码符号中的每一个包含整数个数据的逻辑单元。

8.一种用于通过使用编码器编码数据的方法，所述方法包括：

生成对应于所接收的输入数据的码字；

将所述码字分割到具有第一逻辑单元的数据的逻辑单元中；

计算所述第一逻辑单元的第一奇偶校验位；

根据所述第一奇偶校验位生成针对所述第一逻辑单元的纠错位；

将所述纠错位插入到所述第一逻辑单元中；以及

复用并输出具有所述纠错位的所述数据的逻辑单元。

9.根据权利要求8所述的方法，其中根据用于存储所输出的所述数据的逻辑单元的存储单元的存储能力，将所述码字分割到所述逻辑单元中。

10.根据权利要求8所述的方法，还包括：

确定存储单元与所输出的所述数据的逻辑单元之间的对应；

将所输出的所述数据的逻辑单元映射到对应的存储单元的信号电平；

根据所述信号电平将所述数据的逻辑单元写入所述对应的存储单元。

11.根据权利要求8所述的方法，其中通过在所述数据的第一逻辑单元中分配用于插入所述纠错位的空间来生成所述第一逻辑单元。

12.根据权利要求8所述的方法，还包括编码从所述数据的逻辑单元计算的所述奇偶校验位。

13.根据权利要求8所述的方法，还包括：

通过编码所接收的输入数据生成所述码字；以及

在所述码字中包含编码符号，其中所述编码符号包含对应于所述第一逻辑单元的整数。

14.一种用于通过使用纠错装置来执行级联纠错的方法，包括：

计算对应于数据的逻辑单元的奇偶校验位；

解码所述奇偶校验位；

检测所述奇偶校验位中的错误；

执行不对称纠错，以根据所检测到的错误对所述数据的逻辑单元中的一个中的数据位进行纠正；以及

当所检测到的错误被纠正时，对所述数据的逻辑单元执行纠错。

15.根据权利要求14所述的方法，其中通过将接收的数据位分组到所述数据的逻辑单元中来生成所述数据的逻辑单元。

16.根据权利要求14所述的方法，还包括复用并输出所纠错的所述数据的逻辑单元。

17.根据权利要求14所述的方法，其中从所述数据的逻辑单元取回所述奇偶校验位。

18.根据权利要求14所述的方法，其中通过假定所述错误是单方向错误和最短距离错误事件，执行所述不对称纠错。

19.根据权利要求14所述的方法，其中对所述逻辑单元执行的所述纠错是对称纠错。

Images