RS纠错编码和解码
//rs code//m=8
#include <math.h>
#include <stdio.h>
#include <string.h>
#define mm8 /* RS code over GF(2**4) - change to suit */
#define nn255 /* nn=2**mm -1 length of codeword */
#define tt10 /* number of errors that can be corrected */
#define kk235 /* kk = nn-2*tt*/
int pp = {1, 0, 1, 1, 1, 0, 0, 0, 1};
int alpha_to , index_of , gg ;
int recd , data , bb ;
void generate_gf()
/* 生成GF(2^m)空间 */
{
register int i, mask ;
mask = 1 ;
alpha_to = 0 ;
for (i=0; i<mm; i++)
{
alpha_to = mask ;
index_of] = i ;
if (pp!=0)
alpha_to ^= mask ;
mask <<= 1 ;
}
index_of] = mm ;
mask >>= 1 ;
for (i=mm+1; i<nn; i++)
{
if (alpha_to >= mask)
alpha_to = alpha_to ^ ((alpha_to^mask)<<1) ;
else
alpha_to = alpha_to<<1 ;
index_of] = i ;
}
index_of = -1 ;
//alpha_to = 1;
for(i=0;i<mm;i++)
printf("gf%d is%d\n",i,alpha_to);
}
void gen_poly()
/* 生成---生成多项式*/
{
register int i,j ;
gg = 2 ; /* primitive element alpha = 2for GF(2**mm)*/
gg = 1 ; /* g(x) = (X+alpha) initially */
for (i=2; i<=nn-kk; i++)
{
gg = 1 ;
for (j=i-1; j>0; j--)
if (gg != 0)
gg = gg^ alpha_to[(index_of]+i)%nn];
else
gg = gg ;
gg = alpha_to[(index_of]+i)%nn] ; /* gg can never be zero */
}
//printf("polynomial:\n");
//for(i=0; i<=nn-kk; i++)
// printf("%d ", gg);
//printf("\n");
/* convert gg[] to index form for quicker encoding */
for (i=0; i<=nn-kk; i++)
gg = index_of];
//printf("polynomial:\n");
//for(i=0; i<=nn-kk; i++)
// printf("%d ", gg);
//printf("\n");
}
void encode_rs()
/* 编码*/
{
register int i,j ;
int feedback ;
for (i=0; i<nn-kk; i++) bb = 0 ;
for (i=kk-1; i>=0; i--)
{
//逐步的将下一步要减的，存入bb(i)
feedback = index_of^bb] ;
if(feedback != -1)
{
for (j=nn-kk-1; j>0; j--)
if (gg != -1)
bb = bb^alpha_to[(gg+feedback)%nn] ; //plus = ^
else
bb = bb ;
bb = alpha_to[(gg+feedback)%nn] ;
}
else
{
for (j=nn-kk-1; j>0; j--)
bb = bb ;
bb = 0 ;
};
};
}
void decode_rs()
{/*解码*/
register int i,j,u,q ;
int elp, d, l, u_lu, s ;
int count=0, syn_error=0, root, loc, z, err, reg ;
/* first form the syndromes */
for(i=0; i<nn; i++) //转换成GF空间的alpha幂次
if(recd == -1)
recd = 0;
else
recd = index_of];
for (i=1; i<=nn-kk; i++)
{
s = 0 ;
for (j=0; j<nn; j++)
if (recd!=-1)
s ^= alpha_to[(recd+i*j)%nn] ; /* recd in index form */
/* convert syndrome from polynomial form to index form*/
if (s!=0)
syn_error=1 ; /* set flag if non-zero syndrome => error */
printf("%3d", s);
s = index_of] ;
printf("%3d", s);
} ;
if (syn_error) /* if errors, try and correct */
{printf("*\n");
/* compute the error location polynomial via the Berlekamp iterative algorithm,
following the terminology of Lin and Costello : d 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 is the
degree of the elp at that step, and u_l is the difference between the
step number and the degree of the elp.*/
/* initialise table entries */
d = 0 ; /* index form */
d = s ; /* index form */
elp = 0 ; /* index form */
elp = 1 ; /* polynomial form */
for (i=1; i<nn-kk; i++)
{
elp = -1 ; /* index form */
elp = 0 ; /* polynomial form */
}
l = 0 ;
l = 0 ;
u_lu = -1 ;
u_lu = 0 ;
u = 0 ;
do
{
u++ ;
if (d==-1)
{
l = l ;
for (i=0; i<=l; i++)
{
elp = elp ;
elp = index_of] ;
}
}
else
/* search for words with greatest u_lu for which d!=0 */
{
q = u-1 ;
while ((d==-1) && (q>0))
q-- ;
/* have found first non-zero d*/
if (q>0)
{
j=q ;
do
{
j-- ;
if ((d!=-1) && (u_lu<u_lu))
q = j ;
}while (j>0) ;
} ;
/* have now found q such that d!=0 and u_lu is maximum */
/* store degree of new elp polynomial */
if (l>l+u-q)
l = l ;
else
l = l+u-q ;
/* form new elp(x) */
for (i=0; i<nn-kk; i++)
elp = 0 ;
for (i=0; i<=l; i++)
if (elp!=-1)
elp = alpha_to[(d+nn-d+elp)%nn] ;
for (i=0; i<=l; i++)
{
elp ^= elp ;
elp = index_of] ;/*convert old elp value to index*/
}
}
u_lu = u-l ;
/* form (u+1)th discrepancy */
if (u<nn-kk) /* no discrepancy computed on last iteration */
{
if (s!=-1)
d = alpha_to] ;
else
d = 0 ;
for (i=1; i<=l; i++)
if ((s!=-1) && (elp!=0))
d ^= alpha_to[(s+index_of])%nn] ;
d = index_of] ; /* put d into index form */
}
} while ((u<nn-kk) && (l<=tt)) ;
u++ ;
if (l<=tt) /* can correct error */
{
/* put elp into index form */
for (i=0; i<=l; i++)
elp = index_of] ;
/* find roots of the error location polynomial */
/*求错误位置多项式的根*/
for (i=1; i<=l; i++)
reg = elp ;
count = 0 ;
for (i=1; i<=nn; i++)
{
q = 1 ;
for (j=1; j<=l; j++)
if (reg!=-1)
{
reg = (reg+j)%nn ;
q ^= alpha_to] ;
} ;
if (!q) /* store root and error location number indices */
{
root = i;
loc = nn-i ;
count++ ;
printf("根%d=%d\n", q, nn-i);
};
} ;
if (count==l) /* no. roots = degree of elp hence <= tt errors */
{/* form polynomial z(x) */
for (i=1; i<=l; i++) /* Z = 1 always - do not need */
{
if ((s!=-1) && (elp!=-1))
z = alpha_to] ^ alpha_to] ;
else if ((s!=-1) && (elp==-1))
z = alpha_to] ;
else if ((s==-1) && (elp!=-1))
z = alpha_to] ;
else
z = 0 ;
for (j=1; j<i; j++)
if ((s!=-1) && (elp!=-1))
z ^= alpha_to[(elp + s)%nn] ;
z = index_of] ; /* put into index form */
} ;
/* evaluate errors at locations given by error location numbers loc */
/*计算错误图样*/
for (i=0; i<nn; i++)
{
err = 0 ;
if (recd!=-1) /* convert recd[] to polynomial form */
recd = alpha_to] ;
else
recd = 0 ;
}
for (i=0; i<l; i++) /* compute numerator of error term first */
{
err] = 1; /* accounts for z */
for (j=1; j<=l; j++)
if (z!=-1)
err] ^= alpha_to[(z+j*root)%nn] ;
if (err]!=0)
{
err] = index_of]] ;
q = 0 ; /* form denominator of error term */
for (j=0; j<l; j++)
if (j!=i)
q += index_of+root)%nn]] ;
q = q % nn ;
err] = alpha_to[(err]-q+nn)%nn] ;
recd] ^= err] ;/*recd 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!=-1) /* convert recd[] to polynomial form*/
recd = alpha_to] ;
else
recd = 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!=-1) /* convert recd[] to polynomial form */
recd = alpha_to] ;
else
recd = 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!=-1) /* convert recd[] to polynomial form */
recd = alpha_to] ;
else
recd = 0 ;
//printf("*");
}
}
int main()
{
int i, length;
char strSrc, strDst;
printf("请输入要编码的字符串：\n");
scanf("%s", strSrc);
length = strlen(strSrc);
if(length <= 0)
return 0;
generate_gf();
printf("Look-up tables for GF(2**%2d)\n",mm) ;
printf("i alpha_toindex_of\n") ;
for (i=0; i<=nn; i++)
printf("%3d %3d %3d\n",i,alpha_to,index_of);
printf("\n\n");
gen_poly();
for(i=0; i<kk; i++)
data = 0;
/* for example, say we transmit the following message (nothing special!) */
for(i=0; i<length; i++)
data = strSrc;
/* data = 8 ;
data = 6 ;
data = 8 ;
data = 1 ;
data = 2 ;
data = 4 ;
data = 15 ;
data = 9 ;
data = 55 ;*/
encode_rs();
data = 19 ;
for (i=0; i<nn-kk; i++)
recd = bb ;
for (i=0; i<kk; i++)
recd = data ;
/* printf("Results for Reed-Solomon code (n=%3d, k=%3d, t= %3d)\n\n",nn,kk,tt) ;
printf("idata recd(decoded) (data, recd in polynomial form)\n");
for (i=0; i<nn-kk; i++)
printf("%3d %3d %3d\n",i, bb, recd) ;
for (i=nn-kk; i<=nn; i++)
printf("%3d %3d %3d\n",i, data, recd) ;*/
decode_rs() ;
printf("Results for Reed-Solomon code (n=%3d, k=%3d, t= %3d)\n\n",nn,kk,tt) ;
printf("idata recd(decoded) (data, recd in polynomial form)\n");
for (i=0; i<nn-kk; i++)
printf("%3d %3d %3d\n",i, bb, recd) ;
for (i=nn-kk; i<=nn; i++)
{
printf("%3d %3d %3d\n",i, data, recd) ;
}
for(i=0; i<length; i++)
strDst = recd;
strDst = '\0';
printf("%s\n", strDst);
}
RS纠错编码和解码 RS纠错编码和解码
页:
[1]
