并行BCH算法的实现（含推导代码）

小飞飞 · 发表于 2020-6-12 13:33:24

有人预言,RISC-V或将是继Intel和Arm之后的第三大主流处理器体系。欢迎访问全球首家只专注于RISC-V单片机行业应用的中文网站

您需要登录才可以下载或查看，没有帐号？立即注册

x

本帖最后由小飞飞于 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就能直接得到我们想要的生成多项式，一句话就够：[genpoly,t] = bchgenpoly(n,k)，这里的n和k用你期望的编码参数代替，如[genpoly,t] = 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了，

因此[genpoly,t] = bchgenpoly(16383,15935)这个语句，得到的就是数据长度为8192位（实际可用的是15935位，但我们只用8192位），校验长度为448位，能够纠错32位的生成多项式，后面的介绍也基本上是以这个码作为例子。

有了生成多项式，我们就可以计算8位并行编码的矩阵了，这里直接附上推导的代码，448生成多项式的，大家可以根据实际情况修改，变成任意多项式的。多项式下标0表示最高次项：

void fp8(char gx[449], char(*f)[448])//根据生成多项式计算8位并行编码的矩阵F
{
char ft[448][448];
int i, j, k;
memset(ft, 0, 448 * 448);//初始化，计算f1
for (i = 0;i < 448;i++)
{
ft[i][0] = gx[i + 1];
}
for (i = 0;i < 447;i++)
{
ft[i][i + 1] = 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[i][0] ^= ft[i][j] & gx[j + 1];
}
}
for (i = 0;i < 448;i++)
{
for (j = 1;j < 448;j++)
{
f[i][j] = ft[i][j - 1];
}
}
memcpy_s(ft, 448 * 448, f, 448 * 448);
}
}

复制代码

然后我们可以根据并行编码矩阵生成C语言的代码，这样就不用手写了，让代码来帮我们写代码吧：

