gen_gf.c

一份比较有价值的有关ＲＳ编码的文章 欢迎下载

/********************************************************************************
 * File:     	Gen_GF.c							*
 * Title:    	Genarate conversion table and genarator ploynomial		*
 *		for Galoias Field  GF(2^mm)					*
 * Authors:  	lzg								*
 * Date:     	2003.4								*
 * Input:	macro define mm,kk,b0								*
 *		kk, message length 						*
 *		b0,g(x)=(x+@^b0)(x+@^(b0+1))......(x+@^(b0+2^mm-1-kk)		*
 * Return:	return pointer of table Alpha_to and table Index_of,		*
 *		generator ploynomial gg						*
 * Note:     	Now mm only suppuly 8 4 and 3					*
 *******************************************************************************/
 
 
 /*******************************************************************************
  generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
   lookup tables:  index->polynomial form   alpha_to[] contains j=alpha**i;
                   polynomial form -> index form  index_of[j=alpha**i] = i
   alpha=2 is the primitive element of GF(2**m)
   HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows:
        Let @ represent the primitive element commonly called "alpha" that
   is the root of the primitive polynomial p(x). Then in GF(2^m), for any
   0 <= i <= 2^m-2,
        @^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
   where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
   of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
   example the polynomial representation of @^5 would be given by the binary
   representation of the integer "alpha_to[5]".
                   Similarily, index_of[] can be used as follows:
        As above, let @ represent the primitive element of GF(2^m) that is
   the root of the primitive polynomial p(x). In order to find the power
   of @ (alpha) that has the polynomial representation
        a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
   we consider the integer "i" whose binary representation with a(0) being LSB
   and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
   "index_of[i]". Now, @^index_of[i] is that element whose polynomial 
    representation is (a(0),a(1),a(2),...,a(m-1)).
   NOTE:
        The element alpha_to[2^m-1] = 0 always signifying that the
   representation of "@^infinity" = 0 is (0,0,0,...,0).
        Similarily, the element index_of[0] = -1 always signifying
   that the power of alpha which has the polynomial representation
   (0,0,...,0) is "infinity".
*******************************************************************************/

#include <math.h>
#include <stdio.h>
#include "stdlib.h"
#include "time.h"
//#include "conio.h"

#ifndef GFMM_KK_B0
#define GFMM_KK_B0
#define mm		8
#define nn		255
#define kk		243
#define tt		6
#define b0		120
#define nn_short	31
#define kk_short	19
#endif

/**** Primitive polynomial ****/
/*int pp[mm+1] = { 1, 0, 1, 1, 1, 0, 0, 0, 1}; */	/* 1 + x^2 + x^3 + x^4 + x^8 */
/*int pp[mm+1] = {1, 0, 1, 0, 0, 1};*/			/* 1 + x^2 + x^5*/
/*int pp[mm+1] = { 1, 1, 0, 0, 1}; */ 			/* 1 + x + x^4 */
/*int pp[mm+1] = {1,1,0,1}; */ 				/* 1 + x + x^3 */


void gen_gf(int *Alpha_to,int *Index_of,int *gg)
 {
  register int i,j, mask,x;
  int *pp;
    
  /*Init primitive polynomial*/
  pp = (int *) calloc((mm + 1),sizeof(int));
  switch(mm)
  {
  	case 3:
		*pp=1;
		*(pp+1)=1;
		*(pp+2)=0;
		*(pp+3)=1;
  		break;
  	case 4:
		*pp=1;
		*(pp+1)=1;
		*(pp+2)=0;
		*(pp+3)=0;
		*(pp+4)=1;
  		break;
  	case 5:
		*pp=1;
		*(pp+1)=0;
		*(pp+2)=1;
		*(pp+3)=0;
		*(pp+4)=0;
		*(pp+5)=1;
  		break;
  	case 8:
		*pp=1;
		*(pp+1)=0;
		*(pp+2)=1;
		*(pp+3)=1;
		*(pp+4)=1;
		*(pp+5)=0;
		*(pp+6)=0;
		*(pp+7)=0;
		*(pp+8)=1;
  		break;
  	default:
  		printf("Now the GF(2^%d) isn't supported",mm);
  		return;
  }


  /*generate table Alpha_to and Index_of for Galoias field GF(2^mm)*/
  mask = 1 ;

  *Alpha_to = 0 ;
  for (i=0; i<mm; i++)
  {
   *(Alpha_to + i) = mask ;
   if (pp[i]!=0)
       *(Alpha_to + mm) ^= mask ;
   mask <<= 1 ;
  }
  *(Index_of + *(Alpha_to + mm)) = mm ;
  mask >>= 1 ;
  for (i=mm+1; i<nn; i++)
   { if (*(Alpha_to + i - 1) >= mask)
        *(Alpha_to + i) = *(Alpha_to + mm) ^ ((*(Alpha_to + i - 1)^mask)<<1) ;
     else *(Alpha_to + i) = *(Alpha_to + i - 1)<<1 ;
   }
   for(i=0;i<=nn;i++)
   {
   	*(Index_of + *(Alpha_to + i)) = i ;
   }
  *Index_of = -1 ;

  /*generate generator ploynomial for Galoias field*/
  /* Obtain the generator polynomial of the tt-error correcting, length
  nn=(2**mm -1) Reed Solomon code from the product of (X+@**(b0+i)), i = 0, ... ,(2*tt-1)
  Examples: 	If b0 = 1, tt = 1. deg(g(x)) = 2*tt = 2.
 	g(x) = (x+@) (x+@**2)
		If b0 = 0, tt = 2. deg(g(x)) = 2*tt = 4.
	g(x) = (x+1) (x+@) (x+@**2) (x+@**3)
 */
  *gg = *(Alpha_to + b0);
  *(gg + 1) = 1 ;    /* g(x) = (X+@**b0) initially */
  for (i=2; i <= nn-kk; i++)
    {
      *(gg + i) = 1 ;
      /* Below multiply (gg[0]+gg[1]*x + ... +gg[i]x^i) by (@**(b0+i-1) + x) */
      for (j=i-1; j>0; j--)
      {
        if ((*(gg + j) == 0)||(*(Alpha_to + b0 + i - 1) == 0))
        	*(gg + j) = *(gg + j - 1) ;
        else
        	*(gg + j) = *(gg + j - 1)^ *(Alpha_to + (*(Index_of + *(gg + j)) + b0 + i - 1)%nn);
      }
      *gg = *(Alpha_to + (*(Index_of + *gg) + b0 + i - 1)%nn) ;     /* gg[0] can never be zero */
    }
   /* convert gg[] to index form for quicker encoding */
  for(i=0;i<=12;i++)
	  x=gg[i];
  for (i=0; i <= nn-kk; i++) 
	  *(gg + i) = *(Index_of + *(gg + i)) ;
  free(pp);
  return;
 }