并行BCH算法的实现（含推导代码）
本帖最后由 小飞飞 于 2020-9-29 10:17 编辑BCH算法是一种编解码算法，可以对数据进行校验和纠错，纠错能力强，但是，算法本身需要用到有限域相关知识，对于工程系玩家来说，学习起来颇有难度，因此，我整理了相关资料和使用方法，可以满足大部分情况下的使用需求。
BCH编解码最常用的领域就是FLASH了，众所周知，NAND FLASH是非常容易出错的，特别是当前，FLASH的密度越来越高，MLC甚至TLC的FLASH大行其道，一页数据错个十几二十比特那是家常便饭，没有好的纠错算法可不行，BCH刚好能满足这一需要。
废话不多说，先上两份资料：
https://max.book118.com/html/2017/0513/106621974.shtm
https://max.book118.com/html/2017/0628/118601177.shtm
这两篇论文详细描述了BCH算法的数学原理和优化方法，我后面的大部分工作都基于这两篇文章，在此，也对作者的辛勤劳动表示感谢！
大体上说，BCH分为编码和解码两部分，而解码又分为伴随式计算、错误多项式计算和钱搜索三个步骤。考虑到目前FLASH基本都是8位，且现在处理器的能力已经很强，因此本文仅介绍8位并行处理相关的内容。
一、编码
编码过程本质是有限域的余式求取，原始数据不变，校验数据等于原始数据MOD生成多项式。生成多项式那两篇文章都是用数学方法计算的，其实我们可以直接用现成的，用Matlab就能直接得到我们想要的生成多项式，一句话就够： = bchgenpoly(n,k)，这里的n和k用你期望的编码参数代替，如 = bchgenpoly(16383,15935)，得到的就是总长度16383，可以纠错32位的生成多项式，高次项在前。
这里多啰嗦一句，BCH编码有几个关键参数，包括n、k、t等，n表示码长，也就是编码之后的数据长度，k表示有效的信息位，也就是编码前的数据长度，t表示纠错能力，也就是能够纠错的位数，其中，n必须是2^m-1。
有的小伙伴可能会问了：一般数据长度都是2的m次方啊，比如我想要编码8192位的数据怎么办呢？
其实很简单，按照16383的码长来生成BCH的生成多项式，然后把前面多出来的数据都视为0（或者视为1），因为这些数据都是虚拟的数据，肯定是不会出错的，因此也就不会对真实数据的纠错产生影响，也不需要进行额外的计算。
如果我们需要对长度为A的数据进行编码，那么我们就看看大于A的2^m-1的数里面最小的是多少，就用那个数作为n，比如对8192长度的数据位编码，那么n就算16383。
然后我们再计算所需的校验位长度，计算方法是用前面计算n时2^m-1里面的m乘以你想要的纠错位数t，得到的结果就算校验数据的总长度，比如前面说到的8192长度的数据，如果要纠错32位，那么校验数据的长度就算14*32=448位，用n减去这个校验数据长度，得到的就是有效信息数据的长度k了，
因此 = bchgenpoly(16383,15935)这个语句，得到的就是数据长度为8192位（实际可用的是15935位，但我们只用8192位），校验长度为448位，能够纠错32位的生成多项式，后面的介绍也基本上是以这个码作为例子。
有了生成多项式，我们就可以计算8位并行编码的矩阵了，这里直接附上推导的代码，448生成多项式的，大家可以根据实际情况修改，变成任意多项式的。多项式下标0表示最高次项：
void fp8(char gx, char(*f))//根据生成多项式计算8位并行编码的矩阵F
{
char ft;
int i, j, k;
memset(ft, 0, 448 * 448);//初始化，计算f1
for (i = 0;i < 448;i++)
{
ft = gx;
}
for (i = 0;i < 447;i++)
{
ft = 1;
}
for (k = 0;k < 7;k++)
{
memset(f, 0, 448 * 448);
for (i = 0;i < 448;i++)
{
for (j = 0;j < 448;j++)
{
f ^= ft & gx;
}
}
for (i = 0;i < 448;i++)
{
for (j = 1;j < 448;j++)
{
f = ft;
}
}
memcpy_s(ft, 448 * 448, f, 448 * 448);
}
}
然后我们可以根据并行编码矩阵生成C语言的代码，这样就不用手写了，让代码来帮我们写代码吧：
void f8code(char f)//将F矩阵以代码形式输出到文件
{
FILE * wenjian;
int i, j;
int jia;
int kuohao;
fopen_s(&wenjian, "f8code.txt", "w");
if (wenjian)
{
for (i = 0;i < 448;i++)
{
fprintf(wenjian, "r[%d] = ", i);
jia = 0;
kuohao = 0;
for (j = 0;j < 448;j++)
{
if (f)
{
if (jia++)
{
fprintf(wenjian, " ^ ");
}
if ((kuohao & 0x01) == 0)
{
fprintf(wenjian, "(");
}
if (j < 8)
{
fprintf(wenjian, "s[%d]", j);
}
else
{
fprintf(wenjian, "r[%d]", j);
}
if (kuohao++ & 0x01)
{
fprintf(wenjian, ")");
}
}
}
if (kuohao & 0x01)
{
fprintf(wenjian, ")");
}
fprintf(wenjian, ";\n");
}
fclose(wenjian);
}
}
输出的文件是这样的：
void bch8(char in, char out)//BCH16383编码，32位纠错，8位并行处理
{
char r = { 0 };//r表示r447
char s;//s表示s0
int i, j;
memcpy_s(out, 8640, in, 8192);
for (i = 0;i < 1024;i++)
{
for (j = 0;j < 8;j++)//计算公共项s
{
s = r ^ in[(i << 3) + j];
}
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ r);
r = (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ r);
r = (s ^ r);
r = (s ^ r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s ^ s) ^ (s ^ r);
r = (s ^ s) ^ (s);
r = (s ^ s) ^ (s ^ s);
r = (s ^ s) ^ (s ^ s);
r = (s ^ s) ^ (s ^ s);
r = (s ^ s);
r = (s ^ s) ^ (s);
r = (s ^ s) ^ (s);
r = (s ^ s) ^ (s ^ s);
}
memcpy_s(out + 8192, 448, r, 448);
}
本帖最后由 小飞飞 于 2020-9-29 10:15 编辑
大家可以用生成的代码替换掉中间那一大堆位运算代码，再修修头尾，就变成了所需要的BCH编码代码了，8位并行编码，位运算也适合大多数嵌入式平台和FPGA，效率非常高。
二、解码-有限域乘法器
其实，有限域乘法就是两个多项式相乘，然后将结果再变回到有限域的范围内，变换的方法就不详细描述了，网上一大堆介绍的。只要我们推导出两个多项式相乘的系数，就可以生成一个高效率的有限域乘法器。跟上面一样，我们肯定不会去手工推导的，借助代码的力量：
void cfqcodex(int wei, char * B)//推导任意位数有限域乘法器计算公式，并以代码形式输出到文件中，输入位数和本源多项式
{
int i, j, m, n;
FILE * wenjian;
char ** x;//X的0次到乘法最高位次对应的在有限域内的多项式
char t;
int jia;
int kuohao;
char wenjianming;
x = new char *;//根据位数分配内存
for (i = 0;i < (wei * 2 - 1);i++)
{
x = new char;
memset(x, 0, wei);
}
//先计算两个乘数相乘得到的多项式，然后将多项式变为有限域内的多项式，形成最终结果计算公式
x = 1;
for (i = 1;i < (wei * 2 - 1);i++)
{
t = x;
for (j = wei - 1;j > 0;j--)//将多项式移位
{
x = x;
}
x = 0;
if (t)//最高位是1，超出有限域范围，使用本源多项式处理
{
for (j = 0;j < wei;j++)
{
x ^= B;
}
}
}
sprintf_s(wenjianming, 256, "ChengCode%d.txt", wei);
fopen_s(&wenjian, wenjianming, "w");
if (wenjian)
{
fprintf(wenjian, "void Cheng_%d(char a[%d], char b[%d], char c[%d])//%d位有限域乘法，使用位运算实现，0下标表示最低位\n{\n", wei, wei, wei, wei, wei);
for (i = wei - 1;i >= 0;i--)
{
fprintf(wenjian, "\tc[%d]=", i);
jia = 0;
kuohao = 0;
for (j = (wei * 2 - 2);j >= 0;j--)
{
if (x)//该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m < wei;m++)
{
for (n = 0;n < wei;n++)
{
if ((m + n) == j)//相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
{
if (jia++)
{
fprintf(wenjian, " ^ ");
}
if ((kuohao & 0x01) == 0)
{
fprintf(wenjian, "(");
}
fprintf(wenjian, "(a[%d] & b[%d])", m, n);
if (kuohao++ & 0x01)
{
fprintf(wenjian, ")");
}
}
}
}
}
}
if (kuohao & 0x01)
{
fprintf(wenjian, ")");
}
fprintf(wenjian, ";\n");
}
fprintf(wenjian, "}\n");
fclose(wenjian);
}
}
本帖最后由 小飞飞 于 2020-9-29 10:14 编辑
这段代码中，输入想要的乘法器位数，以及有限域对应的本源多项式，0下标表示多项式最低次项。有限域的本源多项式可以通过下面查到，次数就是2^m-1里面的m：
生成的乘法器代码如下：
另外，我们还需要一些常数乘法器，这种麻烦的事情同样还是让代码去做吧：
void cscfqcode(void)推导14位有限域常数乘法器计算公式，常数为1-32次幂，并以代码形式输出到文件中
{
int i, j, m, n, k;
FILEwenjian;
char x = { 0 };X的0次到26次对应的在有限域内的多项式
char t;
int jia;
int kuohao;
char a;保存当前幂次的数值
先计算两个乘数相乘得到的26次多项式，然后将26次多项式变为有限域内的多项式，形成最终结果计算公式
x = 1;
for (i = 1;i27;i++)
{
t = x;
for (j = 13;j0;j--)将多项式移位
{
x = x;
}
x = 0;
if (t)最高位是1，超出有限域范围，使用本源多项式处理
{
x ^= 0x01;
x ^= 0x01;
x ^= 0x01;
x ^= 0x01;
}
}
fopen_s(&wenjian, cschengcode.txt, w);
if (wenjian)
{
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b, char c);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, k);
}
for (k = 40;k = 512;k += 8)
{
fprintf(wenjian, void cheng%d(char b, char c);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, k);
}
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b, char c);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, (k7743) % 16383);
}
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b, char c)14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, k);
for (i = 0;i14;i++)
{
a = (ysi) & 0x01;
}
for (i = 13;i = 0;i--)
{
fprintf(wenjian, tc[%d]=, i);
jia = 0;
kuohao = 0;
for (j = 26;j = 0;j--)
{
if (x)该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m14;m++)
{
if (a == 0)
{
continue;
}
for (n = 0;n14;n++)
{
if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
{
if (jia++)
{
fprintf(wenjian,^ );
}
if ((kuohao & 0x01) == 0)
{
fprintf(wenjian, ();
}
fprintf(wenjian, b[%d], n);
if (kuohao++ & 0x01)
{
fprintf(wenjian, ));
}
}
}
}
}
}
if (kuohao & 0x01)
{
fprintf(wenjian, ));
}
fprintf(wenjian, ;n);
}
fprintf(wenjian, }nn);
}
for (k = 40;k = 512;k += 8)
{
fprintf(wenjian, void cheng%d(char b, char c)14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, k);
for (i = 0;i14;i++)
{
a = (ysi) & 0x01;
}
for (i = 13;i = 0;i--)
{
fprintf(wenjian, tc[%d]=, i);
jia = 0;
kuohao = 0;
for (j = 26;j = 0;j--)
{
if (x)该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m14;m++)
{
if (a == 0)
{
continue;
}
for (n = 0;n14;n++)
{
if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
{
if (jia++)
{
fprintf(wenjian,^ );
}
if ((kuohao & 0x01) == 0)
{
fprintf(wenjian, ();
}
fprintf(wenjian, b[%d], n);
if (kuohao++ & 0x01)
{
fprintf(wenjian, ));
}
}
}
}
}
}
if (kuohao & 0x01)
{
fprintf(wenjian, ));
}
fprintf(wenjian, ;n);
}
fprintf(wenjian, }nn);
}
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b, char c)14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, (k7743) % 16383);
for (i = 0;i14;i++)
{
a = (ys[(k7743) % 16383]i) & 0x01;
}
for (i = 13;i = 0;i--)
{
fprintf(wenjian, tc[%d]=, i);
jia = 0;
kuohao = 0;
for (j = 26;j = 0;j--)
{
if (x)该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m14;m++)
{
if (a == 0)
{
continue;
}
for (n = 0;n14;n++)
{
if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
{
if (jia++)
{
fprintf(wenjian,^ );
}
if ((kuohao & 0x01) == 0)
{
fprintf(wenjian, ();
}
fprintf(wenjian, b[%d], n);
if (kuohao++ & 0x01)
{
fprintf(wenjian, ));
}
}
}
}
}
}
if (kuohao & 0x01)
{
fprintf(wenjian, ));
}
fprintf(wenjian, ;n);
}
fprintf(wenjian, }nn);
}
for (k = 0;k32;k++)
{
fprintf(wenjian, tcheng%d(elp[%d], c);n, ((k + 1)7743) % 16383, k);
fprintf(wenjian, tfor (i = 0;i14;i++)n);
fprintf(wenjian, t{nttelp[%d] = c;nt}n, k);
}
fclose(wenjian);
}
}
这段代码会生成很多常数乘法器，将会在后面的代码中用到。当然，如果你不在乎那点性能损失，全部用通用的乘法器也是没有问题的，不过考虑到BCH解码速度慢，且会用到NAND FLASH的设备通常不会缺存储代码的空间，因此还是用常数乘法器来优化吧！
除了乘法器，为了能快递生成后面的其它代码，我们还需要做些其它的准备工作，那就是造表，一张是对应有限域的乘法表，一张是乘法表的逆表，代码如下：
void zb(void)//造表，生成2^14有限域上的元素，ys下标表示幂次，数组值表示对应的有限域上的值，ys2为ys的逆表，下标表示有限域上的值，数组值表示幂次
{
int i;
ys = 1;
ys2 = -1;
ys2 = 0;
for (i = 1;i < 16383;i++)//根据本源多项式生成有限域上的所有元素
{
ys = ys << 1;
if (ys & 0xffffc000)//移位后超出有限域范围则使用本源多项式进行处理
{
ys = (ys & 0x00003fff) ^ 1091;//1091为本源多项式去掉最高位后的值
}
ys2 = i;
}
}
这段代码可以很容易修改成其它有限域的乘法表，使用前需要先定义两个全局数组变量作为表格存放的地方。
三、解码-伴随式计算
伴随式的计算使用了第一篇文章里提到的Homer迭代法，利用之前造好的两张表，我们可以很方便的得到所需的全部Homer：
void homercode(void)//Homer迭代法处理流程推导，输入8位数据输出14位，以代码形式输出到文件
{
int i, j, k;
FILE * wenjian;
int jia;
fopen_s(&wenjian, "homercode.txt", "w");
if (wenjian)
{
for (i = 1;i <= 64;i++)
{
fprintf(wenjian, "void homer%d(char r, char t)//将8位输入转换为14位，0下标表示最低位\n{\n", i);
for (j = 0;j < 14;j++)
{
fprintf(wenjian, "\tt[%d]=", j);
jia = 0;
for (k = 0;k < 8;k++)
{
if ((ys >> j) & 0x01)
{
if (jia++)
{
fprintf(wenjian, " ^ ");
}
fprintf(wenjian, "r[%d]", 7 - k);
}
}
if (jia == 0)//一个符合条件的元素都没有，直接赋值0
{
fprintf(wenjian, "0;\n");
}
else
{
fprintf(wenjian, ";\n");
}
}
fprintf(wenjian, "}\n\n");
}
for (i = 1;i <= 64;i++)
{
fprintf(wenjian, "\t\thomer%d(r + (j << 3), t);\n", i);
fprintf(wenjian, "\t\tcheng%d(s[%d], c);\n", i << 3, i - 1);
fprintf(wenjian, "\t\tfor (i = 0;i < 14;i++)\n");
fprintf(wenjian, "\t\t{\n\t\t\ts[%d] = t ^ c;\n\t\t}\n", i - 1);
}
fclose(wenjian);
}
}
本帖最后由 小飞飞 于 2020-9-29 10:12 编辑
生成的文件上半部分是64的Homer接口函数，下半部分则是伴随式计算的使用代码，待会我们就会看到他们。这个计算方法不是最简单的，但是比较容易理解和实现，因此我也选择了这种算法。最终的伴随式代码如下：
void bss8(char r, char s)//伴随式计算，8位并行，输入的0下标表示最高位，输出的伴随式的0下标表示最低位
{
int i, j;
char t = { 0 };//除参数r外，所有数组均为0下标表示最低位
char c = { 0 };
memset(s, 0, 64 * 14);
for (j = 0;j < 1080;j++)//每次迭代处理8位数据，分别使用64个不同的伴随式处理模块计算1-64个伴随式的值
{
homer1(r + (j << 3), t);
cheng8(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer2(r + (j << 3), t);
cheng16(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer3(r + (j << 3), t);
cheng24(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer4(r + (j << 3), t);
cheng32(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer5(r + (j << 3), t);
cheng40(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer6(r + (j << 3), t);
cheng48(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer7(r + (j << 3), t);
cheng56(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer8(r + (j << 3), t);
cheng64(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer9(r + (j << 3), t);
cheng72(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer10(r + (j << 3), t);
cheng80(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer11(r + (j << 3), t);
cheng88(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer12(r + (j << 3), t);
cheng96(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer13(r + (j << 3), t);
cheng104(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer14(r + (j << 3), t);
cheng112(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer15(r + (j << 3), t);
cheng120(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer16(r + (j << 3), t);
cheng128(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer17(r + (j << 3), t);
cheng136(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer18(r + (j << 3), t);
cheng144(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer19(r + (j << 3), t);
cheng152(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer20(r + (j << 3), t);
cheng160(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer21(r + (j << 3), t);
cheng168(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer22(r + (j << 3), t);
cheng176(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer23(r + (j << 3), t);
cheng184(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer24(r + (j << 3), t);
cheng192(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer25(r + (j << 3), t);
cheng200(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer26(r + (j << 3), t);
cheng208(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer27(r + (j << 3), t);
cheng216(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer28(r + (j << 3), t);
cheng224(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer29(r + (j << 3), t);
cheng232(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer30(r + (j << 3), t);
cheng240(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer31(r + (j << 3), t);
cheng248(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer32(r + (j << 3), t);
cheng256(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer33(r + (j << 3), t);
cheng264(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer34(r + (j << 3), t);
cheng272(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer35(r + (j << 3), t);
cheng280(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer36(r + (j << 3), t);
cheng288(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer37(r + (j << 3), t);
cheng296(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer38(r + (j << 3), t);
cheng304(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer39(r + (j << 3), t);
cheng312(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer40(r + (j << 3), t);
cheng320(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer41(r + (j << 3), t);
cheng328(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer42(r + (j << 3), t);
cheng336(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer43(r + (j << 3), t);
cheng344(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer44(r + (j << 3), t);
cheng352(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer45(r + (j << 3), t);
cheng360(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer46(r + (j << 3), t);
cheng368(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer47(r + (j << 3), t);
cheng376(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer48(r + (j << 3), t);
cheng384(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer49(r + (j << 3), t);
cheng392(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer50(r + (j << 3), t);
cheng400(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer51(r + (j << 3), t);
cheng408(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer52(r + (j << 3), t);
cheng416(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer53(r + (j << 3), t);
cheng424(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer54(r + (j << 3), t);
cheng432(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer55(r + (j << 3), t);
cheng440(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer56(r + (j << 3), t);
cheng448(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer57(r + (j << 3), t);
cheng456(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer58(r + (j << 3), t);
cheng464(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer59(r + (j << 3), t);
cheng472(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer60(r + (j << 3), t);
cheng480(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer61(r + (j << 3), t);
cheng488(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer62(r + (j << 3), t);
cheng496(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer63(r + (j << 3), t);
cheng504(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
homer64(r + (j << 3), t);
cheng512(s, c);
for (i = 0;i < 14;i++)
{
s = t ^ c;
}
}
}
代码里面能使用常数乘法器的地方均使用了常数乘法器，直接将数据输入进来即可，输出的伴随式一共有64个，后续的错误多项式求取将会用到。
四、解码-错误多项式
计算完了伴随式，我们就可以进入下一步--求取错误多项式了。错误多项式包含了错误的位置信息，可以再进一步求取出错误位置，并完成纠错。
同时，在错误数量小于可纠错位数时，错误多项式的非零项数量也代表了错误的数量。
第一篇文章里面介绍了一种适合硬件实现且比较节约资源的SIBM算法，无须求逆，因此适合在ARM/FPGA上运行，代码如下：
void cw8(char s, char e)//根据伴随式计算错误多项式，使用SIBM算法，只需迭代t次，输入伴随式，输出最高次为t的错误多项式
{
int i, j, k;
char d;
char dq = { 0 };//所有数组均使用0下标表示最低位
char t = { 0 };
char b = { 0 };
char elp = { 0 };
char st = { 0 };
char c = { 0 };
char c2 = { 0 };
memcpy_s(d, 14, s, 14);
dq = 1;
b = 1;
elp = 1;
memset(e, 0, 33 * 14);
for (j = 1;j <= 32;j++)
{
if (d | d | d | d | d | d | d | d | d | d | d | d | d | d)//判断d是否为0
{
if (j == 1)
{
memcpy_s(elp, 14, s, 14);//其余不需要修改，都是1
}
else
{
memcpy_s(t, 14, elp, 14);
memcpy_s(t, 14, elp, 14);
chengchar(dq, elp, c);//0次项和1次项只和e(x)有关
memcpy_s(elp, 14, c, 14);
chengchar(dq, elp, c);
memcpy_s(elp, 14, c, 14);
for (i = 2;i < 33;i++)//e(x)=dq*e(x)+d*x^2*b(x)
{
memcpy_s(t, 14, elp, 14);
chengchar(dq, elp, c);
chengchar(d, b, c2);
for (k = 0;k < 14;k++)
{
elp = c ^ c2;
}
}
for (i = 0;i < 33;i++)//B(x)=e(x)
{
memcpy_s(b, 14, t, 14);
}
}
memcpy_s(dq, 14, d, 14);
}
else
{
for (i = 32;i > 1;i--)//B(x)=x^2*B(x)，dq和e(x)不变，无需修改
{
memcpy_s(b, 14, b, 14);
}
memset(b, 0, 14);
memset(b, 0, 14);
}
if (j < 32)//最后一次不迭代，没有意义，实际上最后一个伴随式的值没有用到
{
memset(d, 0, 14);//为便于硬件实现，这里每次都做32次运算，由于0乘任何数均为0,0异或任何数均不变，因此不影响结果
for (i = 32;i > 1;i--)
{
memcpy_s(st, 14, st, 14);//全部右移2位
}
memcpy_s(st, 14, s[(j << 1)], 14);
memcpy_s(st, 14, s[(j << 1) - 1], 14);
for (i = 0;i < 33;i++)
{
chengchar(st, elp, c);
for (k = 0;k < 14;k++)
{
d ^= c;
}
}
}
}
memcpy_s(e, 14 * 33, elp, 14 * 33);
}
输入之前计算得到的64个伴随式，输出33个错误多项式，特别说明一下，因为我们的纠错能力是32位，因此错误多项式的最高次项是32次，加上常数项，一共就有33项，这里千万不要漏掉一项，不然会造成纠错能力下降1位的。
获取了错误多项式后，如果最高次项为0，那么错误位数小于32位，错误多项式的最高次项的次数就是错误的总比特数，同时我们可以根据错误多项式查找具体的错误位置。
五、解码-钱搜索
钱搜索是目前BCH最常用的错误位置求取方法，该方法本质上就是穷举所有的出错可能，并根据结果判断是否正确。
虽然原理粗浅，但是目前最实用的一种方法。
前面已经说到，对于8192的数据，我们实际上用的是16383的码，只是前面的数据都视为0或者视为1了，因此，在搜索时，我们需要先跳转到全0或全1搜索到数据开始位置时的搜索状态，也就是对每一个搜索项做一个乘法。具体代码如下：
void ss8(char r, char e, char out)//错误搜索，使用钱搜索方法，输入接收到的数据和错误多项式，输出正确的数据
{
char elp;
int i, j, k;
char s = { 0 };//除r和out外，所有数组均使用0下标表示最低位
char c = { 0 };
memcpy_s(elp, 14 * 32, e + 1, 14 * 32);
cheng7743(elp, c);//初始化处理，由于是缩短码，需要将错误多项式全部乘以a的一定幂次，以便从中间开始
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng15486(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng6846(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng14589(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng5949(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng13692(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng5052(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng12795(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng4155(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng11898(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng3258(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng11001(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng2361(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng10104(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng1464(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng9207(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng567(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng8310(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng16053(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng7413(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng15156(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng6516(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng14259(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng5619(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng13362(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng4722(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng12465(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng3825(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng11568(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng2928(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng10671(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng2031(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
for (j = 0;j < 1024;j++)
{
for (k = 0;k < 8;k++)//这里仍然是串行，但在硬件实现时可以将该循环并行化，实现8位并行处理
{
cheng1(elp, c);//乘以对应幂次
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng2(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng3(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng4(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng5(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng6(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng7(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng8(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng9(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng10(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng11(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng12(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng13(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng14(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng15(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng16(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng17(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng18(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng19(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng20(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng21(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng22(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng23(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng24(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng25(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng26(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng27(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng28(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng29(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng30(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng31(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
cheng32(elp, c);
for (i = 0;i < 14;i++)
{
elp = c;
}
memcpy_s(s, 14, e, 14);
for (i = 0;i < 32;i++)
{
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
s ^= elp;
}
if (s | s | s | s | s | s | s | s | s | s | s | s | s | s)
{
out[(j << 3) + k] = r[(j << 3) + k];
}
else
{
out[(j << 3) + k] = r[(j << 3) + k] ^ (char)0x01;
printf("错误位置：%d\n", (j << 3) + k);
}
}
}
}
由于数据是二进制的，得出了错误位置后，直接将所在位的数据取反就可以得到正确的数据，至此，数据的BCH编码和解码、纠错就全部完成了。
最后，附上一段在网上找到的BCH编码算法，使用传统的BM算法计算错误多项式，供大家参考：
void decode_bch(char * recd, int length, int t, int n)//国外的BCH解码算法，使用传统的BM算法计算错误多项式
/*
* Simon Rockliff's implementation of Berlekamp's algorithm.
*
* Assume we have received bits in recd, i=0..(n-1).
*
* Compute the 2*t syndromes by substituting alpha^i into rec(X) and
* evaluating, storing the syndromes in s, i=1..2t (leave s zero) .
* Then we use the Berlekamp algorithm to find the error location polynomial
* elp.
*
* If the degree of the elp is >t, then we cannot correct all the errors, and
* we have detected an uncorrectable error pattern. We output the information
* bits uncorrected.
*
* If the degree of elp is <=t, we substitute alpha^i , i=1..n into the elp
* to get the roots, hence the inverse roots, the error location numbers.
* This step is usually called "Chien's search".
*
* If the number of errors located is not equal the degree of the elp, then
* the decoder assumes that there are more than t errors and cannot correct
* them, only detect them. We output the information bits uncorrected.
*/
{
register int i, j, u, q, t2, count = 0, syn_error = 0;
int elp, d, l, u_lu, s;
int root, loc, reg;
t2 = 2 * t;
/* first form the syndromes */
printf("S(x) = ");
for (i = 1; i <= t2; i++) {
s = 0;
for (j = 0; j < length; j++)
if (recd != 0)
s ^= ys[(i * j) % n];
if (s != 0)
syn_error = 1; /* set error flag if non-zero syndrome */
/*
* Note: If the code is used only for ERROR DETECTION, then
* exit program here indicating the presence of errors.
*/
/* convert syndrome from polynomial form to index form*/
s = ys2];
printf("%3d ", s);
}
printf("\n");
if (syn_error) { /* if there are errors, try to correct them */
/*
* Compute the error location polynomial via the Berlekamp
* iterative algorithm. Following the terminology of Lin and
* Costello's book : d is the 'mu'th discrepancy, where
* u='mu'+1 and 'mu' (the Greek letter!) is the step number
* ranging from -1 to 2*t (see L&C),l is the degree of
* the elp at that step, and u_l is the difference between
* the step number and the degree of the elp.
*/
/* initialise table entries */
d = 0; /* index form */
d = s; /* index form */
elp = 0; /* index form */
elp = 1; /* polynomial form */
for (i = 1; i < t2; i++)
{
elp = -1; /* index form */
elp = 0;/* polynomial form */
}
l = 0;
l = 0;
u_lu = -1;
u_lu = 0;
u = 0;
do
{
u++;
if (d == -1)
{
l = l;
for (i = 0; i <= l; i++)
{
elp = elp;
elp = ys2];
}
}
else//search for words with greatest u_lu for which d!=0搜索最高次项
{
q = u - 1;
while ((d == -1) && (q > 0))
q--;// have found first non-zero d找到第一个非0的q
if (q > 0)
{
j = q;
do
{
j--;
if ((d != -1) && (u_lu < u_lu))
q = j;
} while (j > 0);
}//have now found q such that d!=0 and u_lu is maximum找到符合条件的q
if (l > l + u - q)//store degree of new elp polynomial存储多项式系数
l = l;
else
l = l + u - q;
for (i = 0; i < t2; i++)//form new elp(x)
elp = 0;
for (i = 0; i <= l; i++)
if (elp != -1)
elp = ys[(d + n - d + elp) % n];
for (i = 0; i <= l; i++)
{
elp ^= elp;
elp = ys2];
}
}
u_lu = u - l;
if (u < t2)//form (u+1)th discrepancy这段代码计算Dn=Sn+1+E(Sn+1-i * Oi)
{
if (s != -1)//no discrepancy computed on last iteration上次迭代中没有错误
d = ys];//将伴随式转换为十进制
else
d = 0;
for (i = 1; i <= l; i++)//算Dj
if ((s != -1) && (elp != 0))
d ^= ys[(s + ys2]) % n];
d = ys2];//put d into index form转换为幂次
}
} while ((u < t2) && (l <= t));
u++;
if (l <= t) {/* Can correct errors */
/* put elp into index form */
for (i = 0; i <= l; i++)
elp = ys2];
printf("sigma(x) = ");
for (i = 0; i <= l; i++)
printf("%3d ", elp);
printf("\n");
printf("Roots: ");
/* Chien search: find roots of the error location polynomial */
for (i = 1; i <= l; i++)
reg = elp;
count = 0;
for (i = 1; i <= n; i++)
{
q = 1;
for (j = 1; j <= l; j++)
if (reg != -1)
{
reg = (reg + j) % n;
q ^= ys];
}
if (!q)
{ // store root and error location number indices
root = i;
loc = n - i;
count++;
printf("%3d ", n - i);
}
}
printf("\n");
if (count == l)
/* no. roots = degree of elp hence <= t errors */
for (i = 0; i < l; i++)
recd] ^= 1;
else /* elp has degree >t hence cannot solve */
printf("Incomplete decoding: errors detected\n");
}
}
}完
页:
[1]