void f8code(char f[448][448])//将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[i][j])
{
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[8192], char out[8640])//BCH16383编码，32位纠错，8位并行处理
{
char r[448] = { 0 };//r[0]表示r447
char s[8];//s[0]表示s0
int i, j;
memcpy_s(out, 8640, in, 8192);
for (i = 0;i < 1024;i++)
{
for (j = 0;j < 8;j++)//计算公共项s
{
s[j] = r[j] ^ in[(i << 3) + j];
}
r[0] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (r[8]);
r[1] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ r[9]);
r[2] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[10]);
r[3] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[11]);
r[4] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[12]);
r[5] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[13]);
r[6] = (s[1] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[14]);
r[7] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[7] ^ r[15]);
r[8] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (r[16]);
r[9] = (s[0] ^ s[1]) ^ (s[3] ^ s[6]) ^ (s[7] ^ r[17]);
r[10] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[18]);
r[11] = (s[1] ^ s[4]) ^ (s[6] ^ r[19]);
r[12] = (s[0] ^ s[2]) ^ (s[5] ^ s[7]) ^ (r[20]);
r[13] = (s[5] ^ s[6]) ^ (r[21]);
r[14] = (s[6] ^ s[7]) ^ (r[22]);
r[15] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[23]);
r[16] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[24]);
r[17] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[25]);
r[18] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[26]);
r[19] = (s[2] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[27]);
r[20] = (s[1] ^ s[4]) ^ (r[28]);
r[21] = (s[0] ^ s[2]) ^ (s[5] ^ r[29]);
r[22] = (s[1] ^ s[3]) ^ (s[6] ^ r[30]);
r[23] = (s[0] ^ s[2]) ^ (s[4] ^ s[7]) ^ (r[31]);
r[24] = (s[0] ^ r[32]);
r[25] = (s[1] ^ r[33]);
r[26] = (s[0] ^ s[2]) ^ (r[34]);
r[27] = (s[1] ^ s[3]) ^ (r[35]);
r[28] = (s[2] ^ s[4]) ^ (r[36]);
r[29] = (s[3] ^ s[5]) ^ (r[37]);
r[30] = (s[0] ^ s[4]) ^ (s[6] ^ r[38]);
r[31] = (s[0] ^ s[1]) ^ (s[5] ^ s[7]) ^ (r[39]);
r[32] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ r[40]);
r[33] = (s[1] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[41]);
r[34] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[42]);
r[35] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (r[43]);
r[36] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ r[44]);
r[37] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (r[45]);
r[38] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[46]);
r[39] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ r[47]);
r[40] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[48]);
r[41] = (s[0] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[49]);
r[42] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[50]);
r[43] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[51]);
r[44] = (s[4] ^ s[6]) ^ (s[7] ^ r[52]);
r[45] = (s[1] ^ s[3]) ^ (s[7] ^ r[53]);
r[46] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[54]);
r[47] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[55]);
r[48] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[56]);
r[49] = (s[0] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[57]);
r[50] = (s[3] ^ s[7]) ^ (r[58]);
r[51] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[59]);
r[52] = (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[60]);
r[53] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[61]);
r[54] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[62]);
r[55] = (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[63]);
r[56] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[64]);
r[57] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[65]);
r[58] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[5] ^ r[66]);
r[59] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[67]);
r[60] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[68]);
r[61] = (s[0] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[69]);
r[62] = (s[6] ^ s[7]) ^ (r[70]);
r[63] = (s[1] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[71]);
r[64] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[72]);
r[65] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[73]);
r[66] = (s[2] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[74]);
r[67] = (s[1] ^ s[7]) ^ (r[75]);
r[68] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (r[76]);
r[69] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[6] ^ r[77]);
r[70] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[78]);
r[71] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (r[79]);
r[72] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[80]);
r[73] = (s[1] ^ s[2]) ^ (s[4] ^ s[6]) ^ (r[81]);
r[74] = (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[82]);
r[75] = (s[0] ^ s[1]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[83]);
r[76] = (s[1] ^ s[2]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[84]);
r[77] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[85]);
r[78] = (s[2] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[86]);
r[79] = (s[0] ^ s[1]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[87]);
r[80] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[88]);
r[81] = (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[89]);
r[82] = (s[0] ^ s[1]) ^ (s[3] ^ s[6]) ^ (s[7] ^ r[90]);
r[83] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[91]);
r[84] = (s[1] ^ s[4]) ^ (s[6] ^ r[92]);
r[85] = (s[2] ^ s[5]) ^ (s[7] ^ r[93]);
r[86] = (s[0] ^ s[1]) ^ (s[5] ^ s[6]) ^ (r[94]);
r[87] = (s[1] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[95]);
r[88] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[7] ^ r[96]);
r[89] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (r[97]);
r[90] = (s[0] ^ s[1]) ^ (s[3] ^ s[6]) ^ (s[7] ^ r[98]);
r[91] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[99]);
r[92] = (s[0] ^ s[1]) ^ (s[4] ^ s[6]) ^ (r[100]);
r[93] = (s[1] ^ s[2]) ^ (s[5] ^ s[7]) ^ (r[101]);
r[94] = (s[1] ^ s[2]) ^ (s[5] ^ s[6]) ^ (r[102]);
r[95] = (s[0] ^ s[2]) ^ (s[3] ^ s[6]) ^ (s[7] ^ r[103]);
r[96] = (s[0] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[104]);
r[97] = (s[3] ^ s[6]) ^ (r[105]);
r[98] = (s[0] ^ s[4]) ^ (s[7] ^ r[106]);
r[99] = (s[0] ^ s[3]) ^ (r[107]);
r[100] = (s[1] ^ s[4]) ^ (r[108]);
r[101] = (s[0] ^ s[2]) ^ (s[5] ^ r[109]);
r[102] = (s[0] ^ s[1]) ^ (s[3] ^ s[6]) ^ (r[110]);
r[103] = (s[1] ^ s[2]) ^ (s[4] ^ s[7]) ^ (r[111]);
r[104] = (s[0] ^ s[1]) ^ (s[2] ^ r[112]);
r[105] = (s[1] ^ s[2]) ^ (s[3] ^ r[113]);
r[106] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[114]);
r[107] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[115]);
r[108] = (s[0] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[116]);
r[109] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[117]);
r[110] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[118]);
r[111] = (s[1] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[119]);
r[112] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[7] ^ r[120]);
r[113] = (s[2] ^ s[4]) ^ (s[5] ^ r[121]);
r[114] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[122]);
r[115] = (s[0] ^ s[1]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[123]);
r[116] = (s[0] ^ s[2]) ^ (s[3] ^ s[7]) ^ (r[124]);
r[117] = (s[0] ^ s[4]) ^ (s[5] ^ r[125]);
r[118] = (s[1] ^ s[5]) ^ (s[6] ^ r[126]);
r[119] = (s[2] ^ s[6]) ^ (s[7] ^ r[127]);
r[120] = (s[1] ^ s[5]) ^ (s[7] ^ r[128]);
r[121] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ r[129]);
r[122] = (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[130]);
r[123] = (s[1] ^ s[4]) ^ (s[7] ^ r[131]);
r[124] = (s[1] ^ s[2]) ^ (s[3] ^ r[132]);
r[125] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[133]);
r[126] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[134]);
r[127] = (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[135]);
r[128] = (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[136]);
r[129] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[137]);
r[130] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[138]);
r[131] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[7] ^ r[139]);
r[132] = (s[2] ^ r[140]);
r[133] = (s[0] ^ s[3]) ^ (r[141]);
r[134] = (s[0] ^ s[1]) ^ (s[4] ^ r[142]);
r[135] = (s[1] ^ s[2]) ^ (s[5] ^ r[143]);
r[136] = (s[0] ^ s[2]) ^ (s[3] ^ s[6]) ^ (r[144]);
r[137] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[145]);
r[138] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[146]);
r[139] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[5] ^ r[147]);
r[140] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[148]);
r[141] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[149]);
r[142] = (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[150]);
r[143] = (s[1] ^ s[3]) ^ (s[6] ^ s[7]) ^ (r[151]);
r[144] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[152]);
r[145] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ r[153]);
r[146] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[154]);
r[147] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[155]);
r[148] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[156]);
r[149] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[157]);
r[150] = (s[2] ^ s[6]) ^ (s[7] ^ r[158]);
r[151] = (s[0] ^ s[1]) ^ (s[5] ^ s[7]) ^ (r[159]);
r[152] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ r[160]);
r[153] = (s[1] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[161]);
r[154] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[162]);
r[155] = (s[2] ^ s[4]) ^ (r[163]);
r[156] = (s[0] ^ s[3]) ^ (s[5] ^ r[164]);
r[157] = (s[0] ^ s[1]) ^ (s[4] ^ s[6]) ^ (r[165]);
r[158] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[7] ^ r[166]);
r[159] = (s[2] ^ s[5]) ^ (s[6] ^ r[167]);
r[160] = (s[0] ^ s[3]) ^ (s[6] ^ s[7]) ^ (r[168]);
r[161] = (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[169]);
r[162] = (s[1] ^ s[3]) ^ (s[4] ^ s[6]) ^ (r[170]);
r[163] = (s[0] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[171]);
r[164] = (s[0] ^ s[6]) ^ (r[172]);
r[165] = (s[0] ^ s[1]) ^ (s[7] ^ r[173]);
r[166] = (s[2] ^ s[3]) ^ (s[5] ^ r[174]);
r[167] = (s[3] ^ s[4]) ^ (s[6] ^ r[175]);
r[168] = (s[0] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[176]);
r[169] = (s[0] ^ s[3]) ^ (s[6] ^ r[177]);
r[170] = (s[0] ^ s[1]) ^ (s[4] ^ s[7]) ^ (r[178]);
r[171] = (s[0] ^ s[2]) ^ (s[3] ^ r[179]);
r[172] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (r[180]);
r[173] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ r[181]);
r[174] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[182]);
r[175] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[183]);
r[176] = (s[2] ^ s[4]) ^ (s[7] ^ r[184]);
r[177] = (s[0] ^ s[1]) ^ (r[185]);
r[178] = (s[1] ^ s[2]) ^ (r[186]);
r[179] = (s[0] ^ s[2]) ^ (s[3] ^ r[187]);
r[180] = (s[1] ^ s[3]) ^ (s[4] ^ r[188]);
r[181] = (s[2] ^ s[4]) ^ (s[5] ^ r[189]);
r[182] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[190]);
r[183] = (s[0] ^ s[1]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[191]);
r[184] = (s[2] ^ s[3]) ^ (s[7] ^ r[192]);
r[185] = (s[0] ^ s[1]) ^ (s[4] ^ s[5]) ^ (r[193]);
r[186] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[6] ^ r[194]);
r[187] = (s[1] ^ s[2]) ^ (s[3] ^ s[6]) ^ (s[7] ^ r[195]);
r[188] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[196]);
r[189] = (s[1] ^ s[2]) ^ (s[6] ^ r[197]);
r[190] = (s[0] ^ s[2]) ^ (s[3] ^ s[7]) ^ (r[198]);
r[191] = (s[0] ^ s[4]) ^ (s[5] ^ r[199]);
r[192] = (s[1] ^ s[5]) ^ (s[6] ^ r[200]);
r[193] = (s[0] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[201]);
r[194] = (s[0] ^ s[5]) ^ (s[7] ^ r[202]);
r[195] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[203]);
r[196] = (s[0] ^ s[1]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[204]);
r[197] = (s[0] ^ s[2]) ^ (s[3] ^ s[7]) ^ (r[205]);
r[198] = (s[0] ^ s[4]) ^ (s[5] ^ r[206]);
r[199] = (s[1] ^ s[5]) ^ (s[6] ^ r[207]);
r[200] = (s[0] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[208]);
r[201] = (s[5] ^ s[7]) ^ (r[209]);
r[202] = (s[1] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[210]);
r[203] = (s[2] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[211]);
r[204] = (s[1] ^ s[7]) ^ (r[212]);
r[205] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ r[213]);
r[206] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[6] ^ r[214]);
r[207] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[215]);
r[208] = (s[0] ^ s[4]) ^ (s[6] ^ r[216]);
r[209] = (s[1] ^ s[5]) ^ (s[7] ^ r[217]);
r[210] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[218]);
r[211] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[219]);
r[212] = (s[0] ^ s[2]) ^ (s[4] ^ s[7]) ^ (r[220]);
r[213] = (s[0] ^ r[221]);
r[214] = (s[0] ^ s[1]) ^ (r[222]);
r[215] = (s[1] ^ s[2]) ^ (r[223]);
r[216] = (s[2] ^ s[3]) ^ (r[224]);
r[217] = (s[3] ^ s[4]) ^ (r[225]);
r[218] = (s[4] ^ s[5]) ^ (r[226]);
r[219] = (s[5] ^ s[6]) ^ (r[227]);
r[220] = (s[6] ^ s[7]) ^ (r[228]);
r[221] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[229]);
r[222] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[230]);
r[223] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[231]);
r[224] = (s[0] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[232]);
r[225] = (s[0] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[233]);
r[226] = (s[3] ^ s[4]) ^ (r[234]);
r[227] = (s[0] ^ s[4]) ^ (s[5] ^ r[235]);
r[228] = (s[1] ^ s[5]) ^ (s[6] ^ r[236]);
r[229] = (s[0] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[237]);
r[230] = (s[0] ^ s[5]) ^ (s[7] ^ r[238]);
r[231] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[239]);
r[232] = (s[1] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[240]);
r[233] = (s[1] ^ s[2]) ^ (s[3] ^ s[7]) ^ (r[241]);
r[234] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (r[242]);
r[235] = (s[2] ^ s[3]) ^ (s[5] ^ s[6]) ^ (r[243]);
r[236] = (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[244]);
r[237] = (s[1] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[245]);
r[238] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[246]);
r[239] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ r[247]);
r[240] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[248]);
r[241] = (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[249]);
r[242] = (s[1] ^ s[6]) ^ (s[7] ^ r[250]);
r[243] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[251]);
r[244] = (s[0] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[252]);
r[245] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[253]);
r[246] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[254]);
r[247] = (s[1] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[255]);
r[248] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[7] ^ r[256]);
r[249] = (s[2] ^ s[4]) ^ (s[5] ^ r[257]);
r[250] = (s[3] ^ s[5]) ^ (s[6] ^ r[258]);
r[251] = (s[0] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[259]);
r[252] = (s[0] ^ s[3]) ^ (s[7] ^ r[260]);
r[253] = (s[3] ^ s[4]) ^ (s[5] ^ r[261]);
r[254] = (s[4] ^ s[5]) ^ (s[6] ^ r[262]);
r[255] = (s[0] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[263]);
r[256] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[264]);
r[257] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[265]);
r[258] = (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[266]);
r[259] = (s[1] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[267]);
r[260] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[268]);
r[261] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ r[269]);
r[262] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[270]);
r[263] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[271]);
r[264] = (s[1] ^ s[2]) ^ (s[6] ^ s[7]) ^ (r[272]);
r[265] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[7] ^ r[273]);
r[266] = (s[2] ^ s[5]) ^ (s[6] ^ r[274]);
r[267] = (s[3] ^ s[6]) ^ (s[7] ^ r[275]);
r[268] = (s[1] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[276]);
r[269] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[6] ^ r[277]);
r[270] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[278]);
r[271] = (s[4] ^ s[6]) ^ (r[279]);
r[272] = (s[5] ^ s[7]) ^ (r[280]);
r[273] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[6] ^ r[281]);
r[274] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[282]);
r[275] = (s[0] ^ s[2]) ^ (s[7] ^ r[283]);
r[276] = (s[0] ^ s[5]) ^ (r[284]);
r[277] = (s[1] ^ s[6]) ^ (r[285]);
r[278] = (s[0] ^ s[2]) ^ (s[7] ^ r[286]);
r[279] = (s[0] ^ s[5]) ^ (r[287]);
r[280] = (s[1] ^ s[6]) ^ (r[288]);
r[281] = (s[0] ^ s[2]) ^ (s[7] ^ r[289]);
r[282] = (s[5] ^ r[290]);
r[283] = (s[0] ^ s[6]) ^ (r[291]);
r[284] = (s[1] ^ s[7]) ^ (r[292]);
r[285] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ r[293]);
r[286] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (r[294]);
r[287] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[295]);
r[288] = (s[0] ^ s[2]) ^ (s[4] ^ s[6]) ^ (r[296]);
r[289] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[297]);
r[290] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[298]);
r[291] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[299]);
r[292] = (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[300]);
r[293] = (s[1] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[301]);
r[294] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (r[302]);
r[295] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[303]);
r[296] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[304]);
r[297] = (s[0] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[305]);
r[298] = (s[0] ^ s[3]) ^ (s[6] ^ s[7]) ^ (r[306]);
r[299] = (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[307]);
r[300] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ r[308]);
r[301] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[309]);
r[302] = (s[2] ^ s[6]) ^ (r[310]);
r[303] = (s[0] ^ s[3]) ^ (s[7] ^ r[311]);
r[304] = (s[3] ^ s[4]) ^ (s[5] ^ r[312]);
r[305] = (s[4] ^ s[5]) ^ (s[6] ^ r[313]);
r[306] = (s[5] ^ s[6]) ^ (s[7] ^ r[314]);
r[307] = (s[1] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[315]);
r[308] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[316]);
r[309] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[317]);
r[310] = (s[2] ^ s[7]) ^ (r[318]);
r[311] = (s[0] ^ s[1]) ^ (s[5] ^ r[319]);
r[312] = (s[1] ^ s[2]) ^ (s[6] ^ r[320]);
r[313] = (s[0] ^ s[2]) ^ (s[3] ^ s[7]) ^ (r[321]);
r[314] = (s[0] ^ s[4]) ^ (s[5] ^ r[322]);
r[315] = (s[0] ^ s[1]) ^ (s[5] ^ s[6]) ^ (r[323]);
r[316] = (s[0] ^ s[1]) ^ (s[2] ^ s[6]) ^ (s[7] ^ r[324]);
r[317] = (s[2] ^ s[5]) ^ (s[7] ^ r[325]);
r[318] = (s[0] ^ s[1]) ^ (s[5] ^ s[6]) ^ (r[326]);
r[319] = (s[0] ^ s[1]) ^ (s[2] ^ s[6]) ^ (s[7] ^ r[327]);
r[320] = (s[2] ^ s[5]) ^ (s[7] ^ r[328]);
r[321] = (s[0] ^ s[1]) ^ (s[5] ^ s[6]) ^ (r[329]);
r[322] = (s[0] ^ s[1]) ^ (s[2] ^ s[6]) ^ (s[7] ^ r[330]);
r[323] = (s[0] ^ s[2]) ^ (s[5] ^ s[7]) ^ (r[331]);
r[324] = (s[0] ^ s[5]) ^ (s[6] ^ r[332]);
r[325] = (s[1] ^ s[6]) ^ (s[7] ^ r[333]);
r[326] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[334]);
r[327] = (s[2] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[335]);
r[328] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[336]);
r[329] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[337]);
r[330] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[338]);
r[331] = (s[2] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[339]);
r[332] = (s[0] ^ s[1]) ^ (s[4] ^ r[340]);
r[333] = (s[1] ^ s[2]) ^ (s[5] ^ r[341]);
r[334] = (s[0] ^ s[2]) ^ (s[3] ^ s[6]) ^ (r[342]);
r[335] = (s[1] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[343]);
r[336] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ r[344]);
r[337] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[345]);
r[338] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[346]);
r[339] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[347]);
r[340] = (s[0] ^ s[2]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[348]);
r[341] = (s[7] ^ r[349]);
r[342] = (s[0] ^ s[1]) ^ (s[3] ^ s[5]) ^ (r[350]);
r[343] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[6] ^ r[351]);
r[344] = (s[1] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[7] ^ r[352]);
r[345] = (s[1] ^ s[2]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[353]);
r[346] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[354]);
r[347] = (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[355]);
r[348] = (s[1] ^ s[3]) ^ (s[6] ^ s[7]) ^ (r[356]);
r[349] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[357]);
r[350] = (s[1] ^ s[2]) ^ (s[4] ^ s[6]) ^ (r[358]);
r[351] = (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[359]);
r[352] = (s[0] ^ s[1]) ^ (s[4] ^ s[5]) ^ (s[6] ^ r[360]);
r[353] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[361]);
r[354] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[362]);
r[355] = (s[0] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[363]);
r[356] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[364]);
r[357] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[365]);
r[358] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[366]);
r[359] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[367]);
r[360] = (s[4] ^ r[368]);
r[361] = (s[5] ^ r[369]);
r[362] = (s[6] ^ r[370]);
r[363] = (s[0] ^ s[7]) ^ (r[371]);
r[364] = (s[0] ^ s[3]) ^ (s[5] ^ r[372]);
r[365] = (s[1] ^ s[4]) ^ (s[6] ^ r[373]);
r[366] = (s[2] ^ s[5]) ^ (s[7] ^ r[374]);
r[367] = (s[1] ^ s[5]) ^ (s[6] ^ r[375]);
r[368] = (s[2] ^ s[6]) ^ (s[7] ^ r[376]);
r[369] = (s[0] ^ s[1]) ^ (s[5] ^ s[7]) ^ (r[377]);
r[370] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (s[6] ^ r[378]);
r[371] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[379]);
r[372] = (s[0] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[380]);
r[373] = (s[0] ^ s[4]) ^ (r[381]);
r[374] = (s[1] ^ s[5]) ^ (r[382]);
r[375] = (s[0] ^ s[2]) ^ (s[6] ^ r[383]);
r[376] = (s[0] ^ s[1]) ^ (s[3] ^ s[7]) ^ (r[384]);
r[377] = (s[2] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[385]);
r[378] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[386]);
r[379] = (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[387]);
r[380] = (s[1] ^ s[3]) ^ (s[6] ^ s[7]) ^ (r[388]);
r[381] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[389]);
r[382] = (s[1] ^ s[2]) ^ (s[4] ^ s[6]) ^ (r[390]);
r[383] = (s[2] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[391]);
r[384] = (s[1] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[392]);
r[385] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[393]);
r[386] = (s[0] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[394]);
r[387] = (s[3] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[395]);
r[388] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[396]);
r[389] = (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[397]);
r[390] = (s[1] ^ s[4]) ^ (s[7] ^ r[398]);
r[391] = (s[1] ^ s[2]) ^ (s[3] ^ r[399]);
r[392] = (s[2] ^ s[3]) ^ (s[4] ^ r[400]);
r[393] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[401]);
r[394] = (s[1] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[402]);
r[395] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[403]);
r[396] = (s[0] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[404]);
r[397] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[405]);
r[398] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[406]);
r[399] = (s[1] ^ s[3]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[407]);
r[400] = (s[0] ^ s[1]) ^ (s[2] ^ s[3]) ^ (s[4] ^ s[7]) ^ (r[408]);
r[401] = (s[0] ^ s[2]) ^ (s[4] ^ r[409]);
r[402] = (s[1] ^ s[3]) ^ (s[5] ^ r[410]);
r[403] = (s[2] ^ s[4]) ^ (s[6] ^ r[411]);
r[404] = (s[0] ^ s[3]) ^ (s[5] ^ s[7]) ^ (r[412]);
r[405] = (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[413]);
r[406] = (s[0] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[414]);
r[407] = (s[3] ^ s[6]) ^ (s[7] ^ r[415]);
r[408] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[416]);
r[409] = (s[2] ^ s[3]) ^ (s[4] ^ s[6]) ^ (r[417]);
r[410] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[7] ^ r[418]);
r[411] = (s[3] ^ s[4]) ^ (s[6] ^ r[419]);
r[412] = (s[0] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[420]);
r[413] = (s[3] ^ s[6]) ^ (r[421]);
r[414] = (s[0] ^ s[4]) ^ (s[7] ^ r[422]);
r[415] = (s[3] ^ r[423]);
r[416] = (s[4] ^ r[424]);
r[417] = (s[5] ^ r[425]);
r[418] = (s[0] ^ s[6]) ^ (r[426]);
r[419] = (s[0] ^ s[1]) ^ (s[7] ^ r[427]);
r[420] = (s[0] ^ s[2]) ^ (s[3] ^ s[5]) ^ (r[428]);
r[421] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[6] ^ r[429]);
r[422] = (s[0] ^ s[1]) ^ (s[2] ^ s[4]) ^ (s[5] ^ s[7]) ^ (r[430]);
r[423] = (s[2] ^ s[6]) ^ (r[431]);
r[424] = (s[0] ^ s[3]) ^ (s[7] ^ r[432]);
r[425] = (s[3] ^ s[4]) ^ (s[5] ^ r[433]);
r[426] = (s[4] ^ s[5]) ^ (s[6] ^ r[434]);
r[427] = (s[0] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[435]);
r[428] = (s[0] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[436]);
r[429] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (s[6] ^ s[7]) ^ (r[437]);
r[430] = (s[3] ^ s[4]) ^ (s[6] ^ s[7]) ^ (r[438]);
r[431] = (s[0] ^ s[1]) ^ (s[3] ^ s[4]) ^ (s[7] ^ r[439]);
r[432] = (s[2] ^ s[3]) ^ (s[4] ^ r[440]);
r[433] = (s[0] ^ s[3]) ^ (s[4] ^ s[5]) ^ (r[441]);
r[434] = (s[1] ^ s[4]) ^ (s[5] ^ s[6]) ^ (r[442]);
r[435] = (s[0] ^ s[2]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[443]);
r[436] = (s[5] ^ s[6]) ^ (s[7] ^ r[444]);
r[437] = (s[1] ^ s[3]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[445]);
r[438] = (s[1] ^ s[2]) ^ (s[3] ^ s[4]) ^ (s[5] ^ s[6]) ^ (s[7] ^ r[446]);
r[439] = (s[1] ^ s[2]) ^ (s[4] ^ s[6]) ^ (s[7] ^ r[447]);
r[440] = (s[1] ^ s[2]) ^ (s[7]);
r[441] = (s[0] ^ s[1]) ^ (s[2] ^ s[5]);
r[442] = (s[1] ^ s[2]) ^ (s[3] ^ s[6]);
r[443] = (s[2] ^ s[3]) ^ (s[4] ^ s[7]);
r[444] = (s[1] ^ s[4]);
r[445] = (s[0] ^ s[2]) ^ (s[5]);
r[446] = (s[1] ^ s[3]) ^ (s[6]);
r[447] = (s[0] ^ s[2]) ^ (s[4] ^ s[7]);
}
memcpy_s(out + 8192, 448, r, 448);
}

