uep_rcpcc.c

Go to the documentation of this file.

#include "standard.h"
#include "rcpcc_hg16.h"
/* #include "types.h" */
#include "uep_rcpcc.h"
/* #include "defs.h" */

#define TERMINATEPACKET 1
/* 0: do not assume tail bits
   1: assume tail bits */

extern int debug;
static int    ccx[MAXINPUTBITS][RCPCCDIM];
static double rcx[MAXINPUTBITS][RCPCCDIM];

void ConvBits2Bytes(int *bit_array, unsigned char *byte_array, int N);     


/****************************************************************\
 This function calculates the number of input bits (K) for
 a given rate type (Rtype) and packet lenght (N).
 \****************************************************************/

int rcpcc16_getK(Rtype,N,CRCBytes)
int Rtype;
int N;
int CRCBytes;
{
  int K;
  
  switch(Rtype) 
    {
    case 0: K=(8*(N*8/32)-CRCBytes*8-TAILBITS)/8;  break; /* rate 8/32  */
    case 1: K=(8*(N*8/31)-CRCBytes*8-TAILBITS)/8; break; /*      8/31 */
    case 2: K=(8*(N*8/30)-CRCBytes*8-TAILBITS)/8; break; /*      8/30 */
    case 3: K=(8*(N*8/29)-CRCBytes*8-TAILBITS)/8; break; /*      8/29 */
    case 4: K=(8*(N*8/28)-CRCBytes*8-TAILBITS)/8; break; /*      8/28 */
    case 5: K=(8*(N*8/27)-CRCBytes*8-TAILBITS)/8; break; /*      8/27 */
    case 6: K=(8*(N*8/26)-CRCBytes*8-TAILBITS)/8; break; /*      8/26 */
    case 7: K=(8*(N*8/25)-CRCBytes*8-TAILBITS)/8; break; /*      8/25 */
    case 8: K=(8*(N*8/24)-CRCBytes*8-TAILBITS)/8; break; /*      8/24 */
    case 9: K=(8*(N*8/23)-CRCBytes*8-TAILBITS)/8; break; /*      8/23 */
    case 10: K=(8*(N*8/22)-CRCBytes*8-TAILBITS)/8; break; /*      8/22 */
    case 11: K=(8*(N*8/21)-CRCBytes*8-TAILBITS)/8; break; /*      8/21 */
    case 12: K=(8*(N*8/20)-CRCBytes*8-TAILBITS)/8; break; /*      8/20 */
    case 13: K=(8*(N*8/19)-CRCBytes*8-TAILBITS)/8; break; /*      8/19 */
    case 14: K=(8*(N*8/18)-CRCBytes*8-TAILBITS)/8; break; /*      8/18 */
    case 15: K=(8*(N*8/17)-CRCBytes*8-TAILBITS)/8; break; /*      8/17 */
    case 16: K=(8*(N*8/16)-CRCBytes*8-TAILBITS)/8; break; /*      8/16 */
    case 17: K=(8*(N*8/15)-CRCBytes*8-TAILBITS)/8; break; /*      8/15 */
    case 18: K=(8*(N*8/14)-CRCBytes*8-TAILBITS)/8; break; /*      8/14 */
    case 19: K=(8*(N*8/13)-CRCBytes*8-TAILBITS)/8; break; /*      8/13 */
    case 20: K=(8*(N*8/12)-CRCBytes*8-TAILBITS)/8; break; /*      8/12 */
    case 21: K=(8*(N*8/11)-CRCBytes*8-TAILBITS)/8; break; /*      8/11 */
    case 22: K=(8*(N*8/10)-CRCBytes*8-TAILBITS)/8; break; /*      8/10 */
    case 23:
      K=(8*(N*8/9)-CRCBytes*8-TAILBITS)/8; 
      break; /*      8/9 */
    case 24: K=( (N*8)-CRCBytes*8 - TAILBITS)/8; break; /*      8/8 */
    default: return(0);
    }
  
  if(K<=0) return(0);
 
  return(K);
}


int rcpcc16_encode(u,K, a1 , Rtype, N)
int u[];   /* input bits */
int K;      /*input array size */
buf_rcpc *a1; /* pointer to the rcpc buf structure */
int Rtype; /* rate type = 0-24 for rate R = 8/32, 8/31, .... 8/9, 8/8 */
int N;     /* length of output packet */

/*********************************************************************************\
 This function uses the code rates
   R =  8/32, 8/31, .... 8/9, 8/8
 to produce packets of length N from an input bitstream.
 This means, that for a fixed packet length N, a variable
 number of input bits is used to fill the packet. The number
 of input bits depends on the code rate R and is given by
   K = [N/Numerator(R)]*Denominator(R)- TAILBITS; 
   []=integer truncation 
 Note, that 4 tailbits are used to terminate any number of
 input bits. Any combination of N and R, which result in a
 negative or zero K will cause an error (return code 0). 
 Due to the truncation, the packet may not be completely filled
 with usefull information (e.g. N=360, Rtype=1 -> only 352 bits
 carry usefull information). The remaining bits will not be
 used for decoding.

 This function calls the function "rcpcc_coder" to do the
 actual encoding, and uses the global array ccx[][] to buffer the
 results.
\*******************************************************************************/

