rs.c

Reed-Solomoon 纠错算法C语言的实现

  mb[2] = gadd6(gmult3(*(Syndrome+2), matrix[0], matrix[4]),
                gmult3(*(Syndrome+1), matrix[1], matrix[6]),
                gmult3(*(Syndrome+0), matrix[3], matrix[7]),
                gmult3(*(Syndrome+1), matrix[0], matrix[7]),
                gmult3(*(Syndrome+2), matrix[1], matrix[3]),
                gmult3(*(Syndrome+0), matrix[4], matrix[6]));

  data[0] = gdiv(ma, mb[0]);
  data[1] = gdiv(ma, mb[1]);
  data[2] = gdiv(ma, mb[2]);

  for (i=0; i<3; i++) {
    if (*(location+i) > ulCnt) i++;
    code[i] = *(codeword+(*(location+i)));
    data[i] = ((unsigned int)code[i]) ^ data[i];
    code[i] = (unsigned char) data[i];
    *(codeword+(*(location+i))) = code[i];
  }
}

//---------------------------------------------------------------------------------
//      Function name  :   Four_Error_Correction
//      Description    :   four error corrction
//      Parameter      :   unsigned int ulCnt
//                     :   unsigned int *Syndrome
//                     :   unsigned int *location
//                     :   unsigned int *codeword
//      Return value   :   NULL
//---------------------------------------------------------------------------------

