ribm.cpp

c编的RS编码的程 c编的RS编码的程

      omiga ^= alpha_to[(z[j]+i*j)%nn];
    }

    sita = 0;
    for(j=0; j<=tt; j++){
     if((j%2)!=0 && reg[j]!=-1)
      sita ^= alpha_to[(reg[j]+i*j)%nn];
    }
   }
   file://End of reference*/


//   file://calculate the error value and correct
   for (i=0; i<nn; i++){
    err[i] = 0 ;
       if (recd[i]!=-1)        // convert recd[] to polynomial form
           recd[i] = alpha_to[recd[i]] ;
    else
     recd[i] = 0 ;
   }

   for (i=0; i<count; i++)
   {
    omiga = 0;
    for(j=0; j<tt; j++){
     if(z[j]!=-1 && root[i]!=-1)
      omiga ^= alpha_to[(z[j]+root[i]*j)%nn];
    }

    sita = 0;
    for(j=0; j<=tt; j++){
     if((j%2)!=0 && reg[j]!=-1 && root[i]!=-1)
      sita ^= alpha_to[(reg[j]+root[i]*j)%nn];
    }

//    file://sita = alpha_to[nn-index_of[sita]];
  //  file://yi = alpha_to[root[i]*(no_p+1)%nn];

    /*yi = (root[i]*(no_p-1))%nn;
    if(omiga!=0)
     yi = (yi + index_of[omiga])%nn;
    if(sita!=0)
     yi = (yi + nn - index_of[sita])%nn;*/
    yi = (root[i]*(no_p+1) + index_of[omiga] + nn - index_of[sita])%nn;
    err[loc[i]] = alpha_to[yi];

    recd[loc[i]] ^= err[loc[i]];
   }

   /*yi = alpha_to[nn-index_of[109]];
   yi = alpha_to[nn-index_of[176]];
   yi = alpha_to[nn-index_of[254]];*/

   yi = alpha_to[(index_of[12]+index_of[5])%nn];
   yi = alpha_to[(index_of[125]+index_of[156])%nn];
   yi = alpha_to[(index_of[184]+index_of[240])%nn];

   yi = alpha_to[(index_of[60]+index_of[236])%nn];
   yi = alpha_to[(index_of[201]+index_of[135])%nn];
   yi = alpha_to[(index_of[178]+index_of[126])%nn];

   for(i=0; i<nn; i++)
    recd[i] = index_of[recd[i]];

   syn_error = 0;