{
  int row;
  int i,d;
  int *temp;

  /*  int *temp = (int *)malloc(N * 8 * sizeof(int ));*/
  /*  int *temp = (int *)malloc((K+TAILBITS) * 4 * sizeof(int ));*/
  int *tt;
  int step = 32 - Rtype;
  
  temp = (int *)calloc(N * 8, sizeof(int )); 

  if (debug >= 2) { 
    printf(" inside routine rcpcc16_encode\n");
    printf(" Rtype, N, K are %d %d %d \n", Rtype, N, K);
    
    printf(" temp %d temp + N * 8 %d\n", temp, temp + N * 8); 
  } 
  row = 0;
  while (Rtype >=0)
    {
      if (debug >= 2)
        printf(" Rtype, row are %d %d \n", Rtype, row);
      
      rcpcc_coder(u,ccx,Rtype,K+TAILBITS);
      
      /* copy non-punctured bits in ccx[] to a1;
         map (-1,1) to (0,1) */
      
      tt = temp;
      
      if (row >0){
        for(i=0; i<(K+TAILBITS); i++)
          for(d=0; d<RCPCCDIM; d++)
            if ((ccx[i][d]!=0) && (px[Rtype][i%8][d] - px[Rtype + step][i%8][d] == 1)) {
              if(ccx[i][d]==-1) *tt++ = 0; 
              else              *tt++ = 1;
            }
      }
      else if (row == 0) 
        {
          for(i=0; i<(K+TAILBITS); i++)
            for(d=0; d<RCPCCDIM; d++)
              if ((ccx[i][d]!=0) ) {
                if(ccx[i][d]==-1) *tt++ = 0; 
                else              *tt++ = 1;
              }
        }
      
      ConvBits2Bytes(temp, a1->block[row], N);
      
      row++;
      Rtype = Rtype - step;
    }
  
  free(temp);
  return(1);
  
}

void rcpcc_coder(ix,ccx,rateType,packetLength)
int ix[];           /* array of information bits */
int ccx[][RCPCCDIM]; /* array of encoder bits, +/-1 data, 0 puncture position */
int rateType;       /* rate description in rcpcc.h */
int packetLength;   /* number of information bits including tail bits */
{
/***********************************************************************/
/* This function takes an array of information bits (ix) and generates */
/* a 2 dimensional array of encoder bits (ccx) generated by a rate     */
/* compatible punctured convolutional code.  The ccx dimensions are    */
/* packetLength x code_dimension where code dimension is 1/rate of     */
/* the basic code used to generate the rcpcc. The ccx array is filled  */
/* with data in the form of -1/+1 and uses 0 to denote puncture        */
/* positions!!!  The different rates are specifed with the parameter   */
/* rateType, which describes the various rates supported.  The packet  */
/* length is set by the number of information bits in each packet,     */
/* and in general will vary depending on the rate selected.  The       */
/* ix and ccx arrays should be sized in accordance to the maximum      */
/* packet length supported.                                            */
/*                                                                     */
/* The description of the rcpcc is done with global variables in the   */
/* rcpcc.h file:                                                       */
/*                                                                     */
/* Constants:                                                          */
/* RCPCCDIM  1/rate of basic code generating rcpcc, typ 2-4.           */
/* CONSTRAINTLENGTH -  constraint length of rcpcc, typ 4-7.            */
/* RATETYPES - number of different rates supported by RCPCC, typ 2-4.  */
/* MAXPUNCTUREPERIOD - largest puncture pattern period for all rates   */
/* TAILBITS - number of bits required to terminate code in packet      */
/* TERMINATEPACKET - 0=do not use tail bits, 1=use tail bits           */
/*                                                                     */
/* Global Variables:                                                   */
/* gx[CONSTRAINTLENGTH][RCPCCDIM] - generating polynomial of rcpcc     */
/* px[RATETYPES][MAXPUNCTUREPERIOD][RCPCCDIM] - puncture tables        */
/* puncturePeriod[Rtype] - periods of puncturing rates        */
/***********************************************************************/
  
  int i;
  int d;
  int k;

  for(i=0;i<packetLength;i++) {
    for (d=0;d<RCPCCDIM;d++) {
      /* clear encoder output array */
      
      ccx[i][d] = 0;

      /* compute convolutional code output */
      /* state set initially to 0          */
      /* use tail bits in packet to terminate packet */
      
      for (k=0;k<CONSTRAINTLENGTH;k++)
        if ( (i >= k)  && !(((i-k)>=(packetLength-TAILBITS)) && TERMINATEPACKET) )
          ccx[i][d] = (ccx[i][d] + ix[i-k]*gx[k][d]) % 2;
      
      /* map (0,1) data into (-1,1) and set punctured positions to 0 */
      ccx[i][d] = (2*ccx[i][d] - 1) * px[rateType][i%puncturePeriod][d];
      
    } /* for */
  } /* for */

} /************************* rcpcc_coder() *******************************/ 

