rsheader_decode.h

(31,25)RS码编码以及解码的C程序

#include "RSHeader_public.h"

typedef struct Iterate
{ 
	int iterate[7];
	int length; /*the valuable length */
}Iterate;

typedef struct Root
{
	int root[7];
	int length;
}Root;

typedef struct forney
{
	int value[7];
	int site[7];
	int length;
}forney;

int temp_synd[7];


int rs_poly(int [], int ,int);
int rs_rev(int);
void circshift(int [], int , int);

/*calculate the syndrome polynomial according to the received sequence*/
void rs_decode_syndrome(int [], int);
/*calculate the locator polynomial according to the syndrome polynomial*/
Iterate rs_decode_iterate(int [], int);
/*calculate the roots of locator polynomial*/
Root rs_decode_root(int [], int);
/*calculate evaluator polynomial using forney arithmetic, according to 
syndrome polynomial & locator polynomial & roots of locator polynomial*/
forney rs_decode_forney(int [], int , int [], int , int [], int);



void decode();



int rs_rev(int a)
{
	int a1,y1;
	a1=find(T,a,31)-1;
	y1=(31-a1)%31;
	return T[y1];
}

int rs_poly(int t[], int array_size, int x)
{
	int xx,y1,i;
	xx=find(T,x,31)-1;
	y1=t[0];
	for(i=0;i<array_size-1;i++)
	{
		y1=rs_add(y1,rs_mul(t[i+1],T[((i+1)*xx)%31]));
	}
	return y1;
}

void rs_decode_syndrome(int r_x[], int array_size)
{
	int i;
	temp_synd[0]=1;
	for(i=0;i<6;i++)
	{
		temp_synd[i+1]=rs_poly(r_x, array_size, T[i+1]);
	}
}

Iterate rs_decode_iterate(int synd_x[], int array_size)
{
	int sigma[8][7],D[8],d[8],sigmaji[7];
	int i,j,r;
	int flag;
	Iterate temp;
	/*Initial values*/
	for(i=0;i<8;i++)
		for(j=0;j<7;j++)
			sigma[i][j]=0;

	assignValueInt(D,0,8);
	assignValueInt(d,0,8);
	assignValueInt(sigmaji,0,8);

	D[-2+2]=0;
	d[-2+2]=1;
	sigma[-1+2][0]=1;
	D[-1+2]=0;
	d[-1+2]=synd_x[0+1];
	

	flag=-2;
	for(j=-1;j<5;j++)
	{
		/*massey arithmetic*/
		if(d[j+2] ==0)
		{
			for(i=0;i<7;i++)
				sigma[j+2+1][i]=sigma[j+2][i];
			D[j+2+1]=D[j+2];
		}
		else
		{
			for(i=0;i<7;i++)
			{
				sigmaji[i]=sigma[flag+2][i];
			}
			circshift(sigmaji,7,j-flag);

			for(i=0;i<7;i++)
				sigma[j+2+1][i]=rs_add(sigma[j+2][i],rs_mul(rs_mul(d[j+2],
										rs_rev(d[flag+2])),sigmaji[i]));

			/*to get the D(j)*/
			for(i=0;i<7;i++)
			{
				if(sigma[j+2+1][i] != 0)
					D[j+2+1]=i;
			}
			flag=j;
		}
		
		if(j != 4)
		{
			r=j+1;
			d[r+2]=synd_x[r+1+1];
			for(i=0;i<D[r+2];i++)
			{
				d[r+2]=rs_add(d[r+2],rs_mul(sigma[r+2][i+1],synd_x[r+1-i]));
			}
		}
	}

	for(i=0;i<(D[7]+1);i++)
	{
		temp.iterate[i]=sigma[7][i];
	}
	temp.length=D[7]+1;

	return temp;
}

Root rs_decode_root(int x[], int array_size)
{
	Root temp;
	int i,result,j=0;
	for(i=-1;i<30;i++)
	{
		result = rs_poly(x,array_size,T[i+1]);
		if(result == 0)
		{
			temp.root[j]=T[i+1];
			j=j+1;
		}
	}
	temp.length=j;

	return temp;
}

forney rs_decode_forney(int synd[], int synd_size, int sigma_x[], int sigma_size, int root[], int root_size)
{
	forney temp;
	int w1[20],len_w1,t,i,j;
	int w[6],s[4];
	int s_final,w_final;
	len_w1=synd_size+sigma_size-1;
	assignValueInt(w1,0,len_w1);
	t=3;
	for(i=0;i<synd_size-1;i++)
		for(j=0;j<sigma_size;j++)
			w1[i+j]=rs_add(w1[i+j],rs_mul(synd[i+1],sigma_x[j]));

	/*evaluator polynomial*/
	assignValue(w,w1,2*t);
	assignValueInt(s,0,sigma_size);

	for(i=0;i<sigma_size;i++)
	{
		if(i%2 == 0)
		{
			s[i]=sigma_x[i+1];
		}
	}
	s[sigma_size-1]=0;
	for(i=0;i<root_size;i++)
	{
		w_final = rs_poly(w,6,root[i]);
		s_final = rs_poly(s,sigma_size,root[i]);
		/*error value*/
		if(s_final == 0)
		{
			temp.value[i] = 0;
		}
		else
		{
			temp.value[i] = rs_mul(w_final,rs_rev(s_final));
		}
		temp.site[i] = (32 - find(T,root[i],31))%31;
	}
	temp.length=root_size;

	return temp;
}

void decode()
{
	Iterate temp_iterate;
	Root temp_root;
	forney temp_forney;
	int i;
	int temp[31];

	rs_decode_syndrome(temp_Bdecode, 31);
	printf("the synd_x is\n");
	for(i=0;i<7;i++)
	{
		printf("%d ",temp_synd[i]);
	}

	
	temp_iterate = rs_decode_iterate(temp_synd,7);
	printf("\nthe sigma_x is\n");
	for(i=0;i<temp_iterate.length;i++)
	{
		printf("%d ",temp_iterate.iterate[i]);
	}

	temp_root = rs_decode_root(temp_iterate.iterate,temp_iterate.length);
	printf("\nthe root is\n");
	for(i=0;i<temp_root.length;i++)
	{
		printf("%d ",temp_root.root[i]);
	}
	printf("\n");

	if(temp_root.length == 0)
	{
		printf("no error!\n");
		for(i=0;i<25;i++)
		{
			temp_Adecode[i] = temp_Bdecode[i+6];
		}
	}
	else
	{
		temp_forney = rs_decode_forney(temp_synd,7,temp_iterate.iterate,temp_iterate.length
						,temp_root.root,temp_root.length);
		assignValue(temp,temp_Bdecode,31);
		for(i=0;i<temp_forney.length;i++)
		{
			temp[temp_forney.site[i]] = rs_add(temp_Bdecode[temp_forney.site[i]],temp_forney.value[i]);
		}

		if(temp_forney.length>3)
		{
			printf("too many errors occur, can not correct them all\n");
			for(i=0;i<25;i++)
			{
				temp_Adecode[i] = temp[i+6];
			}			
		}
		else
		{
			printf("output!\n");
			for(i=0;i<25;i++)
			{
				temp_Adecode[i] = temp[i+6];
			}	
		}
	}
}