encode_rs.c

这个文件包括wimax中所有的编解码源代码

/*****************************************************************************/
/*   FIle Name : encode_rs.c                                                 */
/*   Description : Encoder of Reed-Solomon FEC                               */
/*                 This RS encoder may NOT be compliant with 802.16.2004 spec*/
/*                 Because this encoder's output is not matched with an      */
/*                 example listed in :                                       */
/*                 8.3.3.5 Example OFDM uplink RS-CC encoding(pp.444)        */
/*                 In the spec the position of parities is not clear enough. */
/*                 In the above example of OFDM uplink, the paritys are      */
/*                 added as prefix. While in another spec like Homeplug      */
/*                 parities are added as suffix. The latter is easier to     */
/*                 calculate the parities because no SRAMs necessary in      */
/*                 encoder. In this cmodel, I took the formaer one as OFDM   */
/*                 uplink example. And the calculation order is reversed.    */
/*   author : miffie                                                         */
/*   Date   : sep/20/05                                                      */
/*   Copyright (c) 2005 miffie   All rights reserved.                        */
/*****************************************************************************/
#define mm  8           /* RS code over GF(2**4) - change to suit */

void generate_gf(int *alpha_to , int *index_of )
/* generate GF(2**mm) from the irreducible polynomial p(X) in pp[0]..pp[mm]
   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**mm)
*/
 {
   register int i, mask ;
   static int pp = 0x1d ;
   static int NN = 255 ;

  mask = 1 ;
  alpha_to[mm] = 0 ;
  for (i=0; i<mm; i++)
   { alpha_to[i] = mask ;
     index_of[alpha_to[i]] = i ;
     if ((pp>>i)&0x1)
       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 ;
     index_of[alpha_to[i]] = i ;
   }
  index_of[0] = -1 ;
 }


char gf_multiply(char a , char b ) { //gf_multiply
   static int pp = 0x1d ;
   static int NN = 255 ;
   char ii, out ;
   short tmp ;
   out = 0 ;
   tmp = a & 0xff ;
   for(ii=0;ii<8;ii++) {
     out ^= ((b>>ii)&0x1) ? tmp : 0 ;
     tmp = tmp<<1 ;   
     if (tmp&0x100) tmp = (tmp&0xff) ^ pp ;
   }
   return ( out ) ;
} //gf_multiply

void gen_poly(int *alpha_to , int *index_of , int *gg , char RR)
/* Obtain the generator polynomial of the tt-error correcting, length
  nn=(2**mm -1) Reed Solomon code  from the product of (X+alpha**i), i=1..2*tt
*/
 {
   register int i,j ;
   static int NN = 255 ;

   gg[0] = 2 ;    /* primitive element alpha = 2  for GF(2**mm)  */
   gg[1] = 1 ;    /* g(x) = (X+alpha) initially */
   for (i=2; i<=RR; i++)
    { gg[i] = 1 ;
      for (j=i-1; j>0; j--) {
        if (gg[j] != 0)  gg[j] = gg[j-1]^ alpha_to[(index_of[gg[j]]+i)%NN] ;
        else gg[j] = gg[j-1] ;
        //printf("gg[%3x]=%3x\n", j, gg[j] ) ;
      }
      gg[0] = alpha_to[(index_of[gg[0]]+i)%NN] ;     /* gg[0] can never be zero */
    }
   /* convert gg[] to index form for quicker encoding */
   //for (i=0; i<RR; i++) { 
   // printf("gg[%3x] = %3x \n", i, index_of[gg[i]] ) ;
   //}
 }


struct binaryset encode_rs( struct binaryset datain , char RR)
//RR is the number of parity byte or 2*T , 
//where T as the number of byte to be corrected
/* take the string of symbols in data[i], i=0..(k-1) and encode systematically
   to produce 2*tt parity symbols in bb[0]..bb[2*tt-1]
   data[] is input and bb[] is output in polynomial form.
   Encoding is done by using a feedback shift register with appropriate
   connections specified by the elements of gg[], which was generated above.
   Codeword is   c(X) = data(X)*X**(nn-kk)+ b(X)          */
 {
   static int NN = 255 ;
   short KK ;
   short pad ;
   struct  binaryset bset ;
   char    *top ;
   register int i,j ;
   int feedback ;
   int alpha_to [NN+1], index_of [NN+1], gg [RR+1] ;
   int bb[RR] ;
   

// Initializations
  /* generate the Galois Field GF(2**mm) */
  generate_gf(&alpha_to[0], &index_of[0]) ;
  //printf("Look-up tables for GF(2**%2d)\n",mm) ;
  //printf("  i   alpha_to[i]  index_of[i]\n") ;

  //for (i=0; i<=NN; i++)
  // printf("%3x      %3x          %3x\n",i,alpha_to[i],index_of[i]) ;
  //printf("\n\n") ;
  /* compute the generator polynomial for this RS code */
  gen_poly(&alpha_to[0], &index_of[0], &gg[0], RR) ;

// Calculations
  PRINTF("encode_rs size=%d RR=%d\n", datain.size, RR ) ;
  bset.size = 0 ;
  //add pads
  //pad is the number of padding byte  as prefix
  KK = NN-RR ;
  pad = KK-datain.size ;
  if (pad>0) bset = pad_binaryset(pad) ;
  bset = cat_binaryset(bset, datain ) ;
  print_binaryset(bset) ;

  if ((top = (char *)malloc((datain.size+RR)*sizeof(char)) ) == NULL)  {
     PRINTF( " malloc failed in encode_rs.c\n") ;
  } //fail
  else { //allocated
   for (i=0; i<RR; i++)   bb[i] = 0 ;
   for (i=KK-1; i>=0; i--) { //each sample
       feedback = (bset.data[i]&0xff)^bb[RR-1] ;
       for (j=RR-1; j>0; j--) {
              bb[j] = bb[j-1]^gf_multiply(gg[j],feedback) ;
              //printf("bb[%x %x]=%x\n", i, j, bb[j] ) ;
       }
       bb[0] = gf_multiply(gg[0],feedback) ;
   } //each sample

   /* put the transmitted codeword, made up of data plus parity, in recd[] */
   for (i=0; i<RR; i++)   top[i] = bb[i] ;
   for (i=0; i<datain.size; i++)   top[i+RR] = datain.data[i] ;
   bset.format = 1 ;
   bset.size = datain.size+RR ;
   bset.data = top ;
  } //allocated
  return( bset ) ;
 } //encode_rs