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 ; }main(){  register int i;/* generate the Galois Field GF(2**mm) */  generate_gf() ;  printf("Look-up tables for GF(2**%2d)\n",mm) ;  printf("  i   alpha_to[i]  index_of[i]\n") ;  for (i=0; i<=nn; i++)   printf("%3d      %3d          %3d\n",i,alpha_to[i],index_of[i]) ;  printf("\n\n") ;/* compute the generator polynomial for this RS code */  gen_poly() ;/* for known data, stick a few numbers into a zero codeword. Data is in   polynomial form.*/for  (i=0; i<kk; i++)   data[i] = 0 ;/* for example, say we transmit the following message (nothing special!) */data[0] = 8 ;data[1] = 6 ;data[2] = 8 ;data[3] = 1 ;data[4] = 2 ;data[5] = 4 ;data[6] = 15 ;data[7] = 9 ;data[8] = 9 ;/* encode data[] to produce parity in bb[].  Data input and parity output   is in polynomial form*/  encode_rs() ;/* put the transmitted codeword, made up of data plus parity, in recd[] */  for (i=0; i<nn-kk; i++)  recd[i] = bb[i] ;  for (i=0; i<kk; i++) recd[i+nn-kk] = data[i] ;/* if you want to test the program, corrupt some of the elements of recd[]   here. This can also be done easily in a debugger. *//* Again, lets say that a middle element is changed */  data[nn-nn/2] = 3 ;  for (i=0; i<nn; i++)     recd[i] = index_of[recd[i]] ;          /* put recd[i] into index form *//* decode recv[] */  decode_rs() ;         /* recd[] is returned in polynomial form *//* print out the relevant stuff - initial and decoded {parity and message} */  printf("Results for Reed-Solomon code (n=%3d, k=%3d, t= %3d)\n\n",nn,kk,tt) ;  printf("  i  data[i]   recd[i](decoded)   (data, recd in polynomial form)\n");  for (i=0; i<nn-kk; i++)    printf("%3d    %3d      %3d\n",i, bb[i], recd[i]) ;  for (i=nn-kk; i<nn; i++)    printf("%3d    %3d      %3d\n",i, data[i-nn+kk], recd[i]) ;}