//   file://End

   if (syn_error)       /* if errors, try and correct */
    {
/* compute the error location polynomial via the Berlekamp iterative algorithm,
   following the terminology of Lin and Costello :   d[u] is the 'mu'th
   discrepancy, where u='mu'+1 and 'mu' (the Greek letter!) is the step number
   ranging from -1 to 2*tt (see L&C),  l[u] is the
   degree of the elp at that step, and u_l[u] is the difference between the
   step number and the degree of the elp.
*/
/* initialise table entries */
      d[0] = 0 ;           /* index form */
      d[1] = s[1] ;        /* index form */
      elp[0][0] = 0 ;      /* index form */
      elp[1][0] = 1 ;      /* polynomial form */
      for (i=1; i<nn-kk; i++)
        { elp[0][i] = -1 ;   /* index form */
          elp[1][i] = 0 ;   /* polynomial form */
        }
      l[0] = 0 ;
      l[1] = 0 ;
      u_lu[0] = -1 ;
      u_lu[1] = 0 ;
      u = 0 ;

      do
      {
        u++ ;
        if (d[u]==-1)
          { l[u+1] = l[u] ;
            for (i=0; i<=l[u]; i++)
             {  elp[u+1][i] = elp[u][i] ;
                elp[u][i] = index_of[elp[u][i]] ;
             }
          }
        else
/* search for words with greatest u_lu[q] for which d[q]!=0 */
          { q = u-1 ;
            while ((d[q]==-1) && (q>0)) q-- ;
/* have found first non-zero d[q]  */
            if (q>0)
             { j=q ;
               do
               { j-- ;
                 if ((d[j]!=-1) && (u_lu[q]<u_lu[j]))
                   q = j ;
               }while (j>0) ;
             } ;

/* have now found q such that d[u]!=0 and u_lu[q] is maximum */
/* store degree of new elp polynomial */
            if (l[u]>l[q]+u-q)  l[u+1] = l[u] ;
            else  l[u+1] = l[q]+u-q ;

/* form new elp(x) */
            for (i=0; i<nn-kk; i++)    elp[u+1][i] = 0 ;
            for (i=0; i<=l[q]; i++)
              if (elp[q][i]!=-1)
                elp[u+1][i+u-q] = alpha_to[(d[u]+nn-d[q]+elp[q][i])%nn] ;
            for (i=0; i<=l[u]; i++)
              { elp[u+1][i] ^= elp[u][i] ;
                elp[u][i] = index_of[elp[u][i]] ;  /*convert old elp value to index*/
              }
          }
        u_lu[u+1] = u-l[u+1] ;

/* form (u+1)th discrepancy */
        if (u<nn-kk)    /* no discrepancy computed on last iteration */
          {
            if (s[u+1]!=-1)
                   d[u+1] = alpha_to[s[u+1]] ;
            else
              d[u+1] = 0 ;
            for (i=1; i<=l[u+1]; i++)
              if ((s[u+1-i]!=-1) && (elp[u+1][i]!=0))
                d[u+1] ^= alpha_to[(s[u+1-i]+index_of[elp[u+1][i]])%nn] ;
            d[u+1] = index_of[d[u+1]] ;    /* put d[u+1] into index form */
          }
      } while ((u<nn-kk) && (l[u+1]<=tt)) ;

      u++ ;
      if (l[u]<=tt)         /* can correct error */
       {
/* put elp into index form */
         for (i=0; i<=l[u]; i++)   elp[u][i] = index_of[elp[u][i]] ;

/* find roots of the error location polynomial */
         for (i=1; i<=l[u]; i++)
           reg[i] = elp[u][i] ;
         count = 0 ;
         for (i=1; i<=nn; i++)
          {  q = 1 ;
             for (j=1; j<=l[u]; j++)
              if (reg[j]!=-1)
                { reg[j] = (reg[j]+j)%nn ;
                  q ^= alpha_to[reg[j]] ;
                } ;
             if (!q)        /* store root and error location number indices */
              { root[count] = i;
                loc[count] = nn-i ;
                count++ ;
              };
          } ;
         if (count==l[u])    /* no. roots = degree of elp hence <= tt errors */
          {
/* form polynomial z(x) */
           for (i=1; i<=l[u]; i++)        /* Z[0] = 1 always - do not need */
            { if ((s[i]!=-1) && (elp[u][i]!=-1))
                 z[i] = alpha_to[s[i]] ^ alpha_to[elp[u][i]] ;
              else if ((s[i]!=-1) && (elp[u][i]==-1))
                      z[i] = alpha_to[s[i]] ;
                   else if ((s[i]==-1) && (elp[u][i]!=-1))
                          z[i] = alpha_to[elp[u][i]] ;
                        else
                          z[i] = 0 ;
              for (j=1; j<i; j++)
                if ((s[j]!=-1) && (elp[u][i-j]!=-1))
                   z[i] ^= alpha_to[(elp[u][i-j] + s[j])%nn] ;
              z[i] = index_of[z[i]] ;         /* put into index form */
            } ;

  /* evaluate errors at locations given by error location numbers loc[i] */
           for (i=0; i<nn; i++)
             { err[i] = 0 ;
               if (recd[i]!=-1)        /* convert recd[] to polynomial form */
                 recd[i] = alpha_to[recd[i]] ;
               else  recd[i] = 0 ;
             }
           for (i=0; i<l[u]; i++)    /* compute numerator of error term first */
            { err[loc[i]] = 1;       /* accounts for z[0] */
              for (j=1; j<=l[u]; j++)
                if (z[j]!=-1)
                  err[loc[i]] ^= alpha_to[(z[j]+j*root[i])%nn] ;
              if (err[loc[i]]!=0)
               { err[loc[i]] = index_of[err[loc[i]]] ;
                 q = 0 ;     /* form denominator of error term */
                 for (j=0; j<l[u]; j++)
                   if (j!=i)
                     q += index_of[1^alpha_to[(loc[j]+root[i])%nn]] ;
                 q = q % nn ;
                 err[loc[i]] = alpha_to[(err[loc[i]]-q+nn)%nn] ;
                 recd[loc[i]] ^= err[loc[i]] ;  /*recd[i] must be in polynomial form */
               }
            }
          }
         else    /* no. roots != degree of elp => >tt errors and cannot solve */
           for (i=0; i<nn; i++)        /* could return error flag if desired */
               if (recd[i]!=-1)        /* convert recd[] to polynomial form */
                 recd[i] = alpha_to[recd[i]] ;
               else  recd[i] = 0 ;     /* just output received codeword as is */
       }
     else         /* elp has degree has degree >tt hence cannot solve */
       for (i=0; i<nn; i++)       /* could return error flag if desired */
          if (recd[i]!=-1)        /* convert recd[] to polynomial form */
            recd[i] = alpha_to[recd[i]] ;
          else  recd[i] = 0 ;     /* just output received codeword as is */
    }
   else       /* no non-zero syndromes => no errors: output received codeword */
    for (i=0; i<nn; i++)
       if (recd[i]!=-1)        /* convert recd[] to polynomial form */
         recd[i] = alpha_to[recd[i]] ;
       else  recd[i] = 0 ;
 }

 

void main()
{
  register int i, k;
  struct _timeb t1, t2;
  int err_dec;

  generate_gf();
  gen_poly() ;

//file://for  (i=0; i<kk; i++)   data[i] = rand()%256 ;
  for(i=0; i<kk; i++){
   data[i] = kk+2-i;
   if(data[i]>=256)
    data[i] = data[i] - 256;
  }

_ftime(&t1);
for (i = 0; i < 10000; i ++)
  encode_rs() ;
_ftime(&t2);

i = (t2.millitm-t1.millitm)+(t2.time-t1.time)*1000;

  for (i=0; i<nn-kk; i++)  recd[i] = bb[i] ;
  for (i=0; i<kk; i++) recd[i+nn-kk] = data[i] ;

/*for (k = 0; k < tt; k ++)
 recd[rand()%nn] = rand()%256;*/

/*for(k=0; k<nn; k++)
 recd[k] = 255-k+2;

recd[1] = 0;
recd[0] = 1;*/

recd[252] = 11;
recd[228] = 56;
recd[212] = 232;
//file://recd[193] = 197;
//file://recd[161] = 25;
//file://recd[92] = 133;

_ftime(&t1);
//file://for (i = 0; i < 10000; i ++)
for (i = 0; i < 1; i ++)
{
  for (k=0; k<nn; k++)
     recd[k] = index_of[recd[k]] ;          /* put recd[i] into index form */
  decode_rs() ;         /* recd[] is returned in polynomial form */
}
_ftime(&t2);

i = (t2.millitm-t1.millitm)+(t2.time-t1.time)*1000;

err_dec = 1;
for (i = 0; i <kk; i++){
 if (recd[i+nn-kk] != data[i]){
  err_dec = 0;
   break;
 }
}
}