Main Page | Class List | File List | Class Members | File Members

uep_rcpcc.c

Go to the documentation of this file.
00001 #include "standard.h"
00002 #include "rcpcc_hg16.h"
00003 /* #include "types.h" */
00004 #include "uep_rcpcc.h"
00005 /* #include "defs.h" */
00006 
00007 #define TERMINATEPACKET 1
00008 /* 0: do not assume tail bits
00009    1: assume tail bits */
00010 
00011 extern int debug;
00012 static int    ccx[MAXINPUTBITS][RCPCCDIM];
00013 static double rcx[MAXINPUTBITS][RCPCCDIM];
00014 
00015 void ConvBits2Bytes(int *bit_array, unsigned char *byte_array, int N);     
00016 
00017 
00018 /****************************************************************\
00019  This function calculates the number of input bits (K) for
00020  a given rate type (Rtype) and packet lenght (N).
00021  \****************************************************************/
00022 
00023 int rcpcc16_getK(Rtype,N,CRCBytes)
00024 int Rtype;
00025 int N;
00026 int CRCBytes;
00027 {
00028   int K;
00029   
00030   switch(Rtype) 
00031     {
00032     case 0: K=(8*(N*8/32)-CRCBytes*8-TAILBITS)/8;  break; /* rate 8/32  */
00033     case 1: K=(8*(N*8/31)-CRCBytes*8-TAILBITS)/8; break; /*      8/31 */
00034     case 2: K=(8*(N*8/30)-CRCBytes*8-TAILBITS)/8; break; /*      8/30 */
00035     case 3: K=(8*(N*8/29)-CRCBytes*8-TAILBITS)/8; break; /*      8/29 */
00036     case 4: K=(8*(N*8/28)-CRCBytes*8-TAILBITS)/8; break; /*      8/28 */
00037     case 5: K=(8*(N*8/27)-CRCBytes*8-TAILBITS)/8; break; /*      8/27 */
00038     case 6: K=(8*(N*8/26)-CRCBytes*8-TAILBITS)/8; break; /*      8/26 */
00039     case 7: K=(8*(N*8/25)-CRCBytes*8-TAILBITS)/8; break; /*      8/25 */
00040     case 8: K=(8*(N*8/24)-CRCBytes*8-TAILBITS)/8; break; /*      8/24 */
00041     case 9: K=(8*(N*8/23)-CRCBytes*8-TAILBITS)/8; break; /*      8/23 */
00042     case 10: K=(8*(N*8/22)-CRCBytes*8-TAILBITS)/8; break; /*      8/22 */
00043     case 11: K=(8*(N*8/21)-CRCBytes*8-TAILBITS)/8; break; /*      8/21 */
00044     case 12: K=(8*(N*8/20)-CRCBytes*8-TAILBITS)/8; break; /*      8/20 */
00045     case 13: K=(8*(N*8/19)-CRCBytes*8-TAILBITS)/8; break; /*      8/19 */
00046     case 14: K=(8*(N*8/18)-CRCBytes*8-TAILBITS)/8; break; /*      8/18 */
00047     case 15: K=(8*(N*8/17)-CRCBytes*8-TAILBITS)/8; break; /*      8/17 */
00048     case 16: K=(8*(N*8/16)-CRCBytes*8-TAILBITS)/8; break; /*      8/16 */
00049     case 17: K=(8*(N*8/15)-CRCBytes*8-TAILBITS)/8; break; /*      8/15 */
00050     case 18: K=(8*(N*8/14)-CRCBytes*8-TAILBITS)/8; break; /*      8/14 */
00051     case 19: K=(8*(N*8/13)-CRCBytes*8-TAILBITS)/8; break; /*      8/13 */
00052     case 20: K=(8*(N*8/12)-CRCBytes*8-TAILBITS)/8; break; /*      8/12 */
00053     case 21: K=(8*(N*8/11)-CRCBytes*8-TAILBITS)/8; break; /*      8/11 */
00054     case 22: K=(8*(N*8/10)-CRCBytes*8-TAILBITS)/8; break; /*      8/10 */
00055     case 23:
00056       K=(8*(N*8/9)-CRCBytes*8-TAILBITS)/8; 
00057       break; /*      8/9 */
00058     case 24: K=( (N*8)-CRCBytes*8 - TAILBITS)/8; break; /*      8/8 */
00059     default: return(0);
00060     }
00061   
00062   if(K<=0) return(0);
00063  
00064   return(K);
00065 }
00066 
00067 
00068 int rcpcc16_encode(u,K, a1 , Rtype, N)
00069 int u[];   /* input bits */
00070 int K;      /*input array size */
00071 buf_rcpc *a1; /* pointer to the rcpc buf structure */
00072 int Rtype; /* rate type = 0-24 for rate R = 8/32, 8/31, .... 8/9, 8/8 */
00073 int N;     /* length of output packet */
00074 
00075 /*********************************************************************************\
00076  This function uses the code rates
00077    R =  8/32, 8/31, .... 8/9, 8/8
00078  to produce packets of length N from an input bitstream.
00079  This means, that for a fixed packet length N, a variable
00080  number of input bits is used to fill the packet. The number
00081  of input bits depends on the code rate R and is given by
00082    K = [N/Numerator(R)]*Denominator(R)- TAILBITS; 
00083    []=integer truncation 
00084  Note, that 4 tailbits are used to terminate any number of
00085  input bits. Any combination of N and R, which result in a
00086  negative or zero K will cause an error (return code 0). 
00087  Due to the truncation, the packet may not be completely filled
00088  with usefull information (e.g. N=360, Rtype=1 -> only 352 bits
00089  carry usefull information). The remaining bits will not be
00090  used for decoding.
00091 
00092  This function calls the function "rcpcc_coder" to do the
00093  actual encoding, and uses the global array ccx[][] to buffer the
00094  results.
00095 \*******************************************************************************/
00096 
00097 {
00098   int row;
00099   int i,d;
00100   int *temp;
00101 
00102   /*  int *temp = (int *)malloc(N * 8 * sizeof(int ));*/
00103   /*  int *temp = (int *)malloc((K+TAILBITS) * 4 * sizeof(int ));*/
00104   int *tt;
00105   int step = 32 - Rtype;
00106   
00107   temp = (int *)calloc(N * 8, sizeof(int )); 
00108 
00109   if (debug >= 2) { 
00110     printf(" inside routine rcpcc16_encode\n");
00111     printf(" Rtype, N, K are %d %d %d \n", Rtype, N, K);
00112     
00113     printf(" temp %d temp + N * 8 %d\n", temp, temp + N * 8); 
00114   } 
00115   row = 0;
00116   while (Rtype >=0)
00117     {
00118       if (debug >= 2)
00119         printf(" Rtype, row are %d %d \n", Rtype, row);
00120       
00121       rcpcc_coder(u,ccx,Rtype,K+TAILBITS);
00122       
00123       /* copy non-punctured bits in ccx[] to a1;
00124          map (-1,1) to (0,1) */
00125       
00126       tt = temp;
00127       
00128       if (row >0){
00129         for(i=0; i<(K+TAILBITS); i++)
00130           for(d=0; d<RCPCCDIM; d++)
00131             if ((ccx[i][d]!=0) && (px[Rtype][i%8][d] - px[Rtype + step][i%8][d] == 1)) {
00132               if(ccx[i][d]==-1) *tt++ = 0; 
00133               else              *tt++ = 1;
00134             }
00135       }
00136       else if (row == 0) 
00137         {
00138           for(i=0; i<(K+TAILBITS); i++)
00139             for(d=0; d<RCPCCDIM; d++)
00140               if ((ccx[i][d]!=0) ) {
00141                 if(ccx[i][d]==-1) *tt++ = 0; 
00142                 else              *tt++ = 1;
00143               }
00144         }
00145       
00146       ConvBits2Bytes(temp, a1->block[row], N);
00147       
00148       row++;
00149       Rtype = Rtype - step;
00150     }
00151   
00152   free(temp);
00153   return(1);
00154   
00155 }
00156 
00157 void rcpcc_coder(ix,ccx,rateType,packetLength)
00158 int ix[];           /* array of information bits */
00159 int ccx[][RCPCCDIM]; /* array of encoder bits, +/-1 data, 0 puncture position */
00160 int rateType;       /* rate description in rcpcc.h */
00161 int packetLength;   /* number of information bits including tail bits */
00162 {
00163 /***********************************************************************/
00164 /* This function takes an array of information bits (ix) and generates */
00165 /* a 2 dimensional array of encoder bits (ccx) generated by a rate     */
00166 /* compatible punctured convolutional code.  The ccx dimensions are    */
00167 /* packetLength x code_dimension where code dimension is 1/rate of     */
00168 /* the basic code used to generate the rcpcc. The ccx array is filled  */
00169 /* with data in the form of -1/+1 and uses 0 to denote puncture        */
00170 /* positions!!!  The different rates are specifed with the parameter   */
00171 /* rateType, which describes the various rates supported.  The packet  */
00172 /* length is set by the number of information bits in each packet,     */
00173 /* and in general will vary depending on the rate selected.  The       */
00174 /* ix and ccx arrays should be sized in accordance to the maximum      */
00175 /* packet length supported.                                            */
00176 /*                                                                     */
00177 /* The description of the rcpcc is done with global variables in the   */
00178 /* rcpcc.h file:                                                       */
00179 /*                                                                     */
00180 /* Constants:                                                          */
00181 /* RCPCCDIM  1/rate of basic code generating rcpcc, typ 2-4.           */
00182 /* CONSTRAINTLENGTH -  constraint length of rcpcc, typ 4-7.            */
00183 /* RATETYPES - number of different rates supported by RCPCC, typ 2-4.  */
00184 /* MAXPUNCTUREPERIOD - largest puncture pattern period for all rates   */
00185 /* TAILBITS - number of bits required to terminate code in packet      */
00186 /* TERMINATEPACKET - 0=do not use tail bits, 1=use tail bits           */
00187 /*                                                                     */
00188 /* Global Variables:                                                   */
00189 /* gx[CONSTRAINTLENGTH][RCPCCDIM] - generating polynomial of rcpcc     */
00190 /* px[RATETYPES][MAXPUNCTUREPERIOD][RCPCCDIM] - puncture tables        */
00191 /* puncturePeriod[Rtype] - periods of puncturing rates        */
00192 /***********************************************************************/
00193   
00194   int i;
00195   int d;
00196   int k;
00197 
00198   for(i=0;i<packetLength;i++) {
00199     for (d=0;d<RCPCCDIM;d++) {
00200       /* clear encoder output array */
00201       
00202       ccx[i][d] = 0;
00203 
00204       /* compute convolutional code output */
00205       /* state set initially to 0          */
00206       /* use tail bits in packet to terminate packet */
00207       
00208       for (k=0;k<CONSTRAINTLENGTH;k++)
00209         if ( (i >= k)  && !(((i-k)>=(packetLength-TAILBITS)) && TERMINATEPACKET) )
00210           ccx[i][d] = (ccx[i][d] + ix[i-k]*gx[k][d]) % 2;
00211       
00212       /* map (0,1) data into (-1,1) and set punctured positions to 0 */
00213       ccx[i][d] = (2*ccx[i][d] - 1) * px[rateType][i%puncturePeriod][d];
00214       
00215     } /* for */
00216   } /* for */
00217 
00218 } /************************* rcpcc_coder() *******************************/ 
00219 
00220 void ConvBits2Bytes(int *bit_array, unsigned char *byte_array, int N)
00221 {
00222   int i, j;
00223 
00224   for (i =0;i< N; i++){
00225     byte_array[i] = 0;
00226     for (j=0; j< 8; j++){
00227       byte_array[i] = byte_array[i] | (bit_array[i* 8+j] << (7-j) ); 
00228     }
00229   }
00230 }
00231 
00232 
00233 void ConvBytes2Bits(unsigned char *byte_array, int *bit_array, int N)
00234 {
00235   int i, j;
00236 
00237   for (i =0;i< N; i++){
00238     for (j=0; j< 8; j++){
00239       bit_array[i* 8 + j] = (byte_array[i] >> (7-j)) &1;
00240     }
00241   }
00242 }
00243 
00244 /****************************************************************
00245  This function decodes packets of length N at code rates
00246    R = 8/32, 8/31, .... 8/9, 8/8 
00247  to produce K bits of an output bitstream.
00248    K = [N/Numerator(R)]*Donomator(R)-TAILBITS; 
00249    []=integer truncation 
00250  Note, that for a given packet length N, the number of decoded 
00251  bits K depends on the code rate R. On an error 0 is returned.
00252 
00253  This function calls the function "rcpcc_decoder" to do the
00254  actual decoding, and uses the global array rcx[][] to buffer the
00255  results.
00256 ****************************************************************/
00257 int rcpcc16_decode(rx,du,Rtype,N, ppx, CRCBytes)
00258      int rx[];  /* received bits; x[] after channel                  */
00259      int du[];  /* decoded input bits u[]                            */
00260      int Rtype; /* rate type = 0-24 for rate R = 8/32, 8/31, .... 8/9, 8/8 */
00261      int N;     /* length of output packet; N = 8*k                  */
00262      int ppx[8][4];  /* the puntureing table */
00263                  int CRCBytes; /* number of CRC bytes to use */
00264 {
00265   int K; /* number of decoded bits */
00266   int i,d,j;
00267   int info_dim;
00268   /* check the input */
00269 
00270   K=rcpcc16_getK(Rtype,N,CRCBytes);
00271   if(K==0) return(0);
00272   info_dim =(K+ CRCBytes) * 8  + TAILBITS; 
00273   if (debug >= 2) {
00274                 printf(" K, info_dim %d %d\n", K, info_dim);
00275   
00276 /* fill rcx[] with (0,-1,+1) depending on received bits rx[], 
00277      rate type and related puncturing pattern px[][][] */
00278   
00279     for (i=0; i< 8; i++){
00280       for (j=0; j< 4; j++){
00281         printf("%d ", ppx[i][j]);
00282       }printf("\n");
00283     }
00284         }
00285       
00286   
00287   for(i=0; i<(info_dim); i++)
00288     for(d=0; d<RCPCCDIM; d++)
00289       if(ppx[i%puncturePeriod][d]==0)
00290         rcx[i][d] = 0.0;
00291       else
00292         if(*rx++) rcx[i][d] =  1.0;
00293         else      rcx[i][d] = -1.0;
00294   
00295   /* calculate du[] from rcx[][] */
00296   
00297   if (debug >= 2)
00298                 printf(" before  rcpcc_decoder\n");
00299   fflush(stdout);
00300         rcpcc_decoder(rcx,du,Rtype,info_dim, ppx);
00301   if (debug >= 2)
00302                 printf(" after  rcpcc_decoder\n");
00303   
00304   return(1);
00305 }
00306 
00307 void rcpcc_decoder(rcx,rix,rateType,packetLength, ppx)
00308 double rcx[][RCPCCDIM]; /* array of encoder bits, +/-1 data, 0 puncture position */
00309 int rix[];              /* array of information bits */
00310 int rateType;           /* rate description in rcpcc.h */
00311 int packetLength;       /* number of information bits including tail bits */
00312 int ppx[8][4];
00313 {
00314 /****************************************************************************/
00315 /* This function takes an array of received codevectors(rcx) and            */
00316 /* generates the most likely set of input vectors(rix) using the            */
00317 /* Viterbi algorithm.  The ccx dimensions are  packetLength x               */
00318 /* code_dimension where code dimension is 1/rate of the basic code          */
00319 /* used to generate the rcpcc.  The different rates and puncturing          */
00320 /* tables are specifed with the parameter rateType, which describes         */
00321 /* the various rates supported.  The packet length is set by the            */
00322 /* number of information bits in each packet, and in general will           */
00323 /* vary depending on the rate selected.                                     */
00324 /*                                                                          */
00325 /* The description of the rcpcc trellis is done with global variables       */
00326 /* in the rcpcc.h file.  In additions to the encoder variables, the         */
00327 /* following are used:                                                      */
00328 /*                                                                          */
00329 /* Constants:                                                               */
00330 /* STATES - number of states in the Trellis                                 */
00331 /* INPUTS - number of inputs to the convolutional coder                     */
00332 /* BRANCHES - number of branches from each state in trellis = INPUTS        */
00333 /* OUTPUTS - number of outputs (symbols) generated by coder                 */
00334 /* TL      - Truncation Length of VA                                        */
00335 /* LARGENUMBER - A value >> metrics, used to approximate infinity           */
00336 /*                                                                          */
00337 /* Global Variables:                                                        */
00338 /* dsignal[OUTPUTS][RCPCCDIM] - codesymbols correponsing to rcpcc outputs   */
00339 /* prevState[STATES][BRANCHES] - reverse transitions describing trellis     */
00340 /* prevOutput[STATES][BRANCHES] - outputs corresponding to transitions      */
00341 /****************************************************************************/
00342 
00343   double VAmetric[TL][STATES];    /* accumulated state metric             */
00344   int VAstate[TL][STATES];        /* best previous state path             */
00345   double branchMetric[OUTPUTS];   /* branch metric based on branch output */
00346 
00347   int bin;    /* index for circular array used to store VA data */
00348   int state;  /* index for VA calculations one state at a time  */
00349 
00350   int i, j;      /* index for each step in the VA, = # info bit in packet */
00351   int d;      /* index for codevector dimension */
00352   int output; /* index for possible symbols generated by code */
00353   int branch; /* index for number of branches from each state in trellis */
00354 
00355   int trace;  /* index for traceback in VA */
00356 
00357   double metric;    /* temporary register for storing state metric */
00358   double minMetric; /*temporary register for storing minimum state metric */
00359   int minState;     /* temporary register for storing minimum state index */
00360 
00361   printf("rcpcc_decoder - rateType %d packetLength %d\n",rateType, packetLength);
00362 
00363 
00364   /* Initialize Viterbi Decoder */
00365   for(bin=0;bin<TL;bin++) {
00366     for(state=0;state<STATES;state++) {
00367       if (state==0)
00368         VAmetric[bin][state] = 0;
00369       else
00370         VAmetric[bin][state] = LARGENUMBER;
00371       VAstate[bin][state] = 0;
00372       } /* for */
00373   } /* for */
00374 
00375   /* Process Samples */
00376   for(i=0;i<packetLength;i++) {
00377 
00378     /* Compute Path Metrics */
00379     /* distance() function includes puncturing */
00380     for (output=0;output<OUTPUTS;output++) {
00381       branchMetric[output] = distance(rcx[i],
00382                                       dsignal[output],
00383                                       ppx[i%puncturePeriod]);
00384       } /* for */
00385 
00386 
00387     /* ACS */
00388     /* Results stored in circular array of size TL                      */
00389     /* TERMINATEPACKET flag enables tail bit forcing pruning of trellis */
00390     bin = i%TL; /* array index */ 
00391 
00392     for (state=0;state<STATES;state++) {
00393       for (branch=0;branch<BRANCHES;branch++) {
00394         metric = VAmetric[(bin-1+TL)%TL][prevState[state][branch]] +
00395                  branchMetric[prevOutput[state][branch]];
00396         if(metric<VAmetric[bin][state] || (branch==0)) {
00397             VAmetric[bin][state] = metric;
00398             VAstate[bin][state] = prevState[state][branch];
00399           } /* if */      
00400         } /* for */
00401       } /* for */
00402  
00403     /* Trellis pruning to terminate packet */
00404     /* Set metric of invalid states to infinity */
00405     if((i+TAILBITS>=packetLength) && TERMINATEPACKET)
00406       for (state=0;state<STATES;state++) 
00407         if (state % (2<<(TAILBITS+i-packetLength)) != 0)
00408           VAmetric[bin][state] = VAmetric[bin][state] + LARGENUMBER;
00409 
00410     /* find minimum state */
00411     minState = 0;
00412     minMetric = VAmetric[bin%TL][0];
00413     for(state=1;state<STATES;state++) {
00414       if (VAmetric[bin%TL][state] < minMetric) {
00415         minState = state;
00416         minMetric = VAmetric[bin%TL][state];
00417         } /* if */
00418       } /* for */
00419 
00420  
00421     /* Trace back and truncate VA */
00422     /* Preliminary best path is stored in ix  */
00423     /* Next sample overwrites best path       */
00424     /* Last sample writes final best path     */
00425 
00426 
00427     if ( (i>=TL) || (i==(packetLength-1)) ) {
00428 
00429       for(trace=0;((trace<i)&&(trace<TL));trace++) {
00430         rix[i-trace] = minState % 2;
00431         
00432         minState = VAstate[(bin-trace+TL)%TL][minState];
00433 
00434       } /* for */
00435       rix[i-trace] = minState % 2;
00436 
00437     } /* if */
00438     
00439   } /* for i */
00440 
00441 } /************************* rcpcc_decoder() *******************************/ 
00442 
00443 double distance(rcx,dsignal,px)
00444      double *rcx;     /* received codevector */
00445      double *dsignal;  /* codesymbols */
00446      int *px;         /* puncture pattern */
00447 {
00448   /**********************************************************************/
00449   /* This function computes the branch metric based on the distance     */
00450   /* between the received codevector and the codesymbols.  It takes     */
00451   /* into account that a punctured symbol may have been received.       */
00452   /**********************************************************************/
00453   double error;
00454   int i;
00455   error = 0;
00456   for(i=0;i<RCPCCDIM;i++)
00457     error += (rcx[i]-dsignal[i])*(rcx[i]-dsignal[i])*px[i];
00458   return(error);
00459 } /************************* distance() ***************************** */
00460 
00461 
00462 
00463 
00464 
00465 
00466 
00467 
00468 

Generated on Sun Jul 16 16:27:45 2006 by  doxygen 1.3.9.1