rs.c

RS(15,9)上的C语言纠错源码.在VC++6.0平台上调试通过

            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 codewor d */ 
	{
		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] = 4; 
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 */
//------------------------ Here Assum The Nioce Coming -----------------------
  //data[nn-nn/2] = 3 ;
//------------------------ Here Assum The Noice Coming -----------------------
  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]) ; 
} 
 
 
/////////--