查看: 330|回复: 3
收起左侧

并行BCH算法的实现(含推导代码)

[复制链接]

  离线 

  • TA的每日心情
    奋斗
    2021-3-3 12:35
  • 签到天数: 45 天

    [LV.5]

    RISC-V最佳新人RISC-V活跃会员RISC-V热心会员RISC-V推广达人

    发表于 2020-6-12 13:33:24 | 显示全部楼层 |阅读模式

    成为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表示最高次项:


    1. void fp8(char gx[449], char(*f)[448])//根据生成多项式计算8位并行编码的矩阵F
    2. {
    3.         char ft[448][448];
    4.         int i, j, k;

    5.         memset(ft, 0, 448 * 448);//初始化,计算f1
    6.         for (i = 0;i < 448;i++)
    7.         {
    8.                 ft[i][0] = gx[i + 1];
    9.         }
    10.         for (i = 0;i < 447;i++)
    11.         {
    12.                 ft[i][i + 1] = 1;
    13.         }

    14.         for (k = 0;k < 7;k++)
    15.         {
    16.                 memset(f, 0, 448 * 448);
    17.                 for (i = 0;i < 448;i++)
    18.                 {
    19.                         for (j = 0;j < 448;j++)
    20.                         {
    21.                                 f[i][0] ^= ft[i][j] & gx[j + 1];
    22.                         }
    23.                 }
    24.                 for (i = 0;i < 448;i++)
    25.                 {
    26.                         for (j = 1;j < 448;j++)
    27.                         {
    28.                                 f[i][j] = ft[i][j - 1];
    29.                         }
    30.                 }
    31.                 memcpy_s(ft, 448 * 448, f, 448 * 448);
    32.         }
    33. }
    复制代码

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

    1. void f8code(char f[448][448])//将F矩阵以代码形式输出到文件
    2. {
    3.         FILE * wenjian;
    4.         int i, j;
    5.         int jia;
    6.         int kuohao;

    7.         fopen_s(&wenjian, "f8code.txt", "w");
    8.         if (wenjian)
    9.         {
    10.                 for (i = 0;i < 448;i++)
    11.                 {
    12.                         fprintf(wenjian, "r[%d] = ", i);
    13.                         jia = 0;
    14.                         kuohao = 0;
    15.                         for (j = 0;j < 448;j++)
    16.                         {
    17.                                 if (f[i][j])
    18.                                 {
    19.                                         if (jia++)
    20.                                         {
    21.                                                 fprintf(wenjian, " ^ ");
    22.                                         }
    23.                                         if ((kuohao & 0x01) == 0)
    24.                                         {
    25.                                                 fprintf(wenjian, "(");
    26.                                         }
    27.                                         if (j < 8)
    28.                                         {
    29.                                                 fprintf(wenjian, "s[%d]", j);
    30.                                         }
    31.                                         else
    32.                                         {
    33.                                                 fprintf(wenjian, "r[%d]", j);
    34.                                         }
    35.                                         if (kuohao++ & 0x01)
    36.                                         {
    37.                                                 fprintf(wenjian, ")");
    38.                                         }
    39.                                 }
    40.                         }
    41.                         if (kuohao & 0x01)
    42.                         {
    43.                                 fprintf(wenjian, ")");
    44.                         }
    45.                         fprintf(wenjian, ";\n");
    46.                 }
    47.                 fclose(wenjian);
    48.         }
    49. }
    复制代码

    输出的文件是这样的:

    1. void bch8(char in[8192], char out[8640])//BCH16383编码,32位纠错,8位并行处理
    2. {
    3.         char r[448] = { 0 };//r[0]表示r447
    4.         char s[8];//s[0]表示s0
    5.         int i, j;

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





    上一篇:Freedom E310简介
    下一篇:SEGGER---SiFive
    题主优质好文
    相信自已,未来是自已创造的。
    回复

    使用道具 举报

      离线 

  • TA的每日心情
    奋斗
    2021-3-3 12:35
  • 签到天数: 45 天

    [LV.5]

    RISC-V最佳新人RISC-V活跃会员RISC-V热心会员RISC-V推广达人

     楼主| 发表于 2020-6-13 20:49:39 | 显示全部楼层
    本帖最后由 小飞飞 于 2020-9-29 10:15 编辑

    大家可以用生成的代码替换掉中间那一大堆位运算代码,再修修头尾,就变成了所需要的BCH编码代码了,8位并行编码,位运算也适合大多数嵌入式平台和FPGA,效率非常高。


    二、解码-有限域乘法器


    其实,有限域乘法就是两个多项式相乘,然后将结果再变回到有限域的范围内,变换的方法就不详细描述了,网上一大堆介绍的。只要我们推导出两个多项式相乘的系数,就可以生成一个高效率的有限域乘法器。跟上面一样,我们肯定不会去手工推导的,借助代码的力量:

    1. void cfqcodex(int wei, char * B)//推导任意位数有限域乘法器计算公式,并以代码形式输出到文件中,输入位数和本源多项式
    2. {
    3.     int i, j, m, n;
    4.     FILE * wenjian;
    5.     char ** x;//X的0次到乘法最高位次对应的在有限域内的多项式
    6.     char t;
    7.     int jia;
    8.     int kuohao;
    9.     char wenjianming[256];

    10.     x = new char *[wei * 2 - 1];//根据位数分配内存
    11.     for (i = 0;i < (wei * 2 - 1);i++)
    12.     {
    13.         x[i] = new char[wei];
    14.         memset(x[i], 0, wei);
    15.     }
    16.     //先计算两个乘数相乘得到的多项式,然后将多项式变为有限域内的多项式,形成最终结果计算公式
    17.     x[0][0] = 1;
    18.     for (i = 1;i < (wei * 2 - 1);i++)
    19.     {
    20.         t = x[i - 1][wei - 1];
    21.         for (j = wei - 1;j > 0;j--)//将多项式移位
    22.         {
    23.             x[i][j] = x[i - 1][j - 1];
    24.         }
    25.         x[i][0] = 0;
    26.         if (t)//最高位是1,超出有限域范围,使用本源多项式处理
    27.         {
    28.             for (j = 0;j < wei;j++)
    29.             {
    30.                 x[i][j] ^= B[j];
    31.             }
    32.         }
    33.     }

    34.     sprintf_s(wenjianming, 256, "ChengCode%d.txt", wei);
    35.     fopen_s(&wenjian, wenjianming, "w");
    36.     if (wenjian)
    37.     {
    38.         fprintf(wenjian, "void Cheng_%d(char a[%d], char b[%d], char c[%d])//%d位有限域乘法,使用位运算实现,0下标表示最低位\n{\n", wei, wei, wei, wei, wei);
    39.         for (i = wei - 1;i >= 0;i--)
    40.         {
    41.             fprintf(wenjian, "\tc[%d]=", i);
    42.             jia = 0;
    43.             kuohao = 0;
    44.             for (j = (wei * 2 - 2);j >= 0;j--)
    45.             {
    46.                 if (x[j][i])//该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
    47.                 {
    48.                     for (m = 0;m < wei;m++)
    49.                     {
    50.                         for (n = 0;n < wei;n++)
    51.                         {
    52.                             if ((m + n) == j)//相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
    53.                             {
    54.                                 if (jia++)
    55.                                 {
    56.                                     fprintf(wenjian, " ^ ");
    57.                                 }
    58.                                 if ((kuohao & 0x01) == 0)
    59.                                 {
    60.                                     fprintf(wenjian, "(");
    61.                                 }
    62.                                 fprintf(wenjian, "(a[%d] & b[%d])", m, n);
    63.                                 if (kuohao++ & 0x01)
    64.                                 {
    65.                                     fprintf(wenjian, ")");
    66.                                 }
    67.                             }
    68.                         }
    69.                     }
    70.                 }
    71.             }
    72.             if (kuohao & 0x01)
    73.             {
    74.                 fprintf(wenjian, ")");
    75.             }
    76.             fprintf(wenjian, ";\n");
    77.         }
    78.         fprintf(wenjian, "}\n");
    79.         fclose(wenjian);
    80.     }
    81. }
    复制代码


    相信自已,未来是自已创造的。
    回复 支持 反对

    使用道具 举报

      离线 

  • TA的每日心情
    奋斗
    2021-3-3 12:35
  • 签到天数: 45 天

    [LV.5]

    RISC-V最佳新人RISC-V活跃会员RISC-V热心会员RISC-V推广达人

     楼主| 发表于 2020-6-13 20:56:12 | 显示全部楼层
    本帖最后由 小飞飞 于 2020-9-29 10:14 编辑

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

    生成的乘法器代码如下:

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

    1. void cscfqcode(void)推导14位有限域常数乘法器计算公式,常数为1-32次幂,并以代码形式输出到文件中
    2. {
    3.         int i, j, m, n, k;
    4.         FILE  wenjian;
    5.         char x[27][14] = { 0 };X的0次到26次对应的在有限域内的多项式
    6.         char t;
    7.         int jia;
    8.         int kuohao;
    9.         char a[14];保存当前幂次的数值
    10.         先计算两个乘数相乘得到的26次多项式,然后将26次多项式变为有限域内的多项式,形成最终结果计算公式
    11.         x[0][0] = 1;
    12.         for (i = 1;i  27;i++)
    13.         {
    14.                 t = x[i - 1][13];
    15.                 for (j = 13;j  0;j--)将多项式移位
    16.                 {
    17.                         x[i][j] = x[i - 1][j - 1];
    18.                 }
    19.                 x[i][0] = 0;
    20.                 if (t)最高位是1,超出有限域范围,使用本源多项式处理
    21.                 {
    22.                         x[i][10] ^= 0x01;
    23.                         x[i][6] ^= 0x01;
    24.                         x[i][1] ^= 0x01;
    25.                         x[i][0] ^= 0x01;
    26.                 }
    27.         }
    28.   
    29.         fopen_s(&wenjian, cschengcode.txt, w);
    30.         if (wenjian)
    31.         {
    32.                 for (k = 1;k = 32;k++)
    33.                 {
    34.                         fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法,使用位运算实现,0下标表示最低位nn, k);
    35.                 }
    36.                 for (k = 40;k = 512;k += 8)
    37.                 {
    38.                         fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法,使用位运算实现,0下标表示最低位nn, k);
    39.                 }
    40.                 for (k = 1;k = 32;k++)
    41.                 {
    42.                         fprintf(wenjian, void cheng%d(char b[14], char c[14]);14位有限域常数乘法,使用位运算实现,0下标表示最低位nn, (k  7743) % 16383);
    43.                 }
    44.                 for (k = 1;k = 32;k++)
    45.                 {
    46.                         fprintf(wenjian, void cheng%d(char b[14], char c[14])14位有限域常数乘法,使用位运算实现,0下标表示最低位n{n, k);
    47.                         for (i = 0;i  14;i++)
    48.                         {
    49.                                 a[i] = (ys[k]  i) & 0x01;
    50.                         }
    51.                         for (i = 13;i = 0;i--)
    52.                         {
    53.                                 fprintf(wenjian, tc[%d]=, i);
    54.                                 jia = 0;
    55.                                 kuohao = 0;
    56.                                 for (j = 26;j = 0;j--)
    57.                                 {
    58.                                         if (x[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
    59.                                         {
    60.                                                 for (m = 0;m  14;m++)
    61.                                                 {
    62.                                                         if (a[m] == 0)
    63.                                                         {
    64.                                                                 continue;
    65.                                                         }
    66.                                                         for (n = 0;n  14;n++)
    67.                                                         {
    68.                                                                 if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
    69.                                                                 {
    70.                                                                         if (jia++)
    71.                                                                         {
    72.                                                                                 fprintf(wenjian,  ^ );
    73.                                                                         }
    74.                                                                         if ((kuohao & 0x01) == 0)
    75.                                                                         {
    76.                                                                                 fprintf(wenjian, ();
    77.                                                                         }
    78.                                                                         fprintf(wenjian, b[%d], n);
    79.                                                                         if (kuohao++ & 0x01)
    80.                                                                         {
    81.                                                                                 fprintf(wenjian, ));
    82.                                                                         }
    83.                                                                 }
    84.                                                         }
    85.                                                 }
    86.                                         }
    87.                                 }
    88.                                 if (kuohao & 0x01)
    89.                                 {
    90.                                         fprintf(wenjian, ));
    91.                                 }
    92.                                 fprintf(wenjian, ;n);
    93.                         }
    94.                         fprintf(wenjian, }nn);
    95.                 }
    96.                 for (k = 40;k = 512;k += 8)
    97.                 {
    98.                         fprintf(wenjian, void cheng%d(char b[14], char c[14])14位有限域常数乘法,使用位运算实现,0下标表示最低位n{n, k);
    99.                         for (i = 0;i  14;i++)
    100.                         {
    101.                                 a[i] = (ys[k]  i) & 0x01;
    102.                         }
    103.                         for (i = 13;i = 0;i--)
    104.                         {
    105.                                 fprintf(wenjian, tc[%d]=, i);
    106.                                 jia = 0;
    107.                                 kuohao = 0;
    108.                                 for (j = 26;j = 0;j--)
    109.                                 {
    110.                                         if (x[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
    111.                                         {
    112.                                                 for (m = 0;m  14;m++)
    113.                                                 {
    114.                                                         if (a[m] == 0)
    115.                                                         {
    116.                                                                 continue;
    117.                                                         }
    118.                                                         for (n = 0;n  14;n++)
    119.                                                         {
    120.                                                                 if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
    121.                                                                 {
    122.                                                                         if (jia++)
    123.                                                                         {
    124.                                                                                 fprintf(wenjian,  ^ );
    125.                                                                         }
    126.                                                                         if ((kuohao & 0x01) == 0)
    127.                                                                         {
    128.                                                                                 fprintf(wenjian, ();
    129.                                                                         }
    130.                                                                         fprintf(wenjian, b[%d], n);
    131.                                                                         if (kuohao++ & 0x01)
    132.                                                                         {
    133.                                                                                 fprintf(wenjian, ));
    134.                                                                         }
    135.                                                                 }
    136.                                                         }
    137.                                                 }
    138.                                         }
    139.                                 }
    140.                                 if (kuohao & 0x01)
    141.                                 {
    142.                                         fprintf(wenjian, ));
    143.                                 }
    144.                                 fprintf(wenjian, ;n);
    145.                         }
    146.                         fprintf(wenjian, }nn);
    147.                 }
    148.                 for (k = 1;k = 32;k++)
    149.                 {
    150.                         fprintf(wenjian, void cheng%d(char b[14], char c[14])14位有限域常数乘法,使用位运算实现,0下标表示最低位n{n, (k  7743) % 16383);
    151.                         for (i = 0;i  14;i++)
    152.                         {
    153.                                 a[i] = (ys[(k  7743) % 16383]  i) & 0x01;
    154.                         }
    155.                         for (i = 13;i = 0;i--)
    156.                         {
    157.                                 fprintf(wenjian, tc[%d]=, i);
    158.                                 jia = 0;
    159.                                 kuohao = 0;
    160.                                 for (j = 26;j = 0;j--)
    161.                                 {
    162.                                         if (x[j][i])该项为1表示最终结果的第i次项的系数有中间结果的第j项系数
    163.                                         {
    164.                                                 for (m = 0;m  14;m++)
    165.                                                 {
    166.                                                         if (a[m] == 0)
    167.                                                         {
    168.                                                                 continue;
    169.                                                         }
    170.                                                         for (n = 0;n  14;n++)
    171.                                                         {
    172.                                                                 if ((m + n) == j)相等说明该中间结果系数包含两个乘数的第m项和第n项的系数乘积
    173.                                                                 {
    174.                                                                         if (jia++)
    175.                                                                         {
    176.                                                                                 fprintf(wenjian,  ^ );
    177.                                                                         }
    178.                                                                         if ((kuohao & 0x01) == 0)
    179.                                                                         {
    180.                                                                                 fprintf(wenjian, ();
    181.                                                                         }
    182.                                                                         fprintf(wenjian, b[%d], n);
    183.                                                                         if (kuohao++ & 0x01)
    184.                                                                         {
    185.                                                                                 fprintf(wenjian, ));
    186.                                                                         }
    187.                                                                 }
    188.                                                         }
    189.                                                 }
    190.                                         }
    191.                                 }
    192.                                 if (kuohao & 0x01)
    193.                                 {
    194.                                         fprintf(wenjian, ));
    195.                                 }
    196.                                 fprintf(wenjian, ;n);
    197.                         }
    198.                         fprintf(wenjian, }nn);
    199.                 }
    200.                 for (k = 0;k  32;k++)
    201.                 {
    202.                         fprintf(wenjian, tcheng%d(elp[%d], c);n, ((k + 1)  7743) % 16383, k);
    203.                         fprintf(wenjian, tfor (i = 0;i  14;i++)n);
    204.                         fprintf(wenjian, t{nttelp[%d][i] = c[i];nt}n, k);
    205.                 }
    206.                 fclose(wenjian);
    207.         }
    208. }
    复制代码

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


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

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


    1. {
    2.     int i;

    3.     ys[0] = 1;
    4.     ys2[0] = -1;
    5.     ys2[1] = 0;
    6.     for (i = 1;i < 16383;i++)//根据本源多项式生成有限域上的所有元素
    7.     {
    8.         ys = ys[i - 1] << 1;
    9.         if (ys & 0xffffc000)//移位后超出有限域范围则使用本源多项式进行处理
    10.         {
    11.             ys = (ys & 0x00003fff) ^ 1091;//1091为本源多项式去掉最高位后的值
    12.         }
    13.         ys2[ys] = i;
    14.     }
    15. }
    复制代码

    这段代码可以很容易修改成其它有限域的乘法表,使用前需要先定义两个全局数组变量作为表格存放的地方。


    三、解码-伴随式计算


    伴随式的计算使用了第一篇文章里提到的Homer迭代法,利用之前造好的两张表,我们可以很方便的得到所需的全部Homer:


    1. void homercode(void)//Homer迭代法处理流程推导,输入8位数据输出14位,以代码形式输出到文件
    2. {
    3.     int i, j, k;
    4.     FILE * wenjian;
    5.     int jia;

    6.     fopen_s(&wenjian, "homercode.txt", "w");
    7.     if (wenjian)
    8.     {
    9.         for (i = 1;i <= 64;i++)
    10.         {
    11.             fprintf(wenjian, "void homer%d(char r[8], char t[14])//将8位输入转换为14位,0下标表示最低位\n{\n", i);
    12.             for (j = 0;j < 14;j++)
    13.             {
    14.                 fprintf(wenjian, "\tt[%d]=", j);
    15.                 jia = 0;
    16.                 for (k = 0;k < 8;k++)
    17.                 {
    18.                     if ((ys[k * i] >> j) & 0x01)
    19.                     {
    20.                         if (jia++)
    21.                         {
    22.                             fprintf(wenjian, " ^ ");
    23.                         }
    24.                         fprintf(wenjian, "r[%d]", 7 - k);
    25.                     }
    26.                 }
    27.                 if (jia == 0)//一个符合条件的元素都没有,直接赋值0
    28.                 {
    29.                     fprintf(wenjian, "0;\n");
    30.                 }
    31.                 else
    32.                 {
    33.                     fprintf(wenjian, ";\n");
    34.                 }
    35.             }
    36.             fprintf(wenjian, "}\n\n");
    37.         }
    38.         for (i = 1;i <= 64;i++)
    39.         {
    40.             fprintf(wenjian, "\t\thomer%d(r + (j << 3), t);\n", i);
    41.             fprintf(wenjian, "\t\tcheng%d(s[%d], c);\n", i << 3, i - 1);
    42.             fprintf(wenjian, "\t\tfor (i = 0;i < 14;i++)\n");
    43.             fprintf(wenjian, "\t\t{\n\t\t\ts[%d][i] = t[i] ^ c[i];\n\t\t}\n", i - 1);
    44.         }
    45.         fclose(wenjian);
    46.     }
    47. }
    复制代码

    相信自已,未来是自已创造的。
    回复 支持 反对

    使用道具 举报

      离线 

  • TA的每日心情
    奋斗
    2021-3-3 12:35
  • 签到天数: 45 天

    [LV.5]

    RISC-V最佳新人RISC-V活跃会员RISC-V热心会员RISC-V推广达人

     楼主| 发表于 2020-6-13 21:03:55 | 显示全部楼层
    本帖最后由 小飞飞 于 2020-9-29 10:12 编辑

    生成的文件上半部分是64的Homer接口函数,下半部分则是伴随式计算的使用代码,待会我们就会看到他们。这个计算方法不是最简单的,但是比较容易理解和实现,因此我也选择了这种算法。最终的伴随式代码如下:
    1. void bss8(char r[8640], char s[64][14])//伴随式计算,8位并行,输入的0下标表示最高位,输出的伴随式的0下标表示最低位
    2. {
    3.     int i, j;
    4.     char t[14] = { 0 };//除参数r外,所有数组均为0下标表示最低位
    5.     char c[14] = { 0 };

    6.     memset(s, 0, 64 * 14);
    7.     for (j = 0;j < 1080;j++)//每次迭代处理8位数据,分别使用64个不同的伴随式处理模块计算1-64个伴随式的值
    8.     {
    9.         homer1(r + (j << 3), t);
    10.         cheng8(s[0], c);
    11.         for (i = 0;i < 14;i++)
    12.         {
    13.             s[0][i] = t[i] ^ c[i];
    14.         }
    15.         homer2(r + (j << 3), t);
    16.         cheng16(s[1], c);
    17.         for (i = 0;i < 14;i++)
    18.         {
    19.             s[1][i] = t[i] ^ c[i];
    20.         }
    21.         homer3(r + (j << 3), t);
    22.         cheng24(s[2], c);
    23.         for (i = 0;i < 14;i++)
    24.         {
    25.             s[2][i] = t[i] ^ c[i];
    26.         }
    27.         homer4(r + (j << 3), t);
    28.         cheng32(s[3], c);
    29.         for (i = 0;i < 14;i++)
    30.         {
    31.             s[3][i] = t[i] ^ c[i];
    32.         }
    33.         homer5(r + (j << 3), t);
    34.         cheng40(s[4], c);
    35.         for (i = 0;i < 14;i++)
    36.         {
    37.             s[4][i] = t[i] ^ c[i];
    38.         }
    39.         homer6(r + (j << 3), t);
    40.         cheng48(s[5], c);
    41.         for (i = 0;i < 14;i++)
    42.         {
    43.             s[5][i] = t[i] ^ c[i];
    44.         }
    45.         homer7(r + (j << 3), t);
    46.         cheng56(s[6], c);
    47.         for (i = 0;i < 14;i++)
    48.         {
    49.             s[6][i] = t[i] ^ c[i];
    50.         }
    51.         homer8(r + (j << 3), t);
    52.         cheng64(s[7], c);
    53.         for (i = 0;i < 14;i++)
    54.         {
    55.             s[7][i] = t[i] ^ c[i];
    56.         }
    57.         homer9(r + (j << 3), t);
    58.         cheng72(s[8], c);
    59.         for (i = 0;i < 14;i++)
    60.         {
    61.             s[8][i] = t[i] ^ c[i];
    62.         }
    63.         homer10(r + (j << 3), t);
    64.         cheng80(s[9], c);
    65.         for (i = 0;i < 14;i++)
    66.         {
    67.             s[9][i] = t[i] ^ c[i];
    68.         }
    69.         homer11(r + (j << 3), t);
    70.         cheng88(s[10], c);
    71.         for (i = 0;i < 14;i++)
    72.         {
    73.             s[10][i] = t[i] ^ c[i];
    74.         }
    75.         homer12(r + (j << 3), t);
    76.         cheng96(s[11], c);
    77.         for (i = 0;i < 14;i++)
    78.         {
    79.             s[11][i] = t[i] ^ c[i];
    80.         }
    81.         homer13(r + (j << 3), t);
    82.         cheng104(s[12], c);
    83.         for (i = 0;i < 14;i++)
    84.         {
    85.             s[12][i] = t[i] ^ c[i];
    86.         }
    87.         homer14(r + (j << 3), t);
    88.         cheng112(s[13], c);
    89.         for (i = 0;i < 14;i++)
    90.         {
    91.             s[13][i] = t[i] ^ c[i];
    92.         }
    93.         homer15(r + (j << 3), t);
    94.         cheng120(s[14], c);
    95.         for (i = 0;i < 14;i++)
    96.         {
    97.             s[14][i] = t[i] ^ c[i];
    98.         }
    99.         homer16(r + (j << 3), t);
    100.         cheng128(s[15], c);
    101.         for (i = 0;i < 14;i++)
    102.         {
    103.             s[15][i] = t[i] ^ c[i];
    104.         }
    105.         homer17(r + (j << 3), t);
    106.         cheng136(s[16], c);
    107.         for (i = 0;i < 14;i++)
    108.         {
    109.             s[16][i] = t[i] ^ c[i];
    110.         }
    111.         homer18(r + (j << 3), t);
    112.         cheng144(s[17], c);
    113.         for (i = 0;i < 14;i++)
    114.         {
    115.             s[17][i] = t[i] ^ c[i];
    116.         }
    117.         homer19(r + (j << 3), t);
    118.         cheng152(s[18], c);
    119.         for (i = 0;i < 14;i++)
    120.         {
    121.             s[18][i] = t[i] ^ c[i];
    122.         }
    123.         homer20(r + (j << 3), t);
    124.         cheng160(s[19], c);
    125.         for (i = 0;i < 14;i++)
    126.         {
    127.             s[19][i] = t[i] ^ c[i];
    128.         }
    129.         homer21(r + (j << 3), t);
    130.         cheng168(s[20], c);
    131.         for (i = 0;i < 14;i++)
    132.         {
    133.             s[20][i] = t[i] ^ c[i];
    134.         }
    135.         homer22(r + (j << 3), t);
    136.         cheng176(s[21], c);
    137.         for (i = 0;i < 14;i++)
    138.         {
    139.             s[21][i] = t[i] ^ c[i];
    140.         }
    141.         homer23(r + (j << 3), t);
    142.         cheng184(s[22], c);
    143.         for (i = 0;i < 14;i++)
    144.         {
    145.             s[22][i] = t[i] ^ c[i];
    146.         }
    147.         homer24(r + (j << 3), t);
    148.         cheng192(s[23], c);
    149.         for (i = 0;i < 14;i++)
    150.         {
    151.             s[23][i] = t[i] ^ c[i];
    152.         }
    153.         homer25(r + (j << 3), t);
    154.         cheng200(s[24], c);
    155.         for (i = 0;i < 14;i++)
    156.         {
    157.             s[24][i] = t[i] ^ c[i];
    158.         }
    159.         homer26(r + (j << 3), t);
    160.         cheng208(s[25], c);
    161.         for (i = 0;i < 14;i++)
    162.         {
    163.             s[25][i] = t[i] ^ c[i];
    164.         }
    165.         homer27(r + (j << 3), t);
    166.         cheng216(s[26], c);
    167.         for (i = 0;i < 14;i++)
    168.         {
    169.             s[26][i] = t[i] ^ c[i];
    170.         }
    171.         homer28(r + (j << 3), t);
    172.         cheng224(s[27], c);
    173.         for (i = 0;i < 14;i++)
    174.         {
    175.             s[27][i] = t[i] ^ c[i];
    176.         }
    177.         homer29(r + (j << 3), t);
    178.         cheng232(s[28], c);
    179.         for (i = 0;i < 14;i++)
    180.         {
    181.             s[28][i] = t[i] ^ c[i];
    182.         }
    183.         homer30(r + (j << 3), t);
    184.         cheng240(s[29], c);
    185.         for (i = 0;i < 14;i++)
    186.         {
    187.             s[29][i] = t[i] ^ c[i];
    188.         }
    189.         homer31(r + (j << 3), t);
    190.         cheng248(s[30], c);
    191.         for (i = 0;i < 14;i++)
    192.         {
    193.             s[30][i] = t[i] ^ c[i];
    194.         }
    195.         homer32(r + (j << 3), t);
    196.         cheng256(s[31], c);
    197.         for (i = 0;i < 14;i++)
    198.         {
    199.             s[31][i] = t[i] ^ c[i];
    200.         }
    201.         homer33(r + (j << 3), t);
    202.         cheng264(s[32], c);
    203.         for (i = 0;i < 14;i++)
    204.         {
    205.             s[32][i] = t[i] ^ c[i];
    206.         }
    207.         homer34(r + (j << 3), t);
    208.         cheng272(s[33], c);
    209.         for (i = 0;i < 14;i++)
    210.         {
    211.             s[33][i] = t[i] ^ c[i];
    212.         }
    213.         homer35(r + (j << 3), t);
    214.         cheng280(s[34], c);
    215.         for (i = 0;i < 14;i++)
    216.         {
    217.             s[34][i] = t[i] ^ c[i];
    218.         }
    219.         homer36(r + (j << 3), t);
    220.         cheng288(s[35], c);
    221.         for (i = 0;i < 14;i++)
    222.         {
    223.             s[35][i] = t[i] ^ c[i];
    224.         }
    225.         homer37(r + (j << 3), t);
    226.         cheng296(s[36], c);
    227.         for (i = 0;i < 14;i++)
    228.         {
    229.             s[36][i] = t[i] ^ c[i];
    230.         }
    231.         homer38(r + (j << 3), t);
    232.         cheng304(s[37], c);
    233.         for (i = 0;i < 14;i++)
    234.         {
    235.             s[37][i] = t[i] ^ c[i];
    236.         }
    237.         homer39(r + (j << 3), t);
    238.         cheng312(s[38], c);
    239.         for (i = 0;i < 14;i++)
    240.         {
    241.             s[38][i] = t[i] ^ c[i];
    242.         }
    243.         homer40(r + (j << 3), t);
    244.         cheng320(s[39], c);
    245.         for (i = 0;i < 14;i++)
    246.         {
    247.             s[39][i] = t[i] ^ c[i];
    248.         }
    249.         homer41(r + (j << 3), t);
    250.         cheng328(s[40], c);
    251.         for (i = 0;i < 14;i++)
    252.         {
    253.             s[40][i] = t[i] ^ c[i];
    254.         }
    255.         homer42(r + (j << 3), t);
    256.         cheng336(s[41], c);
    257.         for (i = 0;i < 14;i++)
    258.         {
    259.             s[41][i] = t[i] ^ c[i];
    260.         }
    261.         homer43(r + (j << 3), t);
    262.         cheng344(s[42], c);
    263.         for (i = 0;i < 14;i++)
    264.         {
    265.             s[42][i] = t[i] ^ c[i];
    266.         }
    267.         homer44(r + (j << 3), t);
    268.         cheng352(s[43], c);
    269.         for (i = 0;i < 14;i++)
    270.         {
    271.             s[43][i] = t[i] ^ c[i];
    272.         }
    273.         homer45(r + (j << 3), t);
    274.         cheng360(s[44], c);
    275.         for (i = 0;i < 14;i++)
    276.         {
    277.             s[44][i] = t[i] ^ c[i];
    278.         }
    279.         homer46(r + (j << 3), t);
    280.         cheng368(s[45], c);
    281.         for (i = 0;i < 14;i++)
    282.         {
    283.             s[45][i] = t[i] ^ c[i];
    284.         }
    285.         homer47(r + (j << 3), t);
    286.         cheng376(s[46], c);
    287.         for (i = 0;i < 14;i++)
    288.         {
    289.             s[46][i] = t[i] ^ c[i];
    290.         }
    291.         homer48(r + (j << 3), t);
    292.         cheng384(s[47], c);
    293.         for (i = 0;i < 14;i++)
    294.         {
    295.             s[47][i] = t[i] ^ c[i];
    296.         }
    297.         homer49(r + (j << 3), t);
    298.         cheng392(s[48], c);
    299.         for (i = 0;i < 14;i++)
    300.         {
    301.             s[48][i] = t[i] ^ c[i];
    302.         }
    303.         homer50(r + (j << 3), t);
    304.         cheng400(s[49], c);
    305.         for (i = 0;i < 14;i++)
    306.         {
    307.             s[49][i] = t[i] ^ c[i];
    308.         }
    309.         homer51(r + (j << 3), t);
    310.         cheng408(s[50], c);
    311.         for (i = 0;i < 14;i++)
    312.         {
    313.             s[50][i] = t[i] ^ c[i];
    314.         }
    315.         homer52(r + (j << 3), t);
    316.         cheng416(s[51], c);
    317.         for (i = 0;i < 14;i++)
    318.         {
    319.             s[51][i] = t[i] ^ c[i];
    320.         }
    321.         homer53(r + (j << 3), t);
    322.         cheng424(s[52], c);
    323.         for (i = 0;i < 14;i++)
    324.         {
    325.             s[52][i] = t[i] ^ c[i];
    326.         }
    327.         homer54(r + (j << 3), t);
    328.         cheng432(s[53], c);
    329.         for (i = 0;i < 14;i++)
    330.         {
    331.             s[53][i] = t[i] ^ c[i];
    332.         }
    333.         homer55(r + (j << 3), t);
    334.         cheng440(s[54], c);
    335.         for (i = 0;i < 14;i++)
    336.         {
    337.             s[54][i] = t[i] ^ c[i];
    338.         }
    339.         homer56(r + (j << 3), t);
    340.         cheng448(s[55], c);
    341.         for (i = 0;i < 14;i++)
    342.         {
    343.             s[55][i] = t[i] ^ c[i];
    344.         }
    345.         homer57(r + (j << 3), t);
    346.         cheng456(s[56], c);
    347.         for (i = 0;i < 14;i++)
    348.         {
    349.             s[56][i] = t[i] ^ c[i];
    350.         }
    351.         homer58(r + (j << 3), t);
    352.         cheng464(s[57], c);
    353.         for (i = 0;i < 14;i++)
    354.         {
    355.             s[57][i] = t[i] ^ c[i];
    356.         }
    357.         homer59(r + (j << 3), t);
    358.         cheng472(s[58], c);
    359.         for (i = 0;i < 14;i++)
    360.         {
    361.             s[58][i] = t[i] ^ c[i];
    362.         }
    363.         homer60(r + (j << 3), t);
    364.         cheng480(s[59], c);
    365.         for (i = 0;i < 14;i++)
    366.         {
    367.             s[59][i] = t[i] ^ c[i];
    368.         }
    369.         homer61(r + (j << 3), t);
    370.         cheng488(s[60], c);
    371.         for (i = 0;i < 14;i++)
    372.         {
    373.             s[60][i] = t[i] ^ c[i];
    374.         }
    375.         homer62(r + (j << 3), t);
    376.         cheng496(s[61], c);
    377.         for (i = 0;i < 14;i++)
    378.         {
    379.             s[61][i] = t[i] ^ c[i];
    380.         }
    381.         homer63(r + (j << 3), t);
    382.         cheng504(s[62], c);
    383.         for (i = 0;i < 14;i++)
    384.         {
    385.             s[62][i] = t[i] ^ c[i];
    386.         }
    387.         homer64(r + (j << 3), t);
    388.         cheng512(s[63], c);
    389.         for (i = 0;i < 14;i++)
    390.         {
    391.             s[63][i] = t[i] ^ c[i];
    392.         }
    393.     }
    394. }
    复制代码


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

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


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


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

    1. void cw8(char s[64][14], char e[33][14])//根据伴随式计算错误多项式,使用SIBM算法,只需迭代t次,输入伴随式,输出最高次为t的错误多项式
    2. {
    3.     int i, j, k;
    4.     char d[14];
    5.     char dq[14] = { 0 };//所有数组均使用0下标表示最低位
    6.     char t[33][14] = { 0 };
    7.     char b[33][14] = { 0 };
    8.     char elp[33][14] = { 0 };
    9.     char st[33][14] = { 0 };
    10.     char c[14] = { 0 };
    11.     char c2[14] = { 0 };

    12.     memcpy_s(d, 14, s[0], 14);
    13.     dq[0] = 1;
    14.     b[0][0] = 1;
    15.     elp[0][0] = 1;
    16.     memset(e, 0, 33 * 14);

    17.     for (j = 1;j <= 32;j++)
    18.     {
    19.         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
    20.         {
    21.             if (j == 1)
    22.             {
    23.                 memcpy_s(elp[1], 14, s[0], 14);//其余不需要修改,都是1
    24.             }
    25.             else
    26.             {
    27.                 memcpy_s(t[0], 14, elp[0], 14);
    28.                 memcpy_s(t[1], 14, elp[1], 14);
    29.                 chengchar(dq, elp[0], c);//0次项和1次项只和e(x)有关
    30.                 memcpy_s(elp[0], 14, c, 14);
    31.                 chengchar(dq, elp[1], c);
    32.                 memcpy_s(elp[1], 14, c, 14);
    33.                 for (i = 2;i < 33;i++)//e(x)=dq*e(x)+d*x^2*b(x)
    34.                 {
    35.                     memcpy_s(t[i], 14, elp[i], 14);
    36.                     chengchar(dq, elp[i], c);
    37.                     chengchar(d, b[i - 2], c2);
    38.                     for (k = 0;k < 14;k++)
    39.                     {
    40.                         elp[i][k] = c[k] ^ c2[k];
    41.                     }
    42.                 }
    43.                 for (i = 0;i < 33;i++)//B(x)=e(x)
    44.                 {
    45.                     memcpy_s(b[i], 14, t[i], 14);
    46.                 }
    47.             }
    48.             memcpy_s(dq, 14, d, 14);
    49.         }
    50.         else
    51.         {
    52.             for (i = 32;i > 1;i--)//B(x)=x^2*B(x),dq和e(x)不变,无需修改
    53.             {
    54.                 memcpy_s(b[i], 14, b[i - 2], 14);
    55.             }
    56.             memset(b[0], 0, 14);
    57.             memset(b[1], 0, 14);
    58.         }

    59.         if (j < 32)//最后一次不迭代,没有意义,实际上最后一个伴随式的值没有用到
    60.         {
    61.             memset(d, 0, 14);//为便于硬件实现,这里每次都做32次运算,由于0乘任何数均为0,0异或任何数均不变,因此不影响结果
    62.             for (i = 32;i > 1;i--)
    63.             {
    64.                 memcpy_s(st[i], 14, st[i - 2], 14);//全部右移2位
    65.             }
    66.             memcpy_s(st[0], 14, s[(j << 1)], 14);
    67.             memcpy_s(st[1], 14, s[(j << 1) - 1], 14);
    68.             for (i = 0;i < 33;i++)
    69.             {
    70.                 chengchar(st[i], elp[i], c);
    71.                 for (k = 0;k < 14;k++)
    72.                 {
    73.                     d[k] ^= c[k];
    74.                 }
    75.             }
    76.         }
    77.     }
    78.     memcpy_s(e, 14 * 33, elp, 14 * 33);
    79. }
    复制代码

    输入之前计算得到的64个伴随式,输出33个错误多项式,特别说明一下,因为我们的纠错能力是32位,因此错误多项式的最高次项是32次,加上常数项,一共就有33项,这里千万不要漏掉一项,不然会造成纠错能力下降1位的。



    获取了错误多项式后,如果最高次项为0,那么错误位数小于32位,错误多项式的最高次项的次数就是错误的总比特数,同时我们可以根据错误多项式查找具体的错误位置。


    五、解码-钱搜索

    钱搜索是目前BCH最常用的错误位置求取方法,该方法本质上就是穷举所有的出错可能,并根据结果判断是否正确。



    虽然原理粗浅,但是目前最实用的一种方法。


    前面已经说到,对于8192的数据,我们实际上用的是16383的码,只是前面的数据都视为0或者视为1了,因此,在搜索时,我们需要先跳转到全0或全1搜索到数据开始位置时的搜索状态,也就是对每一个搜索项做一个乘法。具体代码如下:

    1. void ss8(char r[8640], char e[33][14], char out[8192])//错误搜索,使用钱搜索方法,输入接收到的数据和错误多项式,输出正确的数据
    2. {
    3.     char elp[32][14];
    4.     int i, j, k;
    5.     char s[14] = { 0 };//除r和out外,所有数组均使用0下标表示最低位
    6.     char c[14] = { 0 };

    7.     memcpy_s(elp, 14 * 32, e + 1, 14 * 32);
    8.     cheng7743(elp[0], c);//初始化处理,由于是缩短码,需要将错误多项式全部乘以a的一定幂次,以便从中间开始
    9.     for (i = 0;i < 14;i++)
    10.     {
    11.         elp[0][i] = c[i];
    12.     }
    13.     cheng15486(elp[1], c);
    14.     for (i = 0;i < 14;i++)
    15.     {
    16.         elp[1][i] = c[i];
    17.     }
    18.     cheng6846(elp[2], c);
    19.     for (i = 0;i < 14;i++)
    20.     {
    21.         elp[2][i] = c[i];
    22.     }
    23.     cheng14589(elp[3], c);
    24.     for (i = 0;i < 14;i++)
    25.     {
    26.         elp[3][i] = c[i];
    27.     }
    28.     cheng5949(elp[4], c);
    29.     for (i = 0;i < 14;i++)
    30.     {
    31.         elp[4][i] = c[i];
    32.     }
    33.     cheng13692(elp[5], c);
    34.     for (i = 0;i < 14;i++)
    35.     {
    36.         elp[5][i] = c[i];
    37.     }
    38.     cheng5052(elp[6], c);
    39.     for (i = 0;i < 14;i++)
    40.     {
    41.         elp[6][i] = c[i];
    42.     }
    43.     cheng12795(elp[7], c);
    44.     for (i = 0;i < 14;i++)
    45.     {
    46.         elp[7][i] = c[i];
    47.     }
    48.     cheng4155(elp[8], c);
    49.     for (i = 0;i < 14;i++)
    50.     {
    51.         elp[8][i] = c[i];
    52.     }
    53.     cheng11898(elp[9], c);
    54.     for (i = 0;i < 14;i++)
    55.     {
    56.         elp[9][i] = c[i];
    57.     }
    58.     cheng3258(elp[10], c);
    59.     for (i = 0;i < 14;i++)
    60.     {
    61.         elp[10][i] = c[i];
    62.     }
    63.     cheng11001(elp[11], c);
    64.     for (i = 0;i < 14;i++)
    65.     {
    66.         elp[11][i] = c[i];
    67.     }
    68.     cheng2361(elp[12], c);
    69.     for (i = 0;i < 14;i++)
    70.     {
    71.         elp[12][i] = c[i];
    72.     }
    73.     cheng10104(elp[13], c);
    74.     for (i = 0;i < 14;i++)
    75.     {
    76.         elp[13][i] = c[i];
    77.     }
    78.     cheng1464(elp[14], c);
    79.     for (i = 0;i < 14;i++)
    80.     {
    81.         elp[14][i] = c[i];
    82.     }
    83.     cheng9207(elp[15], c);
    84.     for (i = 0;i < 14;i++)
    85.     {
    86.         elp[15][i] = c[i];
    87.     }
    88.     cheng567(elp[16], c);
    89.     for (i = 0;i < 14;i++)
    90.     {
    91.         elp[16][i] = c[i];
    92.     }
    93.     cheng8310(elp[17], c);
    94.     for (i = 0;i < 14;i++)
    95.     {
    96.         elp[17][i] = c[i];
    97.     }
    98.     cheng16053(elp[18], c);
    99.     for (i = 0;i < 14;i++)
    100.     {
    101.         elp[18][i] = c[i];
    102.     }
    103.     cheng7413(elp[19], c);
    104.     for (i = 0;i < 14;i++)
    105.     {
    106.         elp[19][i] = c[i];
    107.     }
    108.     cheng15156(elp[20], c);
    109.     for (i = 0;i < 14;i++)
    110.     {
    111.         elp[20][i] = c[i];
    112.     }
    113.     cheng6516(elp[21], c);
    114.     for (i = 0;i < 14;i++)
    115.     {
    116.         elp[21][i] = c[i];
    117.     }
    118.     cheng14259(elp[22], c);
    119.     for (i = 0;i < 14;i++)
    120.     {
    121.         elp[22][i] = c[i];
    122.     }
    123.     cheng5619(elp[23], c);
    124.     for (i = 0;i < 14;i++)
    125.     {
    126.         elp[23][i] = c[i];
    127.     }
    128.     cheng13362(elp[24], c);
    129.     for (i = 0;i < 14;i++)
    130.     {
    131.         elp[24][i] = c[i];
    132.     }
    133.     cheng4722(elp[25], c);
    134.     for (i = 0;i < 14;i++)
    135.     {
    136.         elp[25][i] = c[i];
    137.     }
    138.     cheng12465(elp[26], c);
    139.     for (i = 0;i < 14;i++)
    140.     {
    141.         elp[26][i] = c[i];
    142.     }
    143.     cheng3825(elp[27], c);
    144.     for (i = 0;i < 14;i++)
    145.     {
    146.         elp[27][i] = c[i];
    147.     }
    148.     cheng11568(elp[28], c);
    149.     for (i = 0;i < 14;i++)
    150.     {
    151.         elp[28][i] = c[i];
    152.     }
    153.     cheng2928(elp[29], c);
    154.     for (i = 0;i < 14;i++)
    155.     {
    156.         elp[29][i] = c[i];
    157.     }
    158.     cheng10671(elp[30], c);
    159.     for (i = 0;i < 14;i++)
    160.     {
    161.         elp[30][i] = c[i];
    162.     }
    163.     cheng2031(elp[31], c);
    164.     for (i = 0;i < 14;i++)
    165.     {
    166.         elp[31][i] = c[i];
    167.     }

    168.     for (j = 0;j < 1024;j++)
    169.     {
    170.         for (k = 0;k < 8;k++)//这里仍然是串行,但在硬件实现时可以将该循环并行化,实现8位并行处理
    171.         {
    172.             cheng1(elp[0], c);//乘以对应幂次
    173.             for (i = 0;i < 14;i++)
    174.             {
    175.                 elp[0][i] = c[i];
    176.             }
    177.             cheng2(elp[1], c);
    178.             for (i = 0;i < 14;i++)
    179.             {
    180.                 elp[1][i] = c[i];
    181.             }
    182.             cheng3(elp[2], c);
    183.             for (i = 0;i < 14;i++)
    184.             {
    185.                 elp[2][i] = c[i];
    186.             }
    187.             cheng4(elp[3], c);
    188.             for (i = 0;i < 14;i++)
    189.             {
    190.                 elp[3][i] = c[i];
    191.             }
    192.             cheng5(elp[4], c);
    193.             for (i = 0;i < 14;i++)
    194.             {
    195.                 elp[4][i] = c[i];
    196.             }
    197.             cheng6(elp[5], c);
    198.             for (i = 0;i < 14;i++)
    199.             {
    200.                 elp[5][i] = c[i];
    201.             }
    202.             cheng7(elp[6], c);
    203.             for (i = 0;i < 14;i++)
    204.             {
    205.                 elp[6][i] = c[i];
    206.             }
    207.             cheng8(elp[7], c);
    208.             for (i = 0;i < 14;i++)
    209.             {
    210.                 elp[7][i] = c[i];
    211.             }
    212.             cheng9(elp[8], c);
    213.             for (i = 0;i < 14;i++)
    214.             {
    215.                 elp[8][i] = c[i];
    216.             }
    217.             cheng10(elp[9], c);
    218.             for (i = 0;i < 14;i++)
    219.             {
    220.                 elp[9][i] = c[i];
    221.             }
    222.             cheng11(elp[10], c);
    223.             for (i = 0;i < 14;i++)
    224.             {
    225.                 elp[10][i] = c[i];
    226.             }
    227.             cheng12(elp[11], c);
    228.             for (i = 0;i < 14;i++)
    229.             {
    230.                 elp[11][i] = c[i];
    231.             }
    232.             cheng13(elp[12], c);
    233.             for (i = 0;i < 14;i++)
    234.             {
    235.                 elp[12][i] = c[i];
    236.             }
    237.             cheng14(elp[13], c);
    238.             for (i = 0;i < 14;i++)
    239.             {
    240.                 elp[13][i] = c[i];
    241.             }
    242.             cheng15(elp[14], c);
    243.             for (i = 0;i < 14;i++)
    244.             {
    245.                 elp[14][i] = c[i];
    246.             }
    247.             cheng16(elp[15], c);
    248.             for (i = 0;i < 14;i++)
    249.             {
    250.                 elp[15][i] = c[i];
    251.             }
    252.             cheng17(elp[16], c);
    253.             for (i = 0;i < 14;i++)
    254.             {
    255.                 elp[16][i] = c[i];
    256.             }
    257.             cheng18(elp[17], c);
    258.             for (i = 0;i < 14;i++)
    259.             {
    260.                 elp[17][i] = c[i];
    261.             }
    262.             cheng19(elp[18], c);
    263.             for (i = 0;i < 14;i++)
    264.             {
    265.                 elp[18][i] = c[i];
    266.             }
    267.             cheng20(elp[19], c);
    268.             for (i = 0;i < 14;i++)
    269.             {
    270.                 elp[19][i] = c[i];
    271.             }
    272.             cheng21(elp[20], c);
    273.             for (i = 0;i < 14;i++)
    274.             {
    275.                 elp[20][i] = c[i];
    276.             }
    277.             cheng22(elp[21], c);
    278.             for (i = 0;i < 14;i++)
    279.             {
    280.                 elp[21][i] = c[i];
    281.             }
    282.             cheng23(elp[22], c);
    283.             for (i = 0;i < 14;i++)
    284.             {
    285.                 elp[22][i] = c[i];
    286.             }
    287.             cheng24(elp[23], c);
    288.             for (i = 0;i < 14;i++)
    289.             {
    290.                 elp[23][i] = c[i];
    291.             }
    292.             cheng25(elp[24], c);
    293.             for (i = 0;i < 14;i++)
    294.             {
    295.                 elp[24][i] = c[i];
    296.             }
    297.             cheng26(elp[25], c);
    298.             for (i = 0;i < 14;i++)
    299.             {
    300.                 elp[25][i] = c[i];
    301.             }
    302.             cheng27(elp[26], c);
    303.             for (i = 0;i < 14;i++)
    304.             {
    305.                 elp[26][i] = c[i];
    306.             }
    307.             cheng28(elp[27], c);
    308.             for (i = 0;i < 14;i++)
    309.             {
    310.                 elp[27][i] = c[i];
    311.             }
    312.             cheng29(elp[28], c);
    313.             for (i = 0;i < 14;i++)
    314.             {
    315.                 elp[28][i] = c[i];
    316.             }
    317.             cheng30(elp[29], c);
    318.             for (i = 0;i < 14;i++)
    319.             {
    320.                 elp[29][i] = c[i];
    321.             }
    322.             cheng31(elp[30], c);
    323.             for (i = 0;i < 14;i++)
    324.             {
    325.                 elp[30][i] = c[i];
    326.             }
    327.             cheng32(elp[31], c);
    328.             for (i = 0;i < 14;i++)
    329.             {
    330.                 elp[31][i] = c[i];
    331.             }
    332.             memcpy_s(s, 14, e[0], 14);
    333.             for (i = 0;i < 32;i++)
    334.             {
    335.                 s[0] ^= elp[i][0];
    336.                 s[1] ^= elp[i][1];
    337.                 s[2] ^= elp[i][2];
    338.                 s[3] ^= elp[i][3];
    339.                 s[4] ^= elp[i][4];
    340.                 s[5] ^= elp[i][5];
    341.                 s[6] ^= elp[i][6];
    342.                 s[7] ^= elp[i][7];
    343.                 s[8] ^= elp[i][8];
    344.                 s[9] ^= elp[i][9];
    345.                 s[10] ^= elp[i][10];
    346.                 s[11] ^= elp[i][11];
    347.                 s[12] ^= elp[i][12];
    348.                 s[13] ^= elp[i][13];
    349.             }
    350.             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])
    351.             {
    352.                 out[(j << 3) + k] = r[(j << 3) + k];
    353.             }
    354.             else
    355.             {
    356.                 out[(j << 3) + k] = r[(j << 3) + k] ^ (char)0x01;
    357.                 printf("错误位置:%d\n", (j << 3) + k);
    358.             }
    359.         }
    360.     }
    361. }
    复制代码

    由于数据是二进制的,得出了错误位置后,直接将所在位的数据取反就可以得到正确的数据,至此,数据的BCH编码和解码、纠错就全部完成了。


    最后,附上一段在网上找到的BCH编码算法,使用传统的BM算法计算错误多项式,供大家参考:
    1. void decode_bch(char * recd, int length, int t, int n)//国外的BCH解码算法,使用传统的BM算法计算错误多项式
    2. /*
    3. * Simon Rockliff's implementation of Berlekamp's algorithm.
    4. *
    5. * Assume we have received bits in recd[i], i=0..(n-1).
    6. *
    7. * Compute the 2*t syndromes by substituting alpha^i into rec(X) and
    8. * evaluating, storing the syndromes in s[i], i=1..2t (leave s[0] zero) .
    9. * Then we use the Berlekamp algorithm to find the error location polynomial
    10. * elp[i].
    11. *
    12. * If the degree of the elp is >t, then we cannot correct all the errors, and
    13. * we have detected an uncorrectable error pattern. We output the information
    14. * bits uncorrected.
    15. *
    16. * If the degree of elp is <=t, we substitute alpha^i , i=1..n into the elp
    17. * to get the roots, hence the inverse roots, the error location numbers.
    18. * This step is usually called "Chien's search".
    19. *
    20. * If the number of errors located is not equal the degree of the elp, then
    21. * the decoder assumes that there are more than t errors and cannot correct
    22. * them, only detect them. We output the information bits uncorrected.
    23. */
    24. {
    25.     register int    i, j, u, q, t2, count = 0, syn_error = 0;
    26.     int             elp[1026][1024], d[1026], l[1026], u_lu[1026], s[1025];
    27.     int             root[200], loc[200], reg[201];

    28.     t2 = 2 * t;

    29.     /* first form the syndromes */
    30.     printf("S(x) = ");
    31.     for (i = 1; i <= t2; i++) {
    32.         s[i] = 0;
    33.         for (j = 0; j < length; j++)
    34.             if (recd[j] != 0)
    35.                 s[i] ^= ys[(i * j) % n];
    36.         if (s[i] != 0)
    37.             syn_error = 1; /* set error flag if non-zero syndrome */
    38.                            /*
    39.                            * Note:    If the code is used only for ERROR DETECTION, then
    40.                            *          exit program here indicating the presence of errors.
    41.                            */
    42.                            /* convert syndrome from polynomial form to index form  */
    43.         s[i] = ys2[s[i]];
    44.         printf("%3d ", s[i]);
    45.     }
    46.     printf("\n");

    47.     if (syn_error) {    /* if there are errors, try to correct them */
    48.                         /*
    49.                         * Compute the error location polynomial via the Berlekamp
    50.                         * iterative algorithm. Following the terminology of Lin and
    51.                         * Costello's book :   d[u] is the 'mu'th discrepancy, where
    52.                         * u='mu'+1 and 'mu' (the Greek letter!) is the step number
    53.                         * ranging from -1 to 2*t (see L&C),  l[u] is the degree of
    54.                         * the elp at that step, and u_l[u] is the difference between
    55.                         * the step number and the degree of the elp.
    56.                         */
    57.                         /* initialise table entries */
    58.         d[0] = 0;           /* index form */
    59.         d[1] = s[1];        /* index form */
    60.         elp[0][0] = 0;      /* index form */
    61.         elp[1][0] = 1;      /* polynomial form */
    62.         for (i = 1; i < t2; i++)
    63.         {
    64.             elp[0][i] = -1; /* index form */
    65.             elp[1][i] = 0;  /* polynomial form */
    66.         }
    67.         l[0] = 0;
    68.         l[1] = 0;
    69.         u_lu[0] = -1;
    70.         u_lu[1] = 0;
    71.         u = 0;
    72.         do
    73.         {
    74.             u++;
    75.             if (d[u] == -1)
    76.             {
    77.                 l[u + 1] = l[u];
    78.                 for (i = 0; i <= l[u]; i++)
    79.                 {
    80.                     elp[u + 1][i] = elp[u][i];
    81.                     elp[u][i] = ys2[elp[u][i]];
    82.                 }
    83.             }
    84.             else//search for words with greatest u_lu[q] for which d[q]!=0搜索最高次项
    85.             {
    86.                 q = u - 1;
    87.                 while ((d[q] == -1) && (q > 0))
    88.                     q--;// have found first non-zero d[q]找到第一个非0的q
    89.                 if (q > 0)
    90.                 {
    91.                     j = q;
    92.                     do
    93.                     {
    94.                         j--;
    95.                         if ((d[j] != -1) && (u_lu[q] < u_lu[j]))
    96.                             q = j;
    97.                     } while (j > 0);
    98.                 }//have now found q such that d[u]!=0 and u_lu[q] is maximum找到符合条件的q
    99.                 if (l[u] > l[q] + u - q)//store degree of new elp polynomial存储多项式系数
    100.                     l[u + 1] = l[u];
    101.                 else
    102.                     l[u + 1] = l[q] + u - q;
    103.                 for (i = 0; i < t2; i++)//form new elp(x)
    104.                     elp[u + 1][i] = 0;
    105.                 for (i = 0; i <= l[q]; i++)
    106.                     if (elp[q][i] != -1)
    107.                         elp[u + 1][i + u - q] = ys[(d[u] + n - d[q] + elp[q][i]) % n];
    108.                 for (i = 0; i <= l[u]; i++)
    109.                 {
    110.                     elp[u + 1][i] ^= elp[u][i];
    111.                     elp[u][i] = ys2[elp[u][i]];
    112.                 }
    113.             }
    114.             u_lu[u + 1] = u - l[u + 1];
    115.             if (u < t2)//form (u+1)th discrepancy这段代码计算Dn=Sn+1+E(Sn+1-i * Oi)
    116.             {
    117.                 if (s[u + 1] != -1)//no discrepancy computed on last iteration上次迭代中没有错误
    118.                     d[u + 1] = ys[s[u + 1]];//将伴随式转换为十进制
    119.                 else
    120.                     d[u + 1] = 0;
    121.                 for (i = 1; i <= l[u + 1]; i++)//算Dj
    122.                     if ((s[u + 1 - i] != -1) && (elp[u + 1][i] != 0))
    123.                         d[u + 1] ^= ys[(s[u + 1 - i] + ys2[elp[u + 1][i]]) % n];
    124.                 d[u + 1] = ys2[d[u + 1]];//put d[u+1] into index form转换为幂次
    125.             }
    126.         } while ((u < t2) && (l[u + 1] <= t));

    127.         u++;
    128.         if (l[u] <= t) {/* Can correct errors */
    129.                         /* put elp into index form */
    130.             for (i = 0; i <= l[u]; i++)
    131.                 elp[u][i] = ys2[elp[u][i]];

    132.             printf("sigma(x) = ");
    133.             for (i = 0; i <= l[u]; i++)
    134.                 printf("%3d ", elp[u][i]);
    135.             printf("\n");
    136.             printf("Roots: ");

    137.             /* Chien search: find roots of the error location polynomial */
    138.             for (i = 1; i <= l[u]; i++)
    139.                 reg[i] = elp[u][i];
    140.             count = 0;
    141.             for (i = 1; i <= n; i++)
    142.             {
    143.                 q = 1;
    144.                 for (j = 1; j <= l[u]; j++)
    145.                     if (reg[j] != -1)
    146.                     {
    147.                         reg[j] = (reg[j] + j) % n;
    148.                         q ^= ys[reg[j]];
    149.                     }
    150.                 if (!q)
    151.                 {   // store root and error location number indices
    152.                     root[count] = i;
    153.                     loc[count] = n - i;
    154.                     count++;
    155.                     printf("%3d ", n - i);
    156.                 }
    157.             }
    158.             printf("\n");
    159.             if (count == l[u])
    160.                 /* no. roots = degree of elp hence <= t errors */
    161.                 for (i = 0; i < l[u]; i++)
    162.                     recd[loc[i]] ^= 1;
    163.             else    /* elp has degree >t hence cannot solve */
    164.                 printf("Incomplete decoding: errors detected\n");
    165.         }
    166.     }
    167. }
    复制代码


    相信自已,未来是自已创造的。
    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    RISC-V单片机中文网上一条 /2 下一条




    版权及免责声明|RISC-V单片机中文网 |网站地图

    GMT+8, 2021-4-16 23:03 , Processed in 0.583334 second(s), 47 queries .

    快速回复 返回顶部 返回列表