reed_solomon0.h

DSP中实现的RS编码+MFSK调制的实现

	free(gx);
	free(addtemp);
	free(multtemp);
    return Temp;
}

int *CountSi(int *R, int m,int N /* N= 2^m-1*/,int t)   // count the 伴随多项式 S(i)
{
    int i,j;
   // int *result=(int *)calloc(2*t,sizeof(int));
  //  int *s=(int *)calloc(N,sizeof(int));
    int s[2];
    Result=(int *)calloc(2*t,sizeof(int));
    for(j=0;j<2*t;j++)
    {
    	s[0]=R[0];
      for( i=1;i<N;i++)
      {
        s[1]=MultInGf(R[i],(i*(j+1))%N,N);       //R[a^i]
        s[1]=AddInGf(s[1],s[0],m);
		s[0]=s[1];
      }
      Result[j]=s[1];
    }
	 
    return Result;
	//free(result);
}
//多项式的运算。用于decode操作。poly(ErrorLoc,dj,j-1,maxIn,t,m)
int poly(int * o,int *dj, int j,int i,int t,int m)  //o:error,
{
	int Row;	
	int xish;
    int N;
    int q;
	int xi=j-i;
    int h;
	int polyLen=0;
	int *temp=(int *)calloc(2*t,sizeof(int));

	Row=2*t;
	N=(int)pow(2,m)-1;
	xish=DivInGf(dj[j],dj[i],N); // =dj/di;
	
	// count step1=（dj/di）*o(i)
	for(h=0;h<2*t;h++)
	{
		temp[h]=MultInGf(o[Row*i+h],xish,N);
	}

	// count step2=step1*x^(xi)
	for(q=0;q<xi;q++)
	{
		for(h=2*t-1;h>=1;h--)
		{
			temp[h]=temp[h-1];
		}
	}
	for(h=0;h<xi;h++)
		temp[h]=N;  // the LSB = N

	// count step3：o(i+1)
	
	for(h=0;h<2*t;h++)
		o[Row*(j+1)+h]=AddInGf(o[Row*j+h],temp[h],m);
	for(h=2*t-1;h>=0;h--) //计算多项式的阶数。
	{
		if(o[Row*(j+1)+h]!=N)
		{
		polyLen=h;
		break;
		}
	}
	return polyLen;  //返回多项式的阶数。
	//free(temp);
	
}  