void ConvBits2Bytes(int *bit_array, unsigned char *byte_array, int N)
{
  int i, j;

  for (i =0;i< N; i++){
    byte_array[i] = 0;
    for (j=0; j< 8; j++){
      byte_array[i] = byte_array[i] | (bit_array[i* 8+j] << (7-j) ); 
    }
  }
}


void ConvBytes2Bits(unsigned char *byte_array, int *bit_array, int N)
{
  int i, j;

  for (i =0;i< N; i++){
    for (j=0; j< 8; j++){
      bit_array[i* 8 + j] = (byte_array[i] >> (7-j)) &1;
    }
  }
}

/****************************************************************
 This function decodes packets of length N at code rates
   R = 8/32, 8/31, .... 8/9, 8/8 
 to produce K bits of an output bitstream.
   K = [N/Numerator(R)]*Donomator(R)-TAILBITS; 
   []=integer truncation 
 Note, that for a given packet length N, the number of decoded 
 bits K depends on the code rate R. On an error 0 is returned.

 This function calls the function "rcpcc_decoder" to do the
 actual decoding, and uses the global array rcx[][] to buffer the
 results.
****************************************************************/
int rcpcc16_decode(rx,du,Rtype,N, ppx, CRCBytes)
     int rx[];  /* received bits; x[] after channel                  */
     int du[];  /* decoded input bits u[]                            */
     int Rtype; /* rate type = 0-24 for rate R = 8/32, 8/31, .... 8/9, 8/8 */
     int N;     /* length of output packet; N = 8*k                  */
     int ppx[8][4];  /* the puntureing table */
                 int CRCBytes; /* number of CRC bytes to use */
{
  int K; /* number of decoded bits */
  int i,d,j;
  int info_dim;
  /* check the input */

  K=rcpcc16_getK(Rtype,N,CRCBytes);
  if(K==0) return(0);
  info_dim =(K+ CRCBytes) * 8  + TAILBITS; 
  if (debug >= 2) {
                printf(" K, info_dim %d %d\n", K, info_dim);
  
/* fill rcx[] with (0,-1,+1) depending on received bits rx[], 
     rate type and related puncturing pattern px[][][] */
  
    for (i=0; i< 8; i++){
      for (j=0; j< 4; j++){
        printf("%d ", ppx[i][j]);
      }printf("\n");
    }
        }
      
  
  for(i=0; i<(info_dim); i++)
    for(d=0; d<RCPCCDIM; d++)
      if(ppx[i%puncturePeriod][d]==0)
        rcx[i][d] = 0.0;
      else
        if(*rx++) rcx[i][d] =  1.0;
        else      rcx[i][d] = -1.0;
  
  /* calculate du[] from rcx[][] */
  
  if (debug >= 2)
                printf(" before  rcpcc_decoder\n");
  fflush(stdout);
        rcpcc_decoder(rcx,du,Rtype,info_dim, ppx);
  if (debug >= 2)
                printf(" after  rcpcc_decoder\n");
  
  return(1);
}

