generate.c

通信类程序

/*
**    FILE    : generate.c 
**    PURPOSE : The functions in this file can be used to generate binary
**              and non-binary codes.
**              The codes of which the generator polynomials can be generated
**              are :
**              - binary BCH
**              - non-binary BCH
**              - Reed-Solomon (which is in fact a subset of non-binary-BCH)
**              These codes are of practical interest in
**              FEC (Forward Error Control) - coding.
**    AUTHOR  : Bart De Canne, Barco NV.
**    COMPILER: BC++ 3.1 compiler
**    DEPENDENCIES:
**              Include-files: galois.h
**    DATE    : 01-09-1994
**    VERSION : 1.0
*/

#define _GENERATE
#include "galois.h"

static bool update(int *,int,int);
static bool is_primitive(void);

static pPOLYNOM pp_aux=NULL;


/* ##########   IRREDUCIBLE / PRIMITIVE / MINIMAL POLYNOMIALS ############ */

/* 
** Finds a primitive polynomial of the GF
** On exit: pp_prim contains prim.pol.
*/ 

void FindPrimitivePolynomial(void) {

   int k,d;
   int *pi1;                  /* array of (q+1) integers, each indicating  */
                              /* a number between 0 and p-1 -> generation  */
                              /* of all polynomials of degree q with       */
                              /* coeff. in GF(p)                           */
   int *pi2;                  /* idem for polynomials of degree <=q-1      */
   bool rem0;

   BEGIN("FindPrimitivePolynomial");
   d=pg_l->Exp;                 /* degree of primitive polynomial          */
   if(po_s->MaxNo != pg_l->Base) ERROR;
   pp_prim=AllocPolynom(pp_prim,pg_l->Base,d);
   pp_aux=AllocPolynom(pp_aux,pg_l->Base,d-1);
   pi1=(int*)malloc(sizeof(int) * (d+1));    /* d+1 integers -> degree <=d */
   pi2=(int*)malloc(sizeof(int) * d);        /* d integers -> degree <=d-1 */
   if(pi1==NULL || pi2==NULL) ERROR;
   
   memset((void*)pi1,0,sizeof(int)*(d+1));
   pi1[d]=1;                  /* force it to be a degree-q polynomial      */
   START_PACIFIER;
   pp_prim->Deg=d;            
   
   do{                  /* loop for generation of all degree-d polynomials */
      for(k=d;k>=0;k--)
         pp_prim->c[k]=pi1[k];
      PACIFIER(0);
      if(d!=1){         /* all degree 1 polynomials are irreducible        */

         memset((void*)pi2,0,sizeof(int)*d);
         pi2[1]=1;                        /* degree 1 polynomial           */

         do{            /* loop for generation of all degree 0..q-1 pol.   */
            for(k=d-1;k>=0;k--) 
               pp_aux->c[k]=pi2[k];
            DEGREE(pp_aux);
            rem0=DivPoly(pp_prim,pp_aux,NULL,NULL,po_s);
            if(rem0) break;     /* not irreducible                         */
            }
         while(update(pi2,po_s->MaxNo,d-1));
         }
      else 
         rem0=0;
      if(!rem0)         /* found an irreducible polynomial                 */ 
         if(is_primitive())
            break;
      }
   while(update(pi1,po_s->MaxNo,d));
   
   pp_aux=FreePolynom(pp_aux);
   free(pi1);free(pi2);
   STOP_PACIFIER;
   }

/*
** Gets increment for (q+1) integers, each with maximum value p-1
*/

static bool update(int *pi,int p,int q) {

   int i,j,max;

   max=p-1;

   j=0;
   while(pi[j]!=max && j<q) j++;
   i=j;
   while(pi[i]==max && pi[i+1]==max && i<q) i++;
   if(i==q && j==0)
      return FALSE;
   if(j)
      pi[0]++;
   else {
      pi[i+1]++;
      for(j=0;j<=i;j++)
         pi[j]=0;
      }
   return TRUE;
   }

/*
**    Checks for an irreducible polynomial to be primitive.
**    If it is found to be primitive, the function returns TRUE and <pg>
**    contains all GF-elements.
**    If it is not, FALSE is returned and the contents of <pg> should be
**    neglected.
*/

static bool is_primitive(void) {

   int p,i,k,l;
   pPOLYNOM pp_rem=NULL;
   bool is_prim=TRUE;

   p=pp_prim->Deg;
                              /* 0..郶(p^q-2) -> max.deg.p^q-2             */
   pp_aux=AllocPolynom(pp_aux,po_s->MaxNo,pg_l->MaxNo-2);
   pp_rem=AllocPolynom(pp_rem,po_s->MaxNo,p-1);

   memset(pg_l->pe[0].Alpha,0,8);                                    /* 0  */
   memset(pg_l->pe[1].Alpha,0,8);                                    /* 1  */
   pg_l->pe[1].Alpha[0]=1;

   for(i=2;i<pg_l->MaxNo && is_prim;i++) {            /* 郶1,..,郶(p^q-2)  */
      SET_POLY(pp_aux,i-1,1);                         /* D^i <-> 郶i       */
      DivPoly(pp_aux,pp_prim,NULL,pp_rem,po_s);
      memset(pg_l->pe[i].Alpha,0,8);
      for(k=p-1;k>=0;k--)
         pg_l->pe[i].Alpha[k] = (byte)pp_rem->c[k];
      for(l=0;l<i;l++) {
         for(k=0;k<p;k++) {
            if(pg_l->pe[l].Alpha[k] != pg_l->pe[i].Alpha[k])
               break;
            }
         if(k==p) {               /* then pe[l] == pe[i] -> not primitive  */
            is_prim=FALSE;
            break;
            }
         }
      }
   pp_aux=FreePolynom(pp_aux);pp_rem=FreePolynom(pp_rem);
   return(is_prim);
   }

/* 
** Gets the minimal polynomial for each field element (except for 0 and 1)
** and stores this into <pg> structure
** !! function performs initialization of these poly's in <pg>
*/ 

void FindMinimalPolynomials(void) {

   int i,j,k,order;
   pPOLYNOM pp_min;
   
   pp_aux=AllocPolynom(pp_aux,pg_l->Base,1);
   pp_aux->Deg=1;
   START_PACIFIER;

   for(i=2;i<pg_l->MaxNo;i++) {
      PACIFIER(100*i/pg_l->MaxNo);
                                 /* We first get the order of the element  */
                                 /* since this will determine the degree   */
                                 /* of the minimal polynomial              */
      for(order=1;
          i_pow(i,(int)pow((double)pg_l->Base,(double)order),pg_l,po_l) != i;
          order++) ;
      pp_min=pg_l->pe[i].pp=AllocPolynom(pg_l->pe[i].pp,pg_l->Base,order);
                                 /* Now we'll actually start constructing  */
                                 /* it : 磬i(D)=(D-鄆)(D-鄆^2)...(D-鄆^q)  */
                                 /* where q equals the order of 鄆.        */
      SET_POLY(pp_min,0,1);
      for(j=0;j<order;j++) {
         pp_aux->c[1]=1;
         pp_aux->c[0]=
            po_l->InvAdd[
               i_pow(i,(int)pow((double)pg_l->Base,(double)j),pg_l,po_l)];
         pp_min=MultPoly(pp_min,pp_aux,pp_min,po_l,COPY);
         }
                                 /* coeff. of <pp_min>