Byte； RP5---- 跳过 4 个 Byte，处理 4 个 Byte； RP6---- 处理 8 个 Byte，跳过 8 个 Byte RP7---- 跳过 8 个 Byte，处理 8 个 Byte； RP8---- 处理 16 个 Byte，跳过 16 个 Byte RP9---- 跳过 16 个 Byte，处理 16 个 Byte； RP10----处理 32 个 Byte，跳过 32 个 Byte RP11----跳过 32 个 Byte，处理 32 个 Byte； RP12----处理 64 个 Byte，跳过 64 个 Byte RP13----跳过 64 个 Byte，处理 64 个 Byte； RP14----处理 128 个 Byte，跳过 128 个 Byte RP15----跳过 128 个 Byte，处理 128 个 Byte； 可见，RP0 ~ RP15 每个 Bit 位都是 128 个字节（也就是 128 行）即 128*8=1024 个 Bit 位求异或的结果。 综上所述，对 256 字节的数据共生成了 6 个 Bit 的列校验结果，16 个 Bit 的行校验结果， 22 个 Bit。 Nand 中使用 3 个字节存放校验结 共 在 果，多余的两个 Bit 位置 1。存放次序如下表所示： 以 K9F1208 为例， 每个 Page 页包含 512 字节的数据区和 16 字节的 OOB 区。前 256 字节数据生成 3 字节 ECC 校验码，后 256 字节数据 生成 3 字节 ECC 校验码，共 6 字节 ECC 校验码存放在 OOB 区中，存 放的位置为 OOB 区的第 0、1、2 和 3、6、7 字节。 校验码生成算法的 C 语言实现 在 Linux 内核中 ECC 校验算法所在的文件为 drivers/mtd/nand/nand_ecc.c，其实现有新、旧两种，在 ，其实现有新、旧两种， 2.6.27 及更早的内核中使用的程序，从 2.6.28 开始已经不再使用， 及更早的内核中使用的程序， 开始已经不再使用， 而换成了效率更高的程序。 而换成了效率更高的程序。可以在 Documentation/mtd/nand_ecc.txt 文件中找到对新程序的 详细介绍。 详细介绍。 首先分析一下 2.6.27 内核中的 ECC 实现，源代码见:
http://lxr.linux.no/linux+v2.6.27/drivers/mtd/nand/nand_ec c.c /*
Pre-calculated 256-way 1 byte column parity */ static const u_char nand_ecc_precalc_table[] = { 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00, 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f,
0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00 }; 为了加快计算速度，程序中使用了一个预先计算好的列极性表。这个表 中每一个元素都是 unsigned char 类型，表示 8 位二进制数。 表中 8 位二进制数每位的含义： 这个表的意思是：对 0~255 这 256 个数，计算并存储每个数的列校 验值和行校验值，以数作数组下标。比如 nand_ecc_precalc_table[ 13 ] 存储 13 的列校验值和行校验值， 13 的二进制表示为 00001101， 其 CP0 =
Bit0^Bit2^Bit4^Bit6 = 0； CP1 = Bit1^Bit3^Bit5^Bit7 = 1； CP2 = Bit0^Bit1^Bit4^Bit5 = 1; CP3 = Bit2^Bit3^Bit6^Bit7 = 0; CP4 = Bit0^Bit1^Bit2^Bit3 = 1; CP5 = Bit4^Bit5^Bit6^Bit7 = 0; 其行极性 RP = Bit0^Bit1^Bit2^Bit3^Bit4^Bit5^Bit6^Bit7 = 1； 则
nand_ecc_precalc_table[ 13 ] 处存储的值应该是 0101 0110， 即 0x56. 注意，数组 nand_ecc_precalc_table 的下标其实是我们要校验的一 个字节数据。 理解了这个表的含义，也就很容易写个程序生成这个表了。程序见附件 中的 MakeEccTable.c 文件。 有了这个表，对单字节数据 dat，可以直接查表 nand_ecc_precalc_table[ dat ] 得到 dat 的行校验值和列校验值。 但是 ECC 实际要校验的是 256 字节的数据，需要进行 256 次查表， 对得到的 256 个查表结果进行按位异或，最终结果的 Bit0 ~ Bit5 即 是 256 字节数据的 CP0 ~ CP5. /* Build up column parity */ for(i = 0; i < 256; i++) { /* Get CP0 - CP5 from table */ idx = nand_ecc_precalc_table[*dat++]; reg1 ^= (idx & 0x3f); //这里省略了一些，后面会介绍 } Reg1 在这里， 计算列极性的过程其实是先在一个字节数据的内部计算 CP0 ~ CP5, 每个字节都计算完后再与其它字节的计算结果求异或。而表 1 中 是先对一列 Bit0 求异或， 再去异或一列
Bit2。 这两种只是计算顺序不 同，结果是一致的。 因为异或运算的顺序是可交换的。 行极性的计算要复杂一些。 nand_ecc_precalc_table[] 表中的 Bit6 已经保存了每个单字节数 的行极性值。对于待校验的 256 字节数据，分别查表，如果其行极性 为 1，则记录该数据所在的行索引（也就是 for 循环的 i 值），这里的 行索引是很重要的，因为 RP0 ~ RP15 的计算都是跟行索引紧密相关 的，如 RP0 只计算偶数行，RP1 只计算奇数行，等等。 /* Build up column parity */ for(i = 0; i < 256; i++) { /* Get CP0 - CP5 from table */ idx = nand_ecc_precalc_table[*dat++]; reg1 ^= (idx & 0x3f); /* All bit XOR = 1 ? */ if (idx & 0x40) { reg3 ^= (uint8_t) i; reg2 ^= ~((uint8_t) i); } } 这里的关键是理解第 88 和 89 行。 Reg3 和 reg2 都是 unsigned char 型的变量，并都初始化为零。 行索引（也就是 for 循环里的 i）的取值范围为 0~255，根据表 2 可以 得出以下规律： RP0 只计算行索引的 Bit0 为 0 的行，RP1 只计算行索引的 Bit0 为 1 的行； RP2 只计算行索引的 Bit1 为 0 的行，RP3 只计算行索引的 Bit1 为 1 的行； RP4 只计算行索引的 Bit2 为 0 的行，RP5 只计算行索引的 Bit2 为 1 的行； RP6 只计算行索引的 Bit3 为 0 的行，RP7 只计算行索引的 Bit3 为 1 的行； RP8 只计算行索引的 Bit4 为 0 的行，RP9 只计算行索引的 Bit4 为 1 的行； RP10 只计算行索引的 Bit5 为 0 的行，RP11 只计算行索引的 Bit5 为 1 的行； RP12 只计算行索引的 Bit6 为 0 的行，RP13 只计算行索引的 Bit6 为 1 的行； RP14 只计算行索引的 Bit7 为 0 的行，RP15 只计算行索引的 Bit7 为 1 的行； 已经知道，异或运算的作用是判断比特位为 1 的个数，跟比特位为 0 的个数没有关系。如果有偶数个 1 则异或的结果为 0，如果有奇数个 1 则异或的结果为 1。 那么，程序第 88
行，对所有行校验为 1 的行索引按位异或运算，作用 便是： 判断在所有行校验为 1 的行中， 属于 RP1 计算范围内的行有多少个------由 reg3 的 Bit 0 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP3 计算范围内的行有多少个------由 reg3 的 Bit 1 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP5 计算范围内的行有多少个------由 reg3 的 Bit 2 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP7 计算范围内的行有多少个------由 reg3 的 Bit 3 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP9 计算范围内的行有多少个------由 reg3 的 Bit 4 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP11 计算范围内的行有多少个------由 reg3 的 Bit 5 指示，0 表示有偶数个，1 表示有奇数个； 属于 RP13 计算范围内的行有多少个------由 reg3 的 Bit 6 指示，0 表示有偶数个，1 表示有奇数个； 属于 RP15 计算范围内的行有多少个------由 reg3 的 Bit 7 指示，0 表示有偶数个，1 表示有奇数个； 所以，reg3 每个 Bit 位的作用如下表所示： Reg3 第 89 行，对所有行校验为 1 的行索引按位取反之后，再按位异或，作 用就是判断比特位为 0 的个数。比如 reg2 的 Bit0 为 0 表示：所有行 校验为 1 的行中，行索引的 Bit0 为 0 的行有偶数个，也就是落在 RP0 计算范围内的行有偶数个。所以得到结论： 在所有行校验为 1 的行中， 属于 RP0 计算范围内的行有多少个------由 reg2 的 Bit 0 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP2 计算范围内的行有多少个------由 reg2 的 Bit 1 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP4 计算范围内的行有多少个------由 reg2 的 Bit 2 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP6 计算范围内的行有多少个------由 reg2 的 Bit 3 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP8 计算范围内的行有多少个
------由 reg2 的 Bit 4 指示，0 表 示有偶数个，1 表示有奇数个； 属于 RP10 计算范围内的行有多少个------由 reg2 的 Bit 5 指示，0 表示有偶数个，1 表示有奇数个； 属于 RP12 计算范围内的行有多少个------由 reg2 的 Bit 6 指示，0 表示有偶数个，1 表示有奇数个； 属于 RP14 计算范围内的行有多少个------由 reg2 的 Bit 7 指示，0 表示有偶数个，1 表示有奇数个； 所以，reg2 每个 Bit 位的作用如下表所示： Reg2 至此，只用了一个查找表和一个 for 循环，就把所有的校验位 CP0 ~ CP5 和 RP0 ~ RP15 全都计算出来了。下面的任务只是按照表 3 的格 式，把这些比特位重新排列一下顺序而已。 从 reg2 和 reg3 中抽取出 RP8~RP15 放在 tmp1 中，抽取出 RP0~RP7 放在 tmp2 中， Reg1 左移两位，低两位置 1， 然后把 tmp2, tmp1, reg1 放在 ECC 码的三个字节中。 程序中还有 CONFIG_MTD_NAND_ECC_SMC， 又进行了一次取反 操作，暂时还不知为何。 ECC 纠错算法 当往 NAND Flash 的 page 中写入数据的时候，每 256 字节我们生成 一个 ECC 校验和，称之为原 ECC 校验和，保存到 PAGE 的 OOB （out-of-band）数据区中。当从 NAND Flash 中读取数据的时候， 每 256 字节我们生成一个 ECC 校验和，称之为新 ECC 校验和。 将从 OOB 区中读出的原 ECC 校验和新 ECC 校验和按位异或，若结果 为 0，则表示不存在错（或是出现了 ECC 无法检测的错误）；若 3 个 字节异或结果中存在 11 个比特位为 1，表示存在一个比特错误，且可 纠正； 3 个字节异或结果中只存在 1 个比特位为 1， 若 表示 OOB 区出 错；其他情况均表示出现了无法纠正的错误。 假设 ecc_code_raw[3] 保存原始的 ECC 校验码， ecc_code_new[3] 保存新计算出的 ECC 校验码，其格式如下表所示： 对 ecc_code_raw[3] 和 ecc_code_new[3] 按位异或， 得到的结果 三个字节分
别保存在 s0,s1,s2 中，如果 s0s1s2 中共有 11 个 Bit 位 为 1，则表示出现了一个比特位错误，可以修正。定位出错的比特位的 方法是，先确定行地址（即哪个字节出错），再确定列地址（即该字节 中的哪一个 Bit 位出错）。 确定行地址的方法是，设行地址为 unsigned char byteoffs，抽取 s1 中的 Bit7,Bit5,Bit3,Bit1，作为 byteoffs 的高四位， 抽取 s0 中的
Bit7,Bit5,Bit3,Bit1 作为 byteoffs 的低四位， 则 byteoffs 的值就表 示出错字节的行地址（范围为 0 ~ 255）。 确定列地址的方法是：抽取 s2 中的 Bit7,Bit5,Bit3 作为 bitnum 的 低三位，bitnum 其余位置 0，则 bitnum 的表示出错 Bit 位的列地址 （范围为 0 ~ 7）。 下面以一个简单的例子探索一下这其中的奥妙。 假设待校验的数据为两个字节， 0x45 （二进制为 0100 0101） 0x38 和 （二进制为 0011 1000），其行列校验码如下表所示： 从表中可以计算出 CP5 ~ CP0 的值， 列在下表的第一行 （原始数据） 。 假设现在有一个数据位发生变化，0x38 变为 0x3A，也就是 Byte1 的 Bit 1 由 0 变成了 1， 计算得到新的 CP5 ~ CP0 值放在下表第 2 行 （变 化后数据）。新旧校验码求异或的结果放在下表第三行。 可见，当 Bit1 发生变化时，列校验值中只有 CP1，CP2，CP4 发生了 变化，而 CP0，CP3，CP5 没变化，也就是说 6 个 Bit 校验码有一半 发生变化，则求异或的结果中有一半为 1。同理，行校验求异或的结果 也有一半为 1。 这就是为什么前面说 256 字节数据中的一个 Bit 位发生 变化时，新旧 22Bit 校验码求异或的结果中会有 11 个 Bit 位为 1。 再来看怎么定位出错的 Bit 位。以列地址为例，若 CP5 发生变化（异 或后的 CP5=1），则出错处肯定在 Bit 4 ~ Bit 7 中；若 CP5 无变化 （异或后的 CP5=0）,则出错处在 Bit 0 ~ Bit 3 中，这样就筛选掉了 一半的 Bit 位。剩下的 4 个 Bit 位
中，再看 CP3 是否发生变化，又选 出 2 个 Bit 位。剩下的 2Bit 位中再看 CP1 是否发生变化，则最终可定 位 1 个出错的 Bit 位。下面的树形结构更清晰地展示了这个判决过程： 图表 1 出错 Bit 列地址定位的判决树 注意：图中的 CP 指的是求异或之后的结果中的 CP 为什么只用 CP4，CP2，CP0 呢？其实这里面包含冗余信息，因为 CP5=1 则必有 CP4=0， CP5=0 则必有 CP4=1， 也就是 CP5 跟 CP4 一定相反，同理，CP3 跟 CP2 一定相反，CP1 跟 CP0 一定相反。所以 只需要用一半就行了。 这样，我们从异或结果中抽取出 CP5，CP3，CP1 位，便可定位出错 Bit 位的列地址。 比如上面的例子中 CP5/CP3/CP1 = 001， 表示 Bit 1 出错。 同理，行校验 RP1 发生变化，抽取 RP1，可知 Byte 1 发生变化。这 样定位出 Byte 1 的 Bit 0 出错。 当数据位 256 字节时，行校验使用 RP0 ~ RP15，抽取异或结果的 RP15，RP13，RP11，RP9，RP7，RP5，RP3，RP1 位便可定位出 哪个 Byte 出错，再用 CP5,CP3,CP1 定位哪个 Bit 出错。
1 编码
设输入信息多项式I(x)=I0+I1x+…+Ik-1xk-1，校验多项式P(x)=P0+P1x+P2x2+Pn-k-1xn-k-1,则x2tI(x)对生成多项式g(x)求模得到的余式就是校验多项式P(x)，即P(x)= x2tI(x)(mod g(x))，那么生成码子的多项式为C(x)= x2tI(x)+ P(x)。所以BCH码编码的实质就是以生成多项式g(x)为模的除法问题。通常采用LFSR(线性反馈移位寄存器)来实现。具体编码算法如下：
for (i = 0; i < length - k; i++)
bb[i] = 0;
// bb
for (i = k - 1; i >= 0; i--) { //矩阵乘法
feedback = data[i] ^ bb[length - k - 1];
if (feedback != 0) {
for (j = length - k - 1; j > 0; j--)
if (g[j] != 0)
bb[j] = bb[j - 1] ^ feedback;
else
bb[j] = bb[j - 1];
bb[0] = g[0] && feedback;
} else {
for (j = length - k - 1; j > 0; j--)
bb[j] = bb[j - 1];
bb[0] = 0;
}
}
因此编码的关键为：计算对应t的生成多项式，然后根据以上算法完成编码。
已有的c语言程序可以产生g(x)，以上算法实现参见ecc30_encoder.v代码。
代码可能的优化方向：
1. 可以将gg先用mux选择，然后产生bb_0[419:0]~bb_7[419:0] ，可以节省很多组合逻辑。
2. 数据按照8bit并行输入，首先产生bbxx_0=f(bb,g(x)，data_in)，然后利用bbxx_0产生bbxx_1=f(bbxx_0, g(x)，data_in)，依次类推，能否直接推倒出bbxx_x=f(bb,g(x),data_in)
2 译码
在所有的BCH译码算法中最常用是：Berlekamp一Massey迭代算法(简称BM法)。该算法主要分以下三步完成:
第一步：由接收到的R(x)计算伴随式S=(s1,s2，…，s2t);
第二步：根据伴随式S求错误位置多项式σ(x)=σtxt+σt-1xt-1+…+σ1x1+1
第三步：求解σ(x)的根(钱氏(Chien)搜索法)确定错误位置，并进行错误纠正。
2.1 计算伴随式
第一步：由接收到的R(x)计算伴随式S=(s1,s2，…，s2t)
设错误图样为E(x)，则R(x)=C(x)+E(x)
若信道产生t个错误，则
E(x)YtxYt1xltlt1...Y1xYixlil1i1t，式中YiGF(2)，x为错误
li位置数，说明错误发生在R(x)中的第n-li位，错误值是Yi。
R(x)=C(x)+E(x)=q(x)g(x)+r(x)，由码的生成多项式g(x)= m1(x) m3(x)…m2t-1(x)，可以得出αj时
R(x)qj(x)mj(x)rj(x)。式中mj(x)是α的最小多项式，且mj(x)是以αj为根，因此当x=
，所以伴随式S=(s1,s2，…，s2t)的计算转换为R(x)
sjR(j)qj(j)mj(j)rj(j)rj(j)除以g(x)的除法运算，相除之后的余式即为伴随式，伴随式中任何一个元素Sj不为0，则接收到的码元R(x)有错。
以上除法运算，C语言实现如下（为何转换成这个算法，待进一步分析）：
由3.2节可知，对于二进制BCH码，仅需计算S=(s1,s3，…，s2t-1)共t个值，硬件实现以上算法参见ecc30_decoder.v中line555~2122的部分，核心思想是通过
(1,2,3,...,8),(3,6,9,...,24),...,(60,120,180,...,480)共240个α值，求得其他α
（i*jki*jk），并根据以上C语言算法求得S=(s1,s3，…，s2t-1)。
α是伽罗华域GF(2m)的本原域元素，具有如下特性：
2，所以2mm1kk，2m101
代码可能的优化方向：
1. α相乘的单元能否进行优化（详见《纠错码—原理与方法》P172~174）---可以优
2化，m1kk可表示成次数小于m的α多项式表示（例如2m1kk0x1024，那么13个
bit对应位为1，则α对应次幂的系数为1，否则为0），因此
(a0a11a22a33...a1313)ka0ka11ka22ka33k...a1313k'''3'a0a1'1a22a3...a1313合并同类项，可
以得到相乘之后的结果，即系数
''''a0,a1',a2,a3,...,a13，yuming.wang编写了一个C语言程序完成
了以上合并同类项的推导和verilog文件的输出，参见ECC_old.C。
12383692460120180480(,,,...,),(,,,...,),...,(,,,...,)中有重复的部分，能2.
否复用？ ---无法复用，因为每次的被乘数不同
3. 取消双通道的功能：高通道的s计算逻辑全部可以删除
4. 取消读和纠错同时进行功能：syndrxx_latch可以删除
2.2 计算错误位置多项式
第二步：根据伴随式S求错误位置多项式σ(x)=σtxt+σt-1xt-1+…+σ1x1+1
构造错误位置多项式σ(x)=σtxt+σt-1xt-1+…+σ1x1+1，错误位置为该式的根。经过数学推演（详见《纠错码—原理与方法》P270）可知错误位置多项式的系数σ1, σ2,…，σt-1，σ
t和伴随式有如下关系：
求解该线性方程可得错误位置多项式的系数。工程上通过BM迭代算法求解σi。
σ(x)=σtxt+σt-1xt-1+…+σ1x1+1 （1）
S(x)1s1xs2x...six(Yjxij)xi2ii0i0j1t （2）
S(x)(x)(x)11x2x2... （3）
将（1）、（2）代入（3）并经过数学推演（详见《纠错码—原理与方法》P277），得到如下求σ(x)的关键方程：
S(x)(x)(x)(modx2t1)，BM迭代算法即求解该方程：选择一组或两组合理的初值
(0)(x)和(0)(x)，经过第一次迭代运算求得(1)(x)和(1)(x)，依次类推，由(i)(x)和(i)(x)求
(i1)(i1)(x)(x)，其间一共进行2t一1次迭代。迭代过程中定义第j+1步与第j步的差值得和
(j)(x)为dj，则有
djsj1si1j1ii(j) （4）
式中
i(j)是第j次迭代后
(j)2(j)D(j)(j)(x)11(j)x2x...D(j)xi中x的系数，
D(j)(j)(x)，经过数学推演有下列公式成立（详见《纠错码—原理与方法》P279）：
(j1)(x)(j)(x)djdi1xji(i)(x) （5）
(j1)(x)(j)(x)djdi1xji(i)(x) （6）
其中i是j前面的某一行，并满足i-D(i)最大，且di0而D(j1)max(D(j),jiD(i)),
迭代步骤如下：
(1)(1)(x)0，D(1)0，d11 (x)11. 由初值，
(0)(0)(x)0，D(0)0，d0s1 开始迭代 (x)1 ，
2. 由（4）计算
dj，若
dj0(j1)(j)(j1)(j)(x)(x)(x)(x)，，则有，
(j1)D(j1)jD(j)；若dj0，则找出j之前的某一行i，它在所有j行之前各行中的i-D(i)
最大，且
di0(j1)(j1)(x)(x) ，然后根据（5）、（6）计算和
3. 计算和(x)
dj1(2t)(2t)(x)(x)即为所求的(x)，重复（2）进行迭代，经过2t次迭代后得到和
二进制BCH码迭代算法可以进一步简化为如下步骤（数学推演详见《纠错码—原理与方法》P282）：
(1/2)(x)1，D(1/2)0，d1/21， 1. 初始值
(0)(x)1，D(0)0，d0s1 开始迭代
(j)(x)2. 计算
djs2j1si12j1ii(j)，若
dj0(j1)(j)d0(x)(x)，，则有 D(j1)D(j)；若j，
则找出j之前的某一行i，它的2i-D(i)最大，且
di0，计算
(j1)(x)(j)(x)djdi1x2(ji)(i)(x)
3. 计算
dj1(t)，重复2进行迭代，经过t次迭代后得到(x)即为所求的(x)
C语言实现如下：
硬件实现：
由以上算法可知在计算
dj时需要用到S=(s2,s4，…，s2t)，因此首先需要根据S=(s1,s3，…，
22s2s12,s4s2,...,s2ts2t1s2t-1)计算得到S=(s2，s4，…，s2t)(，由伴随式SEH及二进制BCH
T码校验矩阵的定义可得)，galois_mult.v是一个基本乘法单元，在计算S=(s2，s4，…，s2t)时即利用这一个基本乘法单元依次算出S=(s2，s4，…，s2t)，每个需要2cycle，共需2t个cycle完成计算。硬件中已将s2，s4，…，s2t的寄存器和编码寄存器复用。
之后完成以上BM迭代算法（利用的是2t次迭代算法）：
(j)(x)如果在计算
dj0，则(j1)(x)(j)(x)，D(j1)D(j)，然后利用
djsj1si1j1ii(j)计算
dj1，
dj1时利用基本乘法单元galois_mult.v进行相乘，同时累加通过异或完成。对应
ecc30_decoder_p.v中current_bm_state的如下状态跳转：
BM_STATE1->BM_STATE2->BM_STATE2_DU_UPDATE1->BM_STATE2_DU_UPDATE_NOP->BM_STATE2_LAST->BM_STATE_DONE
l_dec_bch_u代表第u次迭代之后的D[u]，l_dec_bch_uplus1代表第u次迭代之后的D[u+1]：即错误位置多项式中最高幂次
elp_u_0,elp_u_1,…,elp_u_30对应第u次迭代之后的错误位置多项式的系数
(u)(u)1(u),2,...,30
d_dec_bch_u代表第u次迭代之后的du
q代表找到的i-D[i]最大的i值,u_lu_q代表i-D[i]。
如果
dj0，则首先通过基本除法单元galois_divide.v计算
12n2di1，利用费尔马小定理的
2222(n1)求逆方法：令A（X）是有限域GF(2m)中的元素，则A(x)A(x)A(x)*A(x)*...*A(x)对应ecc30_decoder_p.v中current_bm_state的如下状态跳转：BM_STATE1->BM_STATE1_ELP_DIVIDE_INIT->BM_STATE1_ELP_TMP
求得
di1
之后，依次求得第u+1次迭代之后的错误位置多项式系数，并判断是否需要更
新q及u_lu_q，对应current_bm_state的如下状态跳转：
BM_STATE1_ELP_TMP->…->BM_STATE1_GET_Q。
之后计算
dj1，对应current_bm_state的如下状态跳转：
BM_STATE1_GET_Q->BM_STATE2->BM_STATE2_DU_UPDATE1->BM_STATE2_DU_UPDATE_NOP->BM_STATE2_LAST->BM_STATE_DONE
硬件可能的优化方向：
1、(s2，s4，…，s2t)的计算能否在(s1,s3，…，s2t-1)计算完成后即进行，从而节省纠错时间，目前(s2，s4，…，s2t)的计算是串行进行的，每个需要2cycle---暂不考虑
2、计数器的复用：在
dj0时计算
dj1时有一个计数器du_iterationg_cnt，在基本除
法单元中有一个计数器---暂不考虑
3、2t次迭代改为t次迭代算法—可以优化
2.3 计算错误位置
第三步：求解σ(x)的根(钱氏(Chien)搜索法)确定错误位置，并进行错误纠正。 求解 (x)0的根就是确定R(x)中哪几位发生了错误，即确定那就需要验证(ni)ni是不是错误位置数，
是不是(x)0的根。若是，则第n一i位有错，否则就无错。依次对每一
位n一i(i=1,2,...,n)进行检验，最后得到(x)0的根，然后取反就得到相应的错误位置。这就是钱氏搜索法的基本思想。
判
((ni))1122...tti是否为0。
硬件实现：
从第8639bit开始进行计算，即取i=8639，利用基本乘法单元依次计算得到
18639,28639*2,...,t8639*t86398639*28639*t,,...,，其中已知，对应current_dec_state的如下状态
跳转：CAN_CORRECT_JUDGE->CHIN_SEARCH_INITIAL->CHIN_SEARCH_STATE1，计算得到的值寄存在syndr1_alpha_table~syndr30_alpha_table的alpha_value中。之后利用syndr1_alpha_table，syndr2_alpha_table,...,syndr30_alpha_table中的galois_mult_alpha_minusX单元计算得到
i8639*i*i*j,i1,2,...,30,j1,2,...,8639，一次计
算判断8个bit是否为错误多项式的根，然后依次对这个8个bit进行统计，共有几个出错的bit，出错位置分别是什么。对应current_dec_state的如下状态跳转：CHIN_SEARCH_STATE1-〉CHIN_SEARCH_ITER-〉…->ONE_CHANNEL_DONE。需要注意的是无论ECC模式是哪种，也不论编码时送入的bit数是多少个，钱搜索时固定从8639搜索到0，判断这8640个bit是否为错误多项式的根，错误位置永远是输入比特的绝对位置，而不是在8640bit中的相对位置，例如，输入待编码bit数为512B+3B+6bit，ecc模式为ecc7，那么编码后总bit数为(512+16)*8bit=4224，那么出错位置一定是在0~4223bit之间。
因篇幅问题不能全部显示，请点此查看更多更全内容