复制代码

小飞飞 · 发表于 2020-6-13 20:49:39

本帖最后由小飞飞于 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[256];
x = new char *[wei * 2 - 1];//根据位数分配内存
for (i = 0;i < (wei * 2 - 1);i++)
{
x[i] = new char[wei];
memset(x[i], 0, wei);
}
//先计算两个乘数相乘得到的多项式，然后将多项式变为有限域内的多项式，形成最终结果计算公式
x[0][0] = 1;
for (i = 1;i < (wei * 2 - 1);i++)
{
t = x[i - 1][wei - 1];
for (j = wei - 1;j > 0;j--)//将多项式移位
{
x[i][j] = x[i - 1][j - 1];
}
x[i][0] = 0;
if (t)//最高位是1，超出有限域范围，使用本源多项式处理
{
for (j = 0;j < wei;j++)
{
x[i][j] ^= B[j];
}
}
}
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[j][i])//该项为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-6-13 20:56:12

本帖最后由小飞飞于 2020-9-29 10:14 编辑

这段代码中，输入想要的乘法器位数，以及有限域对应的本源多项式，0下标表示多项式最低次项。有限域的本源多项式可以通过下面查到，次数就是2^m-1里面的m：

生成的乘法器代码如下：

另外，我们还需要一些常数乘法器，这种麻烦的事情同样还是让代码去做吧：

