rs.c

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

  for (i = 1; i < 1023; i++) {
    p9_tmp = p9;

    p9 = p8;
    p8 = p7;
    p7 = p6;
    p6 = p5;
    p5 = p4;
    p4 = p3;
    p3 = p2 ^ p9_tmp;
    p2 = p1;
    p1 = p0;
    p0 = p9_tmp;
    gexp[i+1] = p0     + p1*2  + p2*4  + p3*8   + 
                p4*16  + p5*32 + p6*64 + p7*128 + 
                p8*256 + p9*512;
  }

  for(i=0; i<1024; i++) glog[gexp[i]] = i;
}

//---------------------------------------------------------------------------------
//      Function name  :   gdiv
//      Description    :   div operator
//      Parameter      :   unsigned int a
//                     :   unsigned int b
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gdiv(unsigned int a, unsigned int b)
{
  unsigned int i, j;
  if (a==0) return (0);
  i = glog[a];
  j = glog[b];
  return(gexp[((j-i+1023)%1023)+1]);
}

//---------------------------------------------------------------------------------
//      Function name  :   gmult
//      Description    :   mult operator
//      Parameter      :   unsigned int a
//                     :   unsigned int b
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gmult(unsigned int a, unsigned int b)
{
  unsigned int i, j;
  if (a==0 || b == 0) return (0);
  i = glog[a];
  j = glog[b];
  return(gexp[((i+j-2)%1023)+1]);
}

//---------------------------------------------------------------------------------
//      Function name  :   gmult3
//      Description    :   mult operator
//      Parameter      :   unsigned int a
//                     :   unsigned int b
//                     :   unsigned int c
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gmult3(unsigned int a, unsigned int b, unsigned int c)
{
  unsigned int i, j, m;
  if (a==0 || b == 0 || c == 0) return (0);
  i = glog[a];
  j = glog[b];
  m = glog[c];
  return(gexp[((i+j+m-3)%1023)+1]);
}

//---------------------------------------------------------------------------------
//      Function name  :   gmult4
//      Description    :   mult operator
//      Parameter      :   unsigned int a
//                     :   unsigned int b
//                     :   unsigned int c
//                     :   unsigned int d
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gmult4(unsigned int a, unsigned int b, unsigned int c, unsigned d)
{
  unsigned int i, j, m, n;
  if (a==0 || b == 0 || c == 0 || d == 0) return (0);
  i = glog[a];
  j = glog[b];
  m = glog[c];
  n = glog[d];
  return(gexp[((i+j+m+n-4)%1023)+1]);
}

//---------------------------------------------------------------------------------
//      Function name  :   gadd
//      Description    :   add operator
//      Parameter      :   unsigned int a
//                     :   unsigned int b
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gadd(unsigned int a, unsigned int b)
{
  return (a ^b);
}

//---------------------------------------------------------------------------------
//      Function name  :   gadd4
//      Description    :   add operator
//      Parameter      :   unsigned int a0
//                     :   unsigned int a1
//                     :   unsigned int a2
//                     :   unsigned int a3
//      Return value   :   unsigned int
//--------------------------------------------------------------------------------- 
unsigned int gadd4(unsigned int a0, unsigned int a1, unsigned int a2, unsigned int a3)
{
  return (a0 ^ a1 ^ a2 ^ a3);
}

//---------------------------------------------------------------------------------
//      Function name  :   gadd6
//      Description    :   add operator
//      Parameter      :   unsigned int a0
//                     :   unsigned int a1
//                     :   unsigned int a2
//                     :   unsigned int a3
//                     :   unsigned int a4
//                     :   unsigned int a5
//      Return value   :   unsigned int
//---------------------------------------------------------------------------------
unsigned int gadd6(unsigned int a0, unsigned int a1, unsigned int a2, 
                   unsigned int a3, unsigned int a4, unsigned int a5)
{
  return (a0 ^ a1 ^ a2 ^ a3 ^ a4 ^ a5);
}

//---------------------------------------------------------------------------------
//      Function name  :   One_Error_Correction
//      Description    :   one error corrction
//      Parameter      :   unsigned int ulCnt
//                     :   unsigned int *Syndrome
//                     :   unsigned int *location
//                     :   unsigned int *codeword
//      Return value   :   NULL
//---------------------------------------------------------------------------------
static void One_Error_Correction(unsigned int ulCnt,
                          unsigned int *Syndrome, 
                          unsigned int *location,
                          unsigned char *codeword)
{
  unsigned int parity;
  unsigned int loc;
  unsigned int data;
  unsigned char code;

  parity = *Syndrome;
  loc = *location;

  data = gexp[((glog[parity]+1023-(ulCnt+8)+1+loc)%1023)];
  code = *(codeword+loc);
  data = ((unsigned int)code) ^ data;
  code = (unsigned char) data;

  *(codeword+loc) = code;
}

//---------------------------------------------------------------------------------
//      Function name  :   Two_Error_Correction
//      Description    :   two error corrction
//      Parameter      :   unsigned int ulCnt
//                     :   unsigned int *Syndrome
//                     :   unsigned int *location
//                     :   unsigned int *codeword
//      Return value   :   NULL
//---------------------------------------------------------------------------------
static void Two_Error_Correction(unsigned int ulCnt,
                          unsigned int *Syndrome, 
                          unsigned int *location,
                          unsigned char *codeword)
{
  unsigned int i;
  unsigned int parity[2];
  unsigned int loc[2];
  unsigned int matrix[4];
  unsigned int ma;
  unsigned int mb[2];
  unsigned int data[2];
  unsigned char code[2];

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

  matrix[0] = loc[0];
  matrix[1] = loc[1];
  matrix[2] = gmult(loc[0], loc[0]);
  matrix[3] = gmult(loc[1], loc[1]);

  ma = gadd(gmult(matrix[0], matrix[3]), gmult(matrix[1], matrix[2]));

  mb[0] = gadd(gmult(*(Syndrome+0), matrix[3]), gmult(matrix[1], *(Syndrome+1)));
  mb[1] = gadd(gmult(*(Syndrome+1), matrix[0]), gmult(matrix[2], *(Syndrome+0)));

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

  for (i=0; i<2; 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  :   Three_Error_Correction
//      Description    :   three error corrction
//      Parameter      :   unsigned int ulCnt
//                     :   unsigned int *Syndrome
//                     :   unsigned int *location
//                     :   unsigned int *codeword
//      Return value   :   NULL
//---------------------------------------------------------------------------------
void Three_Error_Correction(unsigned int ulCnt,
                            unsigned int *Syndrome, 
                            unsigned int *location,
                            unsigned char *codeword)
{
  unsigned int i;
  unsigned int parity[3];
  unsigned int loc[3];
  unsigned int matrix[9];
  unsigned int ma;
  unsigned int mb[3];
  unsigned int data[3];
  unsigned char code[3];

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

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

  ma = gadd6(gmult3(matrix[0], matrix[4], matrix[8]),
             gmult3(matrix[1], matrix[5], matrix[6]),
             gmult3(matrix[2], matrix[3], matrix[7]),
             gmult3(matrix[0], matrix[5], matrix[7]),
             gmult3(matrix[1], matrix[3], matrix[8]),
             gmult3(matrix[2], matrix[4], matrix[6]));

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

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