void rcpcc_decoder(rcx,rix,rateType,packetLength, ppx)
double rcx[][RCPCCDIM]; /* array of encoder bits, +/-1 data, 0 puncture position */
int rix[];              /* array of information bits */
int rateType;           /* rate description in rcpcc.h */
int packetLength;       /* number of information bits including tail bits */
int ppx[8][4];
{
/****************************************************************************/
/* This function takes an array of received codevectors(rcx) and            */
/* generates the most likely set of input vectors(rix) using the            */
/* Viterbi algorithm.  The ccx dimensions are  packetLength x               */
/* code_dimension where code dimension is 1/rate of the basic code          */
/* used to generate the rcpcc.  The different rates and puncturing          */
/* tables are specifed with the parameter rateType, which describes         */
/* the various rates supported.  The packet length is set by the            */
/* number of information bits in each packet, and in general will           */
/* vary depending on the rate selected.                                     */
/*                                                                          */
/* The description of the rcpcc trellis is done with global variables       */
/* in the rcpcc.h file.  In additions to the encoder variables, the         */
/* following are used:                                                      */
/*                                                                          */
/* Constants:                                                               */
/* STATES - number of states in the Trellis                                 */
/* INPUTS - number of inputs to the convolutional coder                     */
/* BRANCHES - number of branches from each state in trellis = INPUTS        */
/* OUTPUTS - number of outputs (symbols) generated by coder                 */
/* TL      - Truncation Length of VA                                        */
/* LARGENUMBER - A value >> metrics, used to approximate infinity           */
/*                                                                          */
/* Global Variables:                                                        */
/* dsignal[OUTPUTS][RCPCCDIM] - codesymbols correponsing to rcpcc outputs   */
/* prevState[STATES][BRANCHES] - reverse transitions describing trellis     */
/* prevOutput[STATES][BRANCHES] - outputs corresponding to transitions      */
/****************************************************************************/

  double VAmetric[TL][STATES];    /* accumulated state metric             */
  int VAstate[TL][STATES];        /* best previous state path             */
  double branchMetric[OUTPUTS];   /* branch metric based on branch output */

  int bin;    /* index for circular array used to store VA data */
  int state;  /* index for VA calculations one state at a time  */

  int i, j;      /* index for each step in the VA, = # info bit in packet */
  int d;      /* index for codevector dimension */
  int output; /* index for possible symbols generated by code */
  int branch; /* index for number of branches from each state in trellis */

  int trace;  /* index for traceback in VA */

  double metric;    /* temporary register for storing state metric */
  double minMetric; /*temporary register for storing minimum state metric */
  int minState;     /* temporary register for storing minimum state index */

  printf("rcpcc_decoder - rateType %d packetLength %d\n",rateType, packetLength);


  /* Initialize Viterbi Decoder */
  for(bin=0;bin<TL;bin++) {
    for(state=0;state<STATES;state++) {
      if (state==0)
        VAmetric[bin][state] = 0;
      else
        VAmetric[bin][state] = LARGENUMBER;
      VAstate[bin][state] = 0;
      } /* for */
  } /* for */

  /* Process Samples */
  for(i=0;i<packetLength;i++) {

    /* Compute Path Metrics */
    /* distance() function includes puncturing */
    for (output=0;output<OUTPUTS;output++) {
      branchMetric[output] = distance(rcx[i],
                                      dsignal[output],
                                      ppx[i%puncturePeriod]);
      } /* for */


    /* ACS */
    /* Results stored in circular array of size TL                      */
    /* TERMINATEPACKET flag enables tail bit forcing pruning of trellis */
    bin = i%TL; /* array index */ 

    for (state=0;state<STATES;state++) {
      for (branch=0;branch<BRANCHES;branch++) {
        metric = VAmetric[(bin-1+TL)%TL][prevState[state][branch]] +
                 branchMetric[prevOutput[state][branch]];
        if(metric<VAmetric[bin][state] || (branch==0)) {
            VAmetric[bin][state] = metric;
            VAstate[bin][state] = prevState[state][branch];
          } /* if */      
        } /* for */
      } /* for */
 
    /* Trellis pruning to terminate packet */
    /* Set metric of invalid states to infinity */
    if((i+TAILBITS>=packetLength) && TERMINATEPACKET)
      for (state=0;state<STATES;state++) 
        if (state % (2<<(TAILBITS+i-packetLength)) != 0)
          VAmetric[bin][state] = VAmetric[bin][state] + LARGENUMBER;

    /* find minimum state */
    minState = 0;
    minMetric = VAmetric[bin%TL][0];
    for(state=1;state<STATES;state++) {
      if (VAmetric[bin%TL][state] < minMetric) {
        minState = state;
        minMetric = VAmetric[bin%TL][state];
        } /* if */
      } /* for */

 
    /* Trace back and truncate VA */
    /* Preliminary best path is stored in ix  */
    /* Next sample overwrites best path       */
    /* Last sample writes final best path     */


    if ( (i>=TL) || (i==(packetLength-1)) ) {

      for(trace=0;((trace<i)&&(trace<TL));trace++) {
        rix[i-trace] = minState % 2;
        
        minState = VAstate[(bin-trace+TL)%TL][minState];

      } /* for */
      rix[i-trace] = minState % 2;

    } /* if */
    
  } /* for i */

} /************************* rcpcc_decoder() *******************************/ 

double distance(rcx,dsignal,px)
     double *rcx;     /* received codevector */
     double *dsignal;  /* codesymbols */
     int *px;         /* puncture pattern */
{
  /**********************************************************************/
  /* This function computes the branch metric based on the distance     */
  /* between the received codevector and the codesymbols.  It takes     */
  /* into account that a punctured symbol may have been received.       */
  /**********************************************************************/
  double error;
  int i;
  error = 0;
  for(i=0;i<RCPCCDIM;i++)
    error += (rcx[i]-dsignal[i])*(rcx[i]-dsignal[i])*px[i];
  return(error);
} /************************* distance() ***************************** */

---