void cscfqcode(void)推导14位有限域常数乘法器计算公式，常数为1-32次幂，并以代码形式输出到文件中
{
int i, j, m, n, k;
FILE wenjian;
char x[27][14] = { 0 };X的0次到26次对应的在有限域内的多项式
char t;
int jia;
int kuohao;
char a[14];保存当前幂次的数值
先计算两个乘数相乘得到的26次多项式，然后将26次多项式变为有限域内的多项式，形成最终结果计算公式
x[0][0] = 1;
for (i = 1;i 27;i++)
{
t = x[i - 1][13];
for (j = 13;j 0;j--)将多项式移位
{
x[i][j] = x[i - 1][j - 1];
}
x[i][0] = 0;
if (t)最高位是1，超出有限域范围，使用本源多项式处理
{
x[i][10] ^= 0x01;
x[i][6] ^= 0x01;
x[i][1] ^= 0x01;
x[i][0] ^= 0x01;
}
}
fopen_s(&wenjian, cschengcode.txt, w);
if (wenjian)
{
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, k);
}
for (k = 40;k = 512;k += 8)
{
fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, k);
}
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法，使用位运算实现，0下标表示最低位nn, (k 7743) % 16383);
}
for (k = 1;k = 32;k++)
{
fprintf(wenjian, void cheng%d(char b[14], char c[14])14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, k);
for (i = 0;i 14;i++)
{
a[i] = (ys[k] 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[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m 14;m++)
{
if (a[m] == 0)
{
continue;
}
for (n = 0;n 14;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[14], char c[14])14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, k);
for (i = 0;i 14;i++)
{
a[i] = (ys[k] 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[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m 14;m++)
{
if (a[m] == 0)
{
continue;
}
for (n = 0;n 14;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[14], char c[14])14位有限域常数乘法，使用位运算实现，0下标表示最低位n{n, (k 7743) % 16383);
for (i = 0;i 14;i++)
{
a[i] = (ys[(k 7743) % 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[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
{
for (m = 0;m 14;m++)
{
if (a[m] == 0)
{
continue;
}
for (n = 0;n 14;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;k 32;k++)
{
fprintf(wenjian, tcheng%d(elp[%d], c);n, ((k + 1) 7743) % 16383, k);
fprintf(wenjian, tfor (i = 0;i 14;i++)n);
fprintf(wenjian, t{nttelp[%d][i] = c[i];nt}n, k);
}
fclose(wenjian);
}
}

复制代码

这段代码会生成很多常数乘法器，将会在后面的代码中用到。当然，如果你不在乎那点性能损失，全部用通用的乘法器也是没有问题的，不过考虑到BCH解码速度慢，且会用到NAND FLASH的设备通常不会缺存储代码的空间，因此还是用常数乘法器来优化吧！

除了乘法器，为了能快递生成后面的其它代码，我们还需要做些其它的准备工作，那就是造表，一张是对应有限域的乘法表，一张是乘法表的逆表，代码如下：

void zb(void)//造表，生成2^14有限域上的元素，ys下标表示幂次，数组值表示对应的有限域上的值，ys2为ys的逆表，下标表示有限域上的值，数组值表示幂次

{
int i;
ys[0] = 1;
ys2[0] = -1;
ys2[1] = 0;
for (i = 1;i < 16383;i++)//根据本源多项式生成有限域上的所有元素
{
ys = ys[i - 1] << 1;
if (ys & 0xffffc000)//移位后超出有限域范围则使用本源多项式进行处理
{
ys = (ys & 0x00003fff) ^ 1091;//1091为本源多项式去掉最高位后的值
}
ys2[ys] = 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[8], char t[14])//将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[k * i] >> 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][i] = t[i] ^ c[i];\n\t\t}\n", i - 1);
}
fclose(wenjian);
}
}

复制代码

小飞飞 · 发表于 2020-6-13 21:03:55

本帖最后由小飞飞于 2020-9-29 10:12 编辑

生成的文件上半部分是64的Homer接口函数，下半部分则是伴随式计算的使用代码，待会我们就会看到他们。这个计算方法不是最简单的，但是比较容易理解和实现，因此我也选择了这种算法。最终的伴随式代码如下：

void bss8(char r[8640], char s[64][14])//伴随式计算，8位并行，输入的0下标表示最高位，输出的伴随式的0下标表示最低位
{
int i, j;
char t[14] = { 0 };//除参数r外，所有数组均为0下标表示最低位
char c[14] = { 0 };
memset(s, 0, 64 * 14);
for (j = 0;j < 1080;j++)//每次迭代处理8位数据，分别使用64个不同的伴随式处理模块计算1-64个伴随式的值
{
homer1(r + (j << 3), t);
cheng8(s[0], c);
for (i = 0;i < 14;i++)
{
s[0][i] = t[i] ^ c[i];
}
homer2(r + (j << 3), t);
cheng16(s[1], c);
for (i = 0;i < 14;i++)
{
s[1][i] = t[i] ^ c[i];
}
homer3(r + (j << 3), t);
cheng24(s[2], c);
for (i = 0;i < 14;i++)
{
s[2][i] = t[i] ^ c[i];
}
homer4(r + (j << 3), t);
cheng32(s[3], c);
for (i = 0;i < 14;i++)
{
s[3][i] = t[i] ^ c[i];
}
homer5(r + (j << 3), t);
cheng40(s[4], c);
for (i = 0;i < 14;i++)
{
s[4][i] = t[i] ^ c[i];
}
homer6(r + (j << 3), t);
cheng48(s[5], c);
for (i = 0;i < 14;i++)
{
s[5][i] = t[i] ^ c[i];
}
homer7(r + (j << 3), t);
cheng56(s[6], c);
for (i = 0;i < 14;i++)
{
s[6][i] = t[i] ^ c[i];
}
homer8(r + (j << 3), t);
cheng64(s[7], c);
for (i = 0;i < 14;i++)
{
s[7][i] = t[i] ^ c[i];
}
homer9(r + (j << 3), t);
cheng72(s[8], c);
for (i = 0;i < 14;i++)
{
s[8][i] = t[i] ^ c[i];
}
homer10(r + (j << 3), t);
cheng80(s[9], c);
for (i = 0;i < 14;i++)
{
s[9][i] = t[i] ^ c[i];
}
homer11(r + (j << 3), t);
cheng88(s[10], c);
for (i = 0;i < 14;i++)
{
s[10][i] = t[i] ^ c[i];
}
homer12(r + (j << 3), t);
cheng96(s[11], c);
for (i = 0;i < 14;i++)
{
s[11][i] = t[i] ^ c[i];
}
homer13(r + (j << 3), t);
cheng104(s[12], c);
for (i = 0;i < 14;i++)
{
s[12][i] = t[i] ^ c[i];
}
homer14(r + (j << 3), t);
cheng112(s[13], c);
for (i = 0;i < 14;i++)
{
s[13][i] = t[i] ^ c[i];
}
homer15(r + (j << 3), t);
cheng120(s[14], c);
for (i = 0;i < 14;i++)
{
s[14][i] = t[i] ^ c[i];
}
homer16(r + (j << 3), t);
cheng128(s[15], c);
for (i = 0;i < 14;i++)
{
s[15][i] = t[i] ^ c[i];
}
homer17(r + (j << 3), t);
cheng136(s[16], c);
for (i = 0;i < 14;i++)
{
s[16][i] = t[i] ^ c[i];
}
homer18(r + (j << 3), t);
cheng144(s[17], c);
for (i = 0;i < 14;i++)
{
s[17][i] = t[i] ^ c[i];
}
homer19(r + (j << 3), t);
cheng152(s[18], c);
for (i = 0;i < 14;i++)
{
s[18][i] = t[i] ^ c[i];
}
homer20(r + (j << 3), t);
cheng160(s[19], c);
for (i = 0;i < 14;i++)
{
s[19][i] = t[i] ^ c[i];
}
homer21(r + (j << 3), t);
cheng168(s[20], c);
for (i = 0;i < 14;i++)
{
s[20][i] = t[i] ^ c[i];
}
homer22(r + (j << 3), t);
cheng176(s[21], c);
for (i = 0;i < 14;i++)
{
s[21][i] = t[i] ^ c[i];
}
homer23(r + (j << 3), t);
cheng184(s[22], c);
for (i = 0;i < 14;i++)
{
s[22][i] = t[i] ^ c[i];
}
homer24(r + (j << 3), t);
cheng192(s[23], c);
for (i = 0;i < 14;i++)
{
s[23][i] = t[i] ^ c[i];
}
homer25(r + (j << 3), t);
cheng200(s[24], c);
for (i = 0;i < 14;i++)
{
s[24][i] = t[i] ^ c[i];
}
homer26(r + (j << 3), t);
cheng208(s[25], c);
for (i = 0;i < 14;i++)
{
s[25][i] = t[i] ^ c[i];
}
homer27(r + (j << 3), t);
cheng216(s[26], c);
for (i = 0;i < 14;i++)
{
s[26][i] = t[i] ^ c[i];
}
homer28(r + (j << 3), t);
cheng224(s[27], c);
for (i = 0;i < 14;i++)
{
s[27][i] = t[i] ^ c[i];
}
homer29(r + (j << 3), t);
cheng232(s[28], c);
for (i = 0;i < 14;i++)
{
s[28][i] = t[i] ^ c[i];
}
homer30(r + (j << 3), t);
cheng240(s[29], c);
for (i = 0;i < 14;i++)
{
s[29][i] = t[i] ^ c[i];
}
homer31(r + (j << 3), t);
cheng248(s[30], c);
for (i = 0;i < 14;i++)
{
s[30][i] = t[i] ^ c[i];
}
homer32(r + (j << 3), t);
cheng256(s[31], c);
for (i = 0;i < 14;i++)
{
s[31][i] = t[i] ^ c[i];
}
homer33(r + (j << 3), t);
cheng264(s[32], c);
for (i = 0;i < 14;i++)
{
s[32][i] = t[i] ^ c[i];
}
homer34(r + (j << 3), t);
cheng272(s[33], c);
for (i = 0;i < 14;i++)
{
s[33][i] = t[i] ^ c[i];
}
homer35(r + (j << 3), t);
cheng280(s[34], c);
for (i = 0;i < 14;i++)
{
s[34][i] = t[i] ^ c[i];
}
homer36(r + (j << 3), t);
cheng288(s[35], c);
for (i = 0;i < 14;i++)
{
s[35][i] = t[i] ^ c[i];
}
homer37(r + (j << 3), t);
cheng296(s[36], c);
for (i = 0;i < 14;i++)
{
s[36][i] = t[i] ^ c[i];
}
homer38(r + (j << 3), t);
cheng304(s[37], c);
for (i = 0;i < 14;i++)
{
s[37][i] = t[i] ^ c[i];
}
homer39(r + (j << 3), t);
cheng312(s[38], c);
for (i = 0;i < 14;i++)
{
s[38][i] = t[i] ^ c[i];
}
homer40(r + (j << 3), t);
cheng320(s[39], c);
for (i = 0;i < 14;i++)
{
s[39][i] = t[i] ^ c[i];
}
homer41(r + (j << 3), t);
cheng328(s[40], c);
for (i = 0;i < 14;i++)
{
s[40][i] = t[i] ^ c[i];
}
homer42(r + (j << 3), t);
cheng336(s[41], c);
for (i = 0;i < 14;i++)
{
s[41][i] = t[i] ^ c[i];
}
homer43(r + (j << 3), t);
cheng344(s[42], c);
for (i = 0;i < 14;i++)
{
s[42][i] = t[i] ^ c[i];
}
homer44(r + (j << 3), t);
cheng352(s[43], c);
for (i = 0;i < 14;i++)
{
s[43][i] = t[i] ^ c[i];
}
homer45(r + (j << 3), t);
cheng360(s[44], c);
for (i = 0;i < 14;i++)
{
s[44][i] = t[i] ^ c[i];
}
homer46(r + (j << 3), t);
cheng368(s[45], c);
for (i = 0;i < 14;i++)
{
s[45][i] = t[i] ^ c[i];
}
homer47(r + (j << 3), t);
cheng376(s[46], c);
for (i = 0;i < 14;i++)
{
s[46][i] = t[i] ^ c[i];
}
homer48(r + (j << 3), t);
cheng384(s[47], c);
for (i = 0;i < 14;i++)
{
s[47][i] = t[i] ^ c[i];
}
homer49(r + (j << 3), t);
cheng392(s[48], c);
for (i = 0;i < 14;i++)
{
s[48][i] = t[i] ^ c[i];
}
homer50(r + (j << 3), t);
cheng400(s[49], c);
for (i = 0;i < 14;i++)
{
s[49][i] = t[i] ^ c[i];
}
homer51(r + (j << 3), t);
cheng408(s[50], c);
for (i = 0;i < 14;i++)
{
s[50][i] = t[i] ^ c[i];
}
homer52(r + (j << 3), t);
cheng416(s[51], c);
for (i = 0;i < 14;i++)
{
s[51][i] = t[i] ^ c[i];
}
homer53(r + (j << 3), t);
cheng424(s[52], c);
for (i = 0;i < 14;i++)
{
s[52][i] = t[i] ^ c[i];
}
homer54(r + (j << 3), t);
cheng432(s[53], c);
for (i = 0;i < 14;i++)
{
s[53][i] = t[i] ^ c[i];
}
homer55(r + (j << 3), t);
cheng440(s[54], c);
for (i = 0;i < 14;i++)
{
s[54][i] = t[i] ^ c[i];
}
homer56(r + (j << 3), t);
cheng448(s[55], c);
for (i = 0;i < 14;i++)
{
s[55][i] = t[i] ^ c[i];
}
homer57(r + (j << 3), t);
cheng456(s[56], c);
for (i = 0;i < 14;i++)
{
s[56][i] = t[i] ^ c[i];
}
homer58(r + (j << 3), t);
cheng464(s[57], c);
for (i = 0;i < 14;i++)
{
s[57][i] = t[i] ^ c[i];
}
homer59(r + (j << 3), t);
cheng472(s[58], c);
for (i = 0;i < 14;i++)
{
s[58][i] = t[i] ^ c[i];
}
homer60(r + (j << 3), t);
cheng480(s[59], c);
for (i = 0;i < 14;i++)
{
s[59][i] = t[i] ^ c[i];
}
homer61(r + (j << 3), t);
cheng488(s[60], c);
for (i = 0;i < 14;i++)
{
s[60][i] = t[i] ^ c[i];
}
homer62(r + (j << 3), t);
cheng496(s[61], c);
for (i = 0;i < 14;i++)
{
s[61][i] = t[i] ^ c[i];
}
homer63(r + (j << 3), t);
cheng504(s[62], c);
for (i = 0;i < 14;i++)
{
s[62][i] = t[i] ^ c[i];
}
homer64(r + (j << 3), t);
cheng512(s[63], c);
for (i = 0;i < 14;i++)
{
s[63][i] = t[i] ^ c[i];
}
}
}

复制代码

代码里面能使用常数乘法器的地方均使用了常数乘法器，直接将数据输入进来即可，输出的伴随式一共有64个，后续的错误多项式求取将会用到。

四、解码-错误多项式
计算完了伴随式，我们就可以进入下一步--求取错误多项式了。错误多项式包含了错误的位置信息，可以再进一步求取出错误位置，并完成纠错。

同时，在错误数量小于可纠错位数时，错误多项式的非零项数量也代表了错误的数量。

第一篇文章里面介绍了一种适合硬件实现且比较节约资源的SIBM算法，无须求逆，因此适合在ARM/FPGA上运行，代码如下：

void cw8(char s[64][14], char e[33][14])//根据伴随式计算错误多项式，使用SIBM算法，只需迭代t次，输入伴随式，输出最高次为t的错误多项式
{
int i, j, k;
char d[14];
char dq[14] = { 0 };//所有数组均使用0下标表示最低位
char t[33][14] = { 0 };
char b[33][14] = { 0 };
char elp[33][14] = { 0 };
char st[33][14] = { 0 };
char c[14] = { 0 };
char c2[14] = { 0 };
memcpy_s(d, 14, s[0], 14);
dq[0] = 1;
b[0][0] = 1;
elp[0][0] = 1;
memset(e, 0, 33 * 14);
for (j = 1;j <= 32;j++)
{
if (d[0] | d[1] | d[2] | d[3] | d[4] | d[5] | d[6] | d[7] | d[8] | d[9] | d[10] | d[11] | d[12] | d[13])//判断d是否为0
{
if (j == 1)
{
memcpy_s(elp[1], 14, s[0], 14);//其余不需要修改，都是1
}
else
{
memcpy_s(t[0], 14, elp[0], 14);
memcpy_s(t[1], 14, elp[1], 14);
chengchar(dq, elp[0], c);//0次项和1次项只和e(x)有关
memcpy_s(elp[0], 14, c, 14);
chengchar(dq, elp[1], c);
memcpy_s(elp[1], 14, c, 14);
for (i = 2;i < 33;i++)//e(x)=dq*e(x)+d*x^2*b(x)
{
memcpy_s(t[i], 14, elp[i], 14);
chengchar(dq, elp[i], c);
chengchar(d, b[i - 2], c2);
for (k = 0;k < 14;k++)
{
elp[i][k] = c[k] ^ c2[k];
}
}
for (i = 0;i < 33;i++)//B(x)=e(x)
{
memcpy_s(b[i], 14, t[i], 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[i], 14, b[i - 2], 14);
}
memset(b[0], 0, 14);
memset(b[1], 0, 14);
}
if (j < 32)//最后一次不迭代，没有意义，实际上最后一个伴随式的值没有用到
{
memset(d, 0, 14);//为便于硬件实现，这里每次都做32次运算，由于0乘任何数均为0,0异或任何数均不变，因此不影响结果
for (i = 32;i > 1;i--)
{
memcpy_s(st[i], 14, st[i - 2], 14);//全部右移2位
}
memcpy_s(st[0], 14, s[(j << 1)], 14);
memcpy_s(st[1], 14, s[(j << 1) - 1], 14);
for (i = 0;i < 33;i++)
{
chengchar(st[i], elp[i], c);
for (k = 0;k < 14;k++)
{
d[k] ^= c[k];
}
}
}
}
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[8640], char e[33][14], char out[8192])//错误搜索，使用钱搜索方法，输入接收到的数据和错误多项式，输出正确的数据
{
char elp[32][14];
int i, j, k;
char s[14] = { 0 };//除r和out外，所有数组均使用0下标表示最低位
char c[14] = { 0 };
memcpy_s(elp, 14 * 32, e + 1, 14 * 32);
cheng7743(elp[0], c);//初始化处理，由于是缩短码，需要将错误多项式全部乘以a的一定幂次，以便从中间开始
for (i = 0;i < 14;i++)
{
elp[0][i] = c[i];
}
cheng15486(elp[1], c);
for (i = 0;i < 14;i++)
{
elp[1][i] = c[i];
}
cheng6846(elp[2], c);
for (i = 0;i < 14;i++)
{
elp[2][i] = c[i];
}
cheng14589(elp[3], c);
for (i = 0;i < 14;i++)
{
elp[3][i] = c[i];
}
cheng5949(elp[4], c);
for (i = 0;i < 14;i++)
{
elp[4][i] = c[i];
}
cheng13692(elp[5], c);
for (i = 0;i < 14;i++)
{
elp[5][i] = c[i];
}
cheng5052(elp[6], c);
for (i = 0;i < 14;i++)
{
elp[6][i] = c[i];
}
cheng12795(elp[7], c);
for (i = 0;i < 14;i++)
{
elp[7][i] = c[i];
}
cheng4155(elp[8], c);
for (i = 0;i < 14;i++)
{
elp[8][i] = c[i];
}
cheng11898(elp[9], c);
for (i = 0;i < 14;i++)
{
elp[9][i] = c[i];
}
cheng3258(elp[10], c);
for (i = 0;i < 14;i++)
{
elp[10][i] = c[i];
}
cheng11001(elp[11], c);
for (i = 0;i < 14;i++)
{
elp[11][i] = c[i];
}
cheng2361(elp[12], c);
for (i = 0;i < 14;i++)
{
elp[12][i] = c[i];
}
cheng10104(elp[13], c);
for (i = 0;i < 14;i++)
{
elp[13][i] = c[i];
}
cheng1464(elp[14], c);
for (i = 0;i < 14;i++)
{
elp[14][i] = c[i];
}
cheng9207(elp[15], c);
for (i = 0;i < 14;i++)
{
elp[15][i] = c[i];
}
cheng567(elp[16], c);
for (i = 0;i < 14;i++)
{
elp[16][i] = c[i];
}
cheng8310(elp[17], c);
for (i = 0;i < 14;i++)
{
elp[17][i] = c[i];
}
cheng16053(elp[18], c);
for (i = 0;i < 14;i++)
{
elp[18][i] = c[i];
}
cheng7413(elp[19], c);
for (i = 0;i < 14;i++)
{
elp[19][i] = c[i];
}
cheng15156(elp[20], c);
for (i = 0;i < 14;i++)
{
elp[20][i] = c[i];
}
cheng6516(elp[21], c);
for (i = 0;i < 14;i++)
{
elp[21][i] = c[i];
}
cheng14259(elp[22], c);
for (i = 0;i < 14;i++)
{
elp[22][i] = c[i];
}
cheng5619(elp[23], c);
for (i = 0;i < 14;i++)
{
elp[23][i] = c[i];
}
cheng13362(elp[24], c);
for (i = 0;i < 14;i++)
{
elp[24][i] = c[i];
}
cheng4722(elp[25], c);
for (i = 0;i < 14;i++)
{
elp[25][i] = c[i];
}
cheng12465(elp[26], c);
for (i = 0;i < 14;i++)
{
elp[26][i] = c[i];
}
cheng3825(elp[27], c);
for (i = 0;i < 14;i++)
{
elp[27][i] = c[i];
}
cheng11568(elp[28], c);
for (i = 0;i < 14;i++)
{
elp[28][i] = c[i];
}
cheng2928(elp[29], c);
for (i = 0;i < 14;i++)
{
elp[29][i] = c[i];
}
cheng10671(elp[30], c);
for (i = 0;i < 14;i++)
{
elp[30][i] = c[i];
}
cheng2031(elp[31], c);
for (i = 0;i < 14;i++)
{
elp[31][i] = c[i];
}
for (j = 0;j < 1024;j++)
{
for (k = 0;k < 8;k++)//这里仍然是串行，但在硬件实现时可以将该循环并行化，实现8位并行处理
{
cheng1(elp[0], c);//乘以对应幂次
for (i = 0;i < 14;i++)
{
elp[0][i] = c[i];
}
cheng2(elp[1], c);
for (i = 0;i < 14;i++)
{
elp[1][i] = c[i];
}
cheng3(elp[2], c);
for (i = 0;i < 14;i++)
{
elp[2][i] = c[i];
}
cheng4(elp[3], c);
for (i = 0;i < 14;i++)
{
elp[3][i] = c[i];
}
cheng5(elp[4], c);
for (i = 0;i < 14;i++)
{
elp[4][i] = c[i];
}
cheng6(elp[5], c);
for (i = 0;i < 14;i++)
{
elp[5][i] = c[i];
}
cheng7(elp[6], c);
for (i = 0;i < 14;i++)
{
elp[6][i] = c[i];
}
cheng8(elp[7], c);
for (i = 0;i < 14;i++)
{
elp[7][i] = c[i];
}
cheng9(elp[8], c);
for (i = 0;i < 14;i++)
{
elp[8][i] = c[i];
}
cheng10(elp[9], c);
for (i = 0;i < 14;i++)
{
elp[9][i] = c[i];
}
cheng11(elp[10], c);
for (i = 0;i < 14;i++)
{
elp[10][i] = c[i];
}
cheng12(elp[11], c);
for (i = 0;i < 14;i++)
{
elp[11][i] = c[i];
}
cheng13(elp[12], c);
for (i = 0;i < 14;i++)
{
elp[12][i] = c[i];
}
cheng14(elp[13], c);
for (i = 0;i < 14;i++)
{
elp[13][i] = c[i];
}
cheng15(elp[14], c);
for (i = 0;i < 14;i++)
{
elp[14][i] = c[i];
}
cheng16(elp[15], c);
for (i = 0;i < 14;i++)
{
elp[15][i] = c[i];
}
cheng17(elp[16], c);
for (i = 0;i < 14;i++)
{
elp[16][i] = c[i];
}
cheng18(elp[17], c);
for (i = 0;i < 14;i++)
{
elp[17][i] = c[i];
}
cheng19(elp[18], c);
for (i = 0;i < 14;i++)
{
elp[18][i] = c[i];
}
cheng20(elp[19], c);
for (i = 0;i < 14;i++)
{
elp[19][i] = c[i];
}
cheng21(elp[20], c);
for (i = 0;i < 14;i++)
{
elp[20][i] = c[i];
}
cheng22(elp[21], c);
for (i = 0;i < 14;i++)
{
elp[21][i] = c[i];
}
cheng23(elp[22], c);
for (i = 0;i < 14;i++)
{
elp[22][i] = c[i];
}
cheng24(elp[23], c);
for (i = 0;i < 14;i++)
{
elp[23][i] = c[i];
}
cheng25(elp[24], c);
for (i = 0;i < 14;i++)
{
elp[24][i] = c[i];
}
cheng26(elp[25], c);
for (i = 0;i < 14;i++)
{
elp[25][i] = c[i];
}
cheng27(elp[26], c);
for (i = 0;i < 14;i++)
{
elp[26][i] = c[i];
}
cheng28(elp[27], c);
for (i = 0;i < 14;i++)
{
elp[27][i] = c[i];
}
cheng29(elp[28], c);
for (i = 0;i < 14;i++)
{
elp[28][i] = c[i];
}
cheng30(elp[29], c);
for (i = 0;i < 14;i++)
{
elp[29][i] = c[i];
}
cheng31(elp[30], c);
for (i = 0;i < 14;i++)
{
elp[30][i] = c[i];
}
cheng32(elp[31], c);
for (i = 0;i < 14;i++)
{
elp[31][i] = c[i];
}
memcpy_s(s, 14, e[0], 14);
for (i = 0;i < 32;i++)
{
s[0] ^= elp[i][0];
s[1] ^= elp[i][1];
s[2] ^= elp[i][2];
s[3] ^= elp[i][3];
s[4] ^= elp[i][4];
s[5] ^= elp[i][5];
s[6] ^= elp[i][6];
s[7] ^= elp[i][7];
s[8] ^= elp[i][8];
s[9] ^= elp[i][9];
s[10] ^= elp[i][10];
s[11] ^= elp[i][11];
s[12] ^= elp[i][12];
s[13] ^= elp[i][13];
}
if (s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | s[6] | s[7] | s[8] | s[9] | s[10] | s[11] | s[12] | s[13])
{
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], i=0..(n-1).
*
* Compute the 2*t syndromes by substituting alpha^i into rec(X) and
* evaluating, storing the syndromes in s[i], i=1..2t (leave s[0] zero) .
* Then we use the Berlekamp algorithm to find the error location polynomial
* elp[i].
*
* 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[1026][1024], d[1026], l[1026], u_lu[1026], s[1025];
int root[200], loc[200], reg[201];
t2 = 2 * t;
/* first form the syndromes */
printf("S(x) = ");
for (i = 1; i <= t2; i++) {
s[i] = 0;
for (j = 0; j < length; j++)
if (recd[j] != 0)
s[i] ^= ys[(i * j) % n];
if (s[i] != 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[i] = ys2[s[i]];
printf("%3d ", s[i]);
}
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[u] 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[u] is the degree of
* the elp at that step, and u_l[u] is the difference between
* the step number and the degree of the elp.
*/
/* initialise table entries */
d[0] = 0; /* index form */
d[1] = s[1]; /* index form */
elp[0][0] = 0; /* index form */
elp[1][0] = 1; /* polynomial form */
for (i = 1; i < t2; i++)
{
elp[0][i] = -1; /* index form */
elp[1][i] = 0; /* polynomial form */
}
l[0] = 0;
l[1] = 0;
u_lu[0] = -1;
u_lu[1] = 0;
u = 0;
do
{
u++;
if (d[u] == -1)
{
l[u + 1] = l[u];
for (i = 0; i <= l[u]; i++)
{
elp[u + 1][i] = elp[u][i];
elp[u][i] = ys2[elp[u][i]];
}
}
else//search for words with greatest u_lu[q] for which d[q]!=0搜索最高次项
{
q = u - 1;
while ((d[q] == -1) && (q > 0))
q--;// have found first non-zero d[q]找到第一个非0的q
if (q > 0)
{
j = q;
do
{
j--;
if ((d[j] != -1) && (u_lu[q] < u_lu[j]))
q = j;
} while (j > 0);
}//have now found q such that d[u]!=0 and u_lu[q] is maximum找到符合条件的q
if (l[u] > l[q] + u - q)//store degree of new elp polynomial存储多项式系数
l[u + 1] = l[u];
else
l[u + 1] = l[q] + u - q;
for (i = 0; i < t2; i++)//form new elp(x)
elp[u + 1][i] = 0;
for (i = 0; i <= l[q]; i++)
if (elp[q][i] != -1)
elp[u + 1][i + u - q] = ys[(d[u] + n - d[q] + elp[q][i]) % n];
for (i = 0; i <= l[u]; i++)
{
elp[u + 1][i] ^= elp[u][i];
elp[u][i] = ys2[elp[u][i]];
}
}
u_lu[u + 1] = u - l[u + 1];
if (u < t2)//form (u+1)th discrepancy这段代码计算Dn=Sn+1+E(Sn+1-i * Oi)
{
if (s[u + 1] != -1)//no discrepancy computed on last iteration上次迭代中没有错误
d[u + 1] = ys[s[u + 1]];//将伴随式转换为十进制
else
d[u + 1] = 0;
for (i = 1; i <= l[u + 1]; i++)//算Dj
if ((s[u + 1 - i] != -1) && (elp[u + 1][i] != 0))
d[u + 1] ^= ys[(s[u + 1 - i] + ys2[elp[u + 1][i]]) % n];
d[u + 1] = ys2[d[u + 1]];//put d[u+1] into index form转换为幂次
}
} while ((u < t2) && (l[u + 1] <= t));
u++;
if (l[u] <= t) {/* Can correct errors */
/* put elp into index form */
for (i = 0; i <= l[u]; i++)
elp[u][i] = ys2[elp[u][i]];
printf("sigma(x) = ");
for (i = 0; i <= l[u]; i++)
printf("%3d ", elp[u][i]);
printf("\n");
printf("Roots: ");
/* Chien search: find roots of the error location polynomial */
for (i = 1; i <= l[u]; i++)
reg[i] = elp[u][i];
count = 0;
for (i = 1; i <= n; i++)
{
q = 1;
for (j = 1; j <= l[u]; j++)
if (reg[j] != -1)
{
reg[j] = (reg[j] + j) % n;
q ^= ys[reg[j]];
}
if (!q)
{ // store root and error location number indices
root[count] = i;
loc[count] = n - i;
count++;
printf("%3d ", n - i);
}
}
printf("\n");
if (count == l[u])
/* no. roots = degree of elp hence <= t errors */
for (i = 0; i < l[u]; i++)
recd[loc[i]] ^= 1;
else /* elp has degree >t hence cannot solve */
printf("Incomplete decoding: errors detected\n");
}
}
}

复制代码

完

RISC-V单片机技术交流群

并行BCH算法的实现（含推导代码）

有人预言,RISC-V或将是继Intel和Arm之后的第三大主流处理器体系。欢迎访问全球首家只专注于RISC-V单片机行业应用的中文网站

相关帖子

RISC-V单片机中文网 /2

RISC-V单片机技术交流群

并行BCH算法的实现（含推导代码）

有人预言,RISC-V或将是继Intel和Arm之后的第三大主流处理器体系。欢迎访问全球首家只专注于RISC-V单片机行业应用的中文网站

相关帖子

RISC-V单片机中文网 /2 document.write(unescape("%3Cspan id='cnzz_stat_icon_1278870330'%3E%3C/span%3E%3Cscript src='https://s4.cnzz.com/z_stat.php%3Fid%3D1278870330%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));

RISC-V单片机中文网 /2