ECC算法.doc

ECC 校验的算法 概述 在计算机系统中，保持数据的正确性和一致性是计算机正常工作的一个重要基础。而数据在进行存储和传输过程中，由于干扰、器件故障等原因就存在着使数据失真的可能性。因此，必须采取一些措施计时纠正失真的数据。目前常用的方法有：传统的奇偶检验、CRC校验、重复码校验等。 ECC（Error Correcting Code）校验是在传统奇偶检验的基础上发展而来的，主要是利用数据块的行、列奇偶校验信息生成ECC码，交出给定数据块是否失真并具有对该数据块辑位数出错、校验码冗长、不能纠错的局限性。 ECC算法原理 ECC算法思想为：ECC校验每256B（Byte）数据的为一组进行操作，把256B数据看成256×8的矩阵，矩阵的每个元素表示一个比特（1bit）位。矩阵进行编码后分别生成6bit的列校验信息和16bit的行校验信息。ECC纠错算法检测和纠正错误的原理为：每向闪存写入256B数据时，生成22bit校验码，成为读校验码。然后将写校验码与读校验码按位异或操作。结果会出现3种情况：1）全为“0”，则数据不存在错误；2）存在11bit为“1”，则存在一个比特错误，且可以纠正，:因为在22bit数据中P和P‘都是相互对立的，假如发生翻转，对写入产生的ECC和读出产生的ECC相异或，必然其中一个为1另一个为0，所以22bit中有有11bit为1表示有1bit错误；（3）只存在1bit为1，则生成的校验码出错，数据本身无错；4）其他情况则出现多个错误，不可纠正。当出现情况2）时，改错误比特在数据组中的字节偏移量为P1024、P521、P256、P128、P64、P32、P16、P8。错误比特所处的字节中的位偏移量为P4、P2、P1。因此，根据字节的偏移量和字节中的位偏移量就可以确定数据中发生的翻转位，然后对其进行纠正。 硬件ECC算法的校验码计算规则如下图所示。其中P1、P1’、P2、P2’、P4、P4’为列校验码，P8、P8’、P16、P16’、P32、P32’、P64、P64’、P128、P128’、P256、P256’、P512、P512’、P1024、P1024’为行校验码。 ECC编码 ECC编码算法思想为：设待输入编码器的第n个字节S为： (1) 列校验P1，P1’的生成计算方法为 (2) , (3) , (4) , (5) , (6) , (7) , (8) 行校验码P和P‘的生成计算方法为 （n=1,2,3，...，256）， (9) ， (10) ， (11) ... ， (12) ， (13) 式中：“+”表示“位异或”操作。由式（2）~（13）可知，计算过程没有乘法和除法运算，均是异或运算，这种特点非常适合FPGA实现，只需要采用组合逻辑电路叠加异或即可，完全不影响闪存读写速度。但硬件ECC纠错算法仅能纠错1bit错，当每256B出现2bit以上错误则无法纠正。 ECC解码 ECC解码是利用数据块初始ECC校验码与读取该数据块时重新生成的ECC校验码按位异或，根据异或运算的结果来判断给定数据块是否有错。假如有11bit数据为1，则现在有1bit的翻转，这时候需要解码了。解码的基本思想就是对于出现1的位中肯定有一个行或者列是错误的，这些行列的共同都出现的行还有列就是错误为对应的行还有列。基本实现方法：（1）对于行校验码对出现1bit的行进行和运算，求出错误位所在的行（2）对于列校验码则对出现1bit的列进行和运算，求出错误位对应的列。 FPGA实现ECC编码 本文采用简易的双端口RAM实现ECC的功能，由于校验码产生了22bit的数据，为了读取方便我们引入2bit为11的数据加载校验码后面，所以一帧数据为256Byte的原始数据，还有3Byte的ECC数据。原理如下图所示： 读写地址的关系如下： 读写地址的低wAddrb[8:0] = rAddra[8:0]; 而读写地址的第10位正好相反： wAddrb[9] = rAddra[9]^1b1; 这也就使得读写地址总是相差512个单位。当写地址是0的时候，对应读地址是512；当写地址是512的时候，读地址是0。这就保证了读写地址冲突，且正好实现乒乓操作。在有序地写数据过程中，也就在有序地进行读数据。由于写和读地址是一一对应的关系，所以，只需要分析写地址。 下面来分析产生’、P2、P2’、 P4、P4’ 行向量： P8、P8’、