void Decode(int * R,int *S,int m,int N,int L)  //解码函数。R=code
{
   int t=(N-L)/2;
   //t=(N-L)/2;

   int * D=(int *) calloc(2*t+2,sizeof(int));
   int * deta=(int*)calloc(2*t+2,sizeof(int));
   int * dj=(int *)calloc(2*t+2,sizeof(int));
   int * ErrorLoc=(int *)calloc((2*t+2) * 2*t,sizeof(int));  //o(x)
 
   int i,j=0;   
   int Row=2*t;

   int max,maxIn=0;
   int temp;
   int sum;

   int vol;

   int thelast;

   int	k=0,current;
   int  RootNum;  //根的个数。
   int  *root;

   int mik;
   int sign;
   int *xe;  //在xe数组里存放了错误值。
   int * ErrorMat;
   int * B;

   int CorrectR=0;

   //  initial  //
   for(i=0;i<(2*t+2)*2*t;i++)
	   ErrorLoc[i]=N;

   ///////////迭代法求错误多项式//////////////
   ErrorLoc[Row*j]=0;   
   D[j]=0;
   deta[j]=-1;
   dj[j]=0;   //a^0=1  //有限域内的指数表示。
   
   j++;
   ErrorLoc[Row*j]=0;
   D[j]=0;
   deta[j]=0;
   dj[j]=S[0];         //有限域内的指数表示。

  
   //int max,maxIn=0;
   //int temp;
   //int sum;

   for(j=2;j<2*t+2;j++)
	{
		if(dj[j-1]!=N)
		{
	     // 找到max(i-D(i)) 并且di!=N
		 // step0: to find the max(i-D(i)) and di!=N
		  max=deta[0];
		  maxIn=0;
			for(i=j-2;i>=1;i--)
			{
			  if(max< deta[i] && dj[i]!=N)
				{ max=deta[i];
				  maxIn=i;
				}
			}

        // 更新ErrorLoc(j+1)=ErrorLoc(i)+dj/di*x^(j-i)*ErrorLoc(i) 
			D[j]=poly(ErrorLoc,dj,j-1,maxIn,t,m); 
			deta[j]=j-D[j]-1;   //更新j-D[j]
          
		}// if(dj[j-1]!=N)
		else   // dj[j-1]==N
		{
			for(i=0;i<2*t;i++)
				ErrorLoc[Row*j+i]=ErrorLoc[Row*(j-1)+i];

			deta[j]=1+deta[j-1];
			D[j]=D[j-1];
			
		}

		// update dj;
			if(j!=2*t+1)
			{
			sum=S[j-1];
			for(vol=1;vol<=D[j];vol++)
			{
				temp=MultInGf(ErrorLoc[Row*j+vol],S[j-vol-1],N);
				sum=AddInGf(sum,temp,m);
			}
			dj[j]=sum;
			}
	}

   //int thelast=j-1;
   thelast=j-1;
     //use the chien method to find the polynomial root.
	 //用钱收索法计算多项式的根。
     //求错误位置。
	 //root[] 存放错误位置。
	
    //int	k=0,current;
	//int RootNum=D[j-1];  //根的个数。
	//int *root=(int *)calloc(RootNum,sizeof(int));
   RootNum=D[j-1];
   root=(int *)calloc(RootNum,sizeof(int));

	for (i=N-1;i>=0;i-- )
	{
        sum=0;
		for(j=1;j<=RootNum;j++)
		{
			current=MultInGf((i*j)% N ,ErrorLoc[Row*thelast+j],N);
			sum=AddInGf(current,sum,m);
		}
		if(sum==N)
		{root[k]=N-i;
		 k++;
		}
	}

////////////////////////////////////////////////////////
// use the Gauss method again to find the error value.
// 计算错误值。
// 下面的方法是基于高斯消元法进行的。
   //int mik;
   //int sign;
   //int *xe=(int *)calloc(RootNum,sizeof(int));  //在xe数组里存放了错误值。
   //int * ErrorMat=(int *)calloc(RootNum*RootNum,sizeof(int));
   //int * B= (int *)calloc(RootNum,sizeof(int));
    xe=(int *)calloc(RootNum,sizeof(int));  //在xe数组里存放了错误值。
    ErrorMat=(int *)calloc(RootNum*RootNum,sizeof(int));
    B= (int *)calloc(RootNum,sizeof(int));

   RootNum=k;
   if(k!=0)   //如果没有错误值，下面的步骤就不用了。
   {
   //建立错误值线性多项式〔矩阵〕。
   for(i=0;i<RootNum;i++)
   {
	   for(j=0;j<RootNum;j++)
	   {
		   ErrorMat[i*RootNum+j]=((i+1)*root[j]) % N;      /// 可能有bug发生
	   }
   B[i]=S[i];
   }
   
   //高斯法求解线性多项式。
	  for(k=0;k<RootNum-1;k++)  // 一共有的行数。
      {
       for(i=k+1;i<RootNum;i++)  //计算 现在所在的行数以下的各行
       {
         mik=(abs(ErrorMat[i*RootNum+k]-ErrorMat[k*RootNum+k])) % N;  //a^i / a^j
         sign=(ErrorMat[i*RootNum+k]-ErrorMat[k*RootNum+k])>0 ? 1:-1;

		 for(j=k+1;j<RootNum;j++)  //对于本行中的所有元素
         {
			 if(sign>0)
				 ErrorMat[i*RootNum+j]=AddInGf(ErrorMat[i*RootNum+j],MultInGf(mik,ErrorMat[k*RootNum+j],N),m);
			 else
				 ErrorMat[i*RootNum+j]=AddInGf( MultInGf(ErrorMat[i*RootNum+j],mik,N), ErrorMat[k*RootNum+j] ,m);
         }
		 if (sign>0)
            B[i]=AddInGf(B[i],MultInGf(mik,B[k],N),m);
		 else
			B[i]=AddInGf(MultInGf(B[i],mik,N), B[k], m);
       }
      }	 

	 // initial the x
   	 //回代求解
	 for (i=0;i<RootNum;i++ )
	 {
		 xe[i]=N;
	 }
	 /////////////////////////////////////////////////////////////////////////////
	 xe[RootNum-1]=DivInGf(B[RootNum-1],ErrorMat[(RootNum-1)*RootNum+RootNum-1],N);  //GF divide

         current=0;
		 for(i=RootNum-2;i>=0;i--)
	     {
			sum=N;
			for(j=i+1;j<=RootNum-1;j++)
			 {
				current=MultInGf(ErrorMat[i*RootNum+j],xe[j],N);
				sum=AddInGf(current,sum,m);
			 }
			   temp=AddInGf(B[i],sum,m);
			   xe[i]=DivInGf(temp,ErrorMat[i*RootNum+i],N);
		 }
	  ////////////// 在xe数组里存放了错误值。/////
		//更正接收值。R[]存放接收值。
		//int CorrectR=0;
          for (i=0;i<N;i++)
		  { if(i==root[CorrectR])
			  {R[i]=AddInGf(R[i],xe[CorrectR],m);
			  CorrectR++;
			  }
		  }
   }//if(k!=0)
   free(xe);  //free memory
   free(D); 
   free(deta);
   free(dj);
   free(ErrorLoc);
   free(ErrorMat);
   free(B); 
   free(root);
}