void Four_Error_Correction(unsigned int ulCnt,
                           unsigned int *Syndrome, 
                           unsigned int *location,
                           unsigned char *codeword)
{
  unsigned int i;
  unsigned int parity[4];
  unsigned int loc[4];
  unsigned int matrix[16];
  unsigned int s[4];
  unsigned int ma;
  unsigned int mb[4];
  unsigned int data[4];
  unsigned char code[4];

  loc[0] = gexp[ulCnt+8-*location];
  loc[1] = gexp[ulCnt+8-*(location+1)];
  loc[2] = gexp[ulCnt+8-*(location+2)];
  loc[3] = gexp[ulCnt+8-*(location+3)];

  matrix[0]  = loc[0];
  matrix[1]  = loc[1];
  matrix[2]  = loc[2];
  matrix[3]  = loc[3];
              
  matrix[4]  = gmult(loc[0], loc[0]);
  matrix[5]  = gmult(loc[1], loc[1]);
  matrix[6]  = gmult(loc[2], loc[2]);
  matrix[7]  = gmult(loc[3], loc[3]);
              
  matrix[8]  = gmult3(loc[0], loc[0], loc[0]);
  matrix[9]  = gmult3(loc[1], loc[1], loc[1]);
  matrix[10] = gmult3(loc[2], loc[2], loc[2]);
  matrix[11] = gmult3(loc[3], loc[3], loc[3]);

  matrix[12] = gmult4(loc[0], loc[0], loc[0], loc[0]);
  matrix[13] = gmult4(loc[1], loc[1], loc[1], loc[1]);
  matrix[14] = gmult4(loc[2], loc[2], loc[2], loc[2]);
  matrix[15] = gmult4(loc[3], loc[3], loc[3], loc[3]);

  s[0] = gadd6(gmult4(matrix[0], matrix[5], matrix[10], matrix[15]),
               gmult4(matrix[0], matrix[6], matrix[11], matrix[13]),
               gmult4(matrix[0], matrix[7], matrix[9],  matrix[14]),
               gmult4(matrix[0], matrix[5], matrix[11], matrix[14]),
               gmult4(matrix[0], matrix[6], matrix[9],  matrix[15]),
               gmult4(matrix[0], matrix[7], matrix[10], matrix[13]));

  s[1] = gadd6(gmult4(matrix[1], matrix[4], matrix[10], matrix[15]),
               gmult4(matrix[1], matrix[6], matrix[11], matrix[12]),
               gmult4(matrix[1], matrix[7], matrix[8],  matrix[14]),
               gmult4(matrix[1], matrix[4], matrix[11], matrix[14]),
               gmult4(matrix[1], matrix[6], matrix[8],  matrix[15]),
               gmult4(matrix[1], matrix[7], matrix[10], matrix[12]));

  s[2] = gadd6(gmult4(matrix[2], matrix[4], matrix[9],  matrix[15]),
               gmult4(matrix[2], matrix[5], matrix[11], matrix[12]),
               gmult4(matrix[2], matrix[7], matrix[8],  matrix[13]),
               gmult4(matrix[2], matrix[4], matrix[11], matrix[13]),
               gmult4(matrix[2], matrix[5], matrix[8],  matrix[15]),
               gmult4(matrix[2], matrix[7], matrix[9],  matrix[12]));

  s[3] = gadd6(gmult4(matrix[3], matrix[4], matrix[9],  matrix[14]),
               gmult4(matrix[3], matrix[5], matrix[10], matrix[12]),
               gmult4(matrix[3], matrix[6], matrix[8],  matrix[13]),
               gmult4(matrix[3], matrix[4], matrix[10], matrix[13]),
               gmult4(matrix[3], matrix[5], matrix[8],  matrix[14]),
               gmult4(matrix[3], matrix[6], matrix[9],  matrix[12]));

  ma = gadd4(s[0], s[1], s[2], s[3]);


  s[0] = gadd6(gmult4(*(Syndrome+0), matrix[5], matrix[10], matrix[15]),
               gmult4(*(Syndrome+0), matrix[6], matrix[11], matrix[13]),
               gmult4(*(Syndrome+0), matrix[7], matrix[9],  matrix[14]),
               gmult4(*(Syndrome+0), matrix[5], matrix[11], matrix[14]),
               gmult4(*(Syndrome+0), matrix[6], matrix[9],  matrix[15]),
               gmult4(*(Syndrome+0), matrix[7], matrix[10], matrix[13]));

  s[1] = gadd6(gmult4(*(Syndrome+1), matrix[1], matrix[10], matrix[15]),
               gmult4(*(Syndrome+3), matrix[1], matrix[6],  matrix[11]),
               gmult4(*(Syndrome+2), matrix[1], matrix[7],  matrix[14]),
               gmult4(*(Syndrome+1), matrix[1], matrix[11], matrix[14]),
               gmult4(*(Syndrome+2), matrix[1], matrix[6],  matrix[15]),
               gmult4(*(Syndrome+3), matrix[1], matrix[7],  matrix[10]));

  s[2] = gadd6(gmult4(*(Syndrome+1), matrix[2], matrix[9],  matrix[15]),
               gmult4(*(Syndrome+3), matrix[2], matrix[5],  matrix[11]),
               gmult4(*(Syndrome+2), matrix[2], matrix[7],  matrix[13]),
               gmult4(*(Syndrome+1), matrix[2], matrix[11], matrix[13]),
               gmult4(*(Syndrome+2), matrix[2], matrix[5],  matrix[15]),
               gmult4(*(Syndrome+3), matrix[2], matrix[7],  matrix[9]));

  s[3] = gadd6(gmult4(*(Syndrome+1), matrix[3], matrix[9],  matrix[14]),
               gmult4(*(Syndrome+3), matrix[3], matrix[5],  matrix[10]),
               gmult4(*(Syndrome+2), matrix[3], matrix[6],  matrix[13]),
               gmult4(*(Syndrome+1), matrix[3], matrix[10], matrix[13]),
               gmult4(*(Syndrome+2), matrix[3], matrix[5],  matrix[14]),
               gmult4(*(Syndrome+3), matrix[3], matrix[6],  matrix[9]));

  mb[0] = gadd4(s[0], s[1], s[2], s[3]);

  s[0] = gadd6(gmult4(*(Syndrome+1), matrix[0], matrix[10], matrix[15]),
               gmult4(*(Syndrome+3), matrix[0], matrix[6],  matrix[11]),
               gmult4(*(Syndrome+2), matrix[0], matrix[7],  matrix[14]),
               gmult4(*(Syndrome+1), matrix[0], matrix[11], matrix[14]),
               gmult4(*(Syndrome+2), matrix[0], matrix[6],  matrix[15]),
               gmult4(*(Syndrome+3), matrix[0], matrix[7],  matrix[10]));

  s[1] = gadd6(gmult4(*(Syndrome+0), matrix[4], matrix[10], matrix[15]),
               gmult4(*(Syndrome+0), matrix[6], matrix[11], matrix[12]),
               gmult4(*(Syndrome+0), matrix[7], matrix[8],  matrix[14]),
               gmult4(*(Syndrome+0), matrix[4], matrix[11], matrix[14]),
               gmult4(*(Syndrome+0), matrix[6], matrix[8],  matrix[15]),
               gmult4(*(Syndrome+0), matrix[7], matrix[10], matrix[12]));

  s[2] = gadd6(gmult4(*(Syndrome+2), matrix[2], matrix[4],  matrix[15]),
               gmult4(*(Syndrome+1), matrix[2], matrix[11], matrix[12]),
               gmult4(*(Syndrome+3), matrix[2], matrix[7],  matrix[8]),
               gmult4(*(Syndrome+3), matrix[2], matrix[4],  matrix[11]),
               gmult4(*(Syndrome+1), matrix[2], matrix[8],  matrix[15]),
               gmult4(*(Syndrome+2), matrix[2], matrix[7],  matrix[12]));

  s[3] = gadd6(gmult4(*(Syndrome+2), matrix[3], matrix[4],  matrix[14]),
               gmult4(*(Syndrome+1), matrix[3], matrix[10], matrix[12]),
               gmult4(*(Syndrome+3), matrix[3], matrix[6],  matrix[8]),
               gmult4(*(Syndrome+3), matrix[3], matrix[4],  matrix[10]),
               gmult4(*(Syndrome+1), matrix[3], matrix[8],  matrix[14]),
               gmult4(*(Syndrome+2), matrix[3], matrix[6],  matrix[12]));

  mb[1] = gadd4(s[0], s[1], s[2], s[3]);

  s[0] = gadd6(gmult4(*(Syndrome+2), matrix[0], matrix[5],  matrix[15]),
               gmult4(*(Syndrome+1), matrix[0], matrix[11], matrix[13]),
               gmult4(*(Syndrome+3), matrix[0], matrix[7],  matrix[9]),
               gmult4(*(Syndrome+3), matrix[0], matrix[5],  matrix[11]),
               gmult4(*(Syndrome+1), matrix[0], matrix[9],  matrix[15]),
               gmult4(*(Syndrome+2), matrix[0], matrix[7],  matrix[13]));

  s[1] = gadd6(gmult4(*(Syndrome+2), matrix[1], matrix[4],  matrix[15]),
               gmult4(*(Syndrome+1), matrix[1], matrix[11], matrix[12]),
               gmult4(*(Syndrome+3), matrix[1], matrix[7],  matrix[8]),
               gmult4(*(Syndrome+3), matrix[1], matrix[4],  matrix[11]),
               gmult4(*(Syndrome+1), matrix[1], matrix[8],  matrix[15]),
               gmult4(*(Syndrome+2), matrix[1], matrix[7],  matrix[12]));

  s[2] = gadd6(gmult4(*(Syndrome+0), matrix[4], matrix[9],  matrix[15]),
               gmult4(*(Syndrome+0), matrix[5], matrix[11], matrix[12]),
               gmult4(*(Syndrome+0), matrix[7], matrix[8],  matrix[13]),
               gmult4(*(Syndrome+0), matrix[4], matrix[11], matrix[13]),
               gmult4(*(Syndrome+0), matrix[5], matrix[8],  matrix[15]),
               gmult4(*(Syndrome+0), matrix[7], matrix[9],  matrix[12]));

  s[3] = gadd6(gmult4(*(Syndrome+3), matrix[3], matrix[4],  matrix[9]),
               gmult4(*(Syndrome+2), matrix[3], matrix[5],  matrix[12]),
               gmult4(*(Syndrome+1), matrix[3], matrix[8],  matrix[13]),
               gmult4(*(Syndrome+2), matrix[3], matrix[4],  matrix[13]),
               gmult4(*(Syndrome+3), matrix[3], matrix[5],  matrix[8]),
               gmult4(*(Syndrome+1), matrix[3], matrix[9],  matrix[12]));

  mb[2] = gadd4(s[0], s[1], s[2], s[3]);


  s[0] = gadd6(gmult4(*(Syndrome+3), matrix[0], matrix[5],  matrix[10]),
               gmult4(*(Syndrome+2), matrix[0], matrix[6],  matrix[13]),
               gmult4(*(Syndrome+1), matrix[0], matrix[9],  matrix[14]),
               gmult4(*(Syndrome+2), matrix[0], matrix[5],  matrix[14]),
               gmult4(*(Syndrome+3), matrix[0], matrix[6],  matrix[9]),
               gmult4(*(Syndrome+1), matrix[0], matrix[10], matrix[13]));

  s[1] = gadd6(gmult4(*(Syndrome+3), matrix[1], matrix[4],  matrix[10]),
               gmult4(*(Syndrome+2), matrix[1], matrix[6],  matrix[12]),
               gmult4(*(Syndrome+1), matrix[1], matrix[8],  matrix[14]),
               gmult4(*(Syndrome+2), matrix[1], matrix[4],  matrix[14]),
               gmult4(*(Syndrome+3), matrix[1], matrix[6],  matrix[8]),
               gmult4(*(Syndrome+1), matrix[1], matrix[10], matrix[12]));

  s[2] = gadd6(gmult4(*(Syndrome+3), matrix[2], matrix[4],  matrix[9]),
               gmult4(*(Syndrome+2), matrix[2], matrix[5],  matrix[12]),
               gmult4(*(Syndrome+1), matrix[2], matrix[8],  matrix[13]),
               gmult4(*(Syndrome+2), matrix[2], matrix[4],  matrix[13]),
               gmult4(*(Syndrome+3), matrix[2], matrix[5],  matrix[8]),
               gmult4(*(Syndrome+1), matrix[2], matrix[9],  matrix[12]));

  s[3] = gadd6(gmult4(*(Syndrome+0), matrix[4], matrix[9],  matrix[14]),
               gmult4(*(Syndrome+0), matrix[5], matrix[10], matrix[12]),
               gmult4(*(Syndrome+0), matrix[6], matrix[8],  matrix[13]),
               gmult4(*(Syndrome+0), matrix[4], matrix[10], matrix[13]),
               gmult4(*(Syndrome+0), matrix[5], matrix[8],  matrix[14]),
               gmult4(*(Syndrome+0), matrix[6], matrix[9],  matrix[12]));

  mb[3] = gadd4(s[0], s[1], s[2], s[3]);

  data[0] = gdiv(ma, mb[0]);
  data[1] = gdiv(ma, mb[1]);
  data[2] = gdiv(ma, mb[2]);
  data[3] = gdiv(ma, mb[3]);

  for (i=0; i<4; i++) {
    if (*(location+i) > ulCnt) i++;
    code[i] = *(codeword+(*(location+i)));
    data[i] = ((unsigned int)code[i]) ^ data[i];
    code[i] = (unsigned char) data[i];
    *(codeword+(*(location+i))) = code[i];
  }
}

//---------------------------------------------------------------------------------
//      Function name  :   Find_Location
//      Description    :   find out error location
//      Parameter      :   unsigned int ulCnt
//                     :   unsigned int *Sigma
//                     :   unsigned int *Location
//      Return value   :   int
//--------------------------------------------------------------------------------- 
static unsigned int Find_Location (unsigned int ulCnt, unsigned int *Sigma, unsigned int *Location)
{
  unsigned int i, j;
  unsigned int x[4];
  unsigned int y;

  gexp[1024] = 1; 
  j = 0;
  for (i=0; i<ulCnt+8; i++) {
    x[0] = gexp[i+1023-ulCnt-8+1+1];
    x[1] = gmult(x[0], x[0]);
    x[2] = gmult(x[1], x[0]);
    x[3] = gmult(x[2], x[0]);
    y    = gadd4(gmult(*(Sigma+3), x[3]), gmult(*(Sigma+2), x[2]),
                 gmult(*(Sigma+1), x[1]), gmult(*(Sigma+0), x[0]));

    if (gadd(y, 1) == 0) {
      *(Location + j) = i;
      j++;
    }
  }
  return (j);
}