git.gag.com Git - debian/gnuradio/blob - gnuradio-core/src/lib/viterbi/viterbi.c

   1 /*
   2  * Copyright 1995 Phil Karn, KA9Q
   3  * Copyright 2008 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   7  * GNU Radio is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 3, or (at your option)
  10  * any later version.
  11  *
  12  * GNU Radio is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GNU Radio; see the file COPYING.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 /*
  24  * Viterbi decoder for K=7 rate=1/2 convolutional code
  25  * Some modifications from original Karn code by Matt Ettus
  26  */
  27
  28 #include "viterbi.h"
  29
  30 /* The two generator polynomials for the NASA Standard K=7 code.
  31  * Since these polynomials are known to be optimal for this constraint
  32  * length there is not much point in changing them. But if you do, you
  33  * will have to regenerate the BUTTERFLY macro calls in viterbi()
  34  */
  35 #define POLYA   0x6d
  36 #define POLYB   0x4f
  37
  38 /* The basic Viterbi decoder operation, called a "butterfly"
  39  * operation because of the way it looks on a trellis diagram. Each
  40  * butterfly involves an Add-Compare-Select (ACS) operation on the two nodes
  41  * where the 0 and 1 paths from the current node merge at the next step of
  42  * the trellis.
  43  *
  44  * The code polynomials are assumed to have 1's on both ends. Given a
  45  * function encode_state() that returns the two symbols for a given
  46  * encoder state in the low two bits, such a code will have the following
  47  * identities for even 'n' < 64:
  48  *
  49  *      encode_state(n) = encode_state(n+65)
  50  *      encode_state(n+1) = encode_state(n+64) = (3 ^ encode_state(n))
  51  *
  52  * Any convolutional code you would actually want to use will have
  53  * these properties, so these assumptions aren't too limiting.
  54  *
  55  * Doing this as a macro lets the compiler evaluate at compile time the
  56  * many expressions that depend on the loop index and encoder state and
  57  * emit them as immediate arguments.
  58  * This makes an enormous difference on register-starved machines such
  59  * as the Intel x86 family where evaluating these expressions at runtime
  60  * would spill over into memory.
  61  */
  62 #define BUTTERFLY(i,sym) { \
  63         int m0,m1;\
  64 \
  65         /* ACS for 0 branch */\
  66         m0 = state[i].metric + mets[sym];       /* 2*i */\
  67         m1 = state[i+32].metric + mets[3^sym];  /* 2*i + 64 */\
  68         if(m0 > m1){\
  69                 next[2*i].metric = m0;\
  70                 next[2*i].path = state[i].path << 1;\
  71         } else {\
  72                 next[2*i].metric = m1;\
  73                 next[2*i].path = (state[i+32].path << 1)|1;\
  74         }\
  75         /* ACS for 1 branch */\
  76         m0 = state[i].metric + mets[3^sym];     /* 2*i + 1 */\
  77         m1 = state[i+32].metric + mets[sym];    /* 2*i + 65 */\
  78         if(m0 > m1){\
  79                 next[2*i+1].metric = m0;\
  80                 next[2*i+1].path = state[i].path << 1;\
  81         } else {\
  82                 next[2*i+1].metric = m1;\
  83                 next[2*i+1].path = (state[i+32].path << 1)|1;\
  84         }\
  85 }
  86
  87 extern unsigned char Partab[];  /* Parity lookup table */
  88
  89 /* Convolutionally encode data into binary symbols */
  90 unsigned char
  91 encode(unsigned char *symbols,
  92        unsigned char *data,
  93        unsigned int nbytes,
  94        unsigned char encstate)
  95 {
  96   int i;
  97
  98   while(nbytes-- != 0){
  99     for(i=7;i>=0;i--){
 100       encstate = (encstate << 1) | ((*data >> i) & 1);
 101       *symbols++ = Partab[encstate & POLYA];
 102       *symbols++ = Partab[encstate & POLYB];
 103     }
 104     data++;
 105   }
 106
 107   return encstate;
 108 }
 109
 110 /* Viterbi decoder */
 111 int
 112 viterbi(unsigned long *metric,  /* Final path metric (returned value) */
 113         unsigned char *data,    /* Decoded output data */
 114         unsigned char *symbols, /* Raw deinterleaved input symbols */
 115         unsigned int nbits,     /* Number of output bits */
 116         int mettab[2][256]      /* Metric table, [sent sym][rx symbol] */
 117         ){
 118   unsigned int bitcnt = 0;
 119   int mets[4];
 120   long bestmetric;
 121   int beststate,i;
 122   struct viterbi_state state0[64],state1[64],*state,*next;
 123
 124   state = state0;
 125   next = state1;
 126
 127   /* Initialize starting metrics to prefer 0 state */
 128   state[0].metric = 0;
 129   for(i=1;i<64;i++)
 130     state[i].metric = -999999;
 131   state[0].path = 0;
 132
 133   for(bitcnt = 0;bitcnt < nbits;bitcnt++){
 134     /* Read input symbol pair and compute all possible branch
 135      * metrics
 136      */
 137     mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
 138     mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
 139     mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
 140     mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
 141     symbols += 2;
 142
 143     /* These macro calls were generated by genbut.c */
 144     BUTTERFLY(0,0);
 145     BUTTERFLY(1,1);
 146     BUTTERFLY(2,3);
 147     BUTTERFLY(3,2);
 148     BUTTERFLY(4,3);
 149     BUTTERFLY(5,2);
 150     BUTTERFLY(6,0);
 151     BUTTERFLY(7,1);
 152     BUTTERFLY(8,0);
 153     BUTTERFLY(9,1);
 154     BUTTERFLY(10,3);
 155     BUTTERFLY(11,2);
 156     BUTTERFLY(12,3);
 157     BUTTERFLY(13,2);
 158     BUTTERFLY(14,0);
 159     BUTTERFLY(15,1);
 160     BUTTERFLY(16,2);
 161     BUTTERFLY(17,3);
 162     BUTTERFLY(18,1);
 163     BUTTERFLY(19,0);
 164     BUTTERFLY(20,1);
 165     BUTTERFLY(21,0);
 166     BUTTERFLY(22,2);
 167     BUTTERFLY(23,3);
 168     BUTTERFLY(24,2);
 169     BUTTERFLY(25,3);
 170     BUTTERFLY(26,1);
 171     BUTTERFLY(27,0);
 172     BUTTERFLY(28,1);
 173     BUTTERFLY(29,0);
 174     BUTTERFLY(30,2);
 175     BUTTERFLY(31,3);
 176
 177     /* Swap current and next states */
 178     if(bitcnt & 1){
 179       state = state0;
 180       next = state1;
 181     } else {
 182       state = state1;
 183       next = state0;
 184     }
 185     // ETTUS
 186     //if(bitcnt > nbits-7){
 187     /* In tail, poison non-zero nodes */
 188     //for(i=1;i<64;i += 2)
 189     //  state[i].metric = -9999999;
 190     //}
 191     /* Produce output every 8 bits once path memory is full */
 192     if((bitcnt % 8) == 5 && bitcnt > 32){
 193       /* Find current best path */
 194       bestmetric = state[0].metric;
 195       beststate = 0;
 196       for(i=1;i<64;i++){
 197         if(state[i].metric > bestmetric){
 198           bestmetric = state[i].metric;
 199           beststate = i;
 200         }
 201       }
 202 #ifdef  notdef
 203       printf("metrics[%d] = %d state = %lx\n",beststate,
 204              state[beststate].metric,state[beststate].path);
 205 #endif
 206       *data++ = state[beststate].path >> 24;
 207     }
 208
 209   }
 210   /* Output remaining bits from 0 state */
 211   // ETTUS  Find best state instead
 212   bestmetric = state[0].metric;
 213   beststate = 0;
 214   for(i=1;i<64;i++){
 215     if(state[i].metric > bestmetric){
 216       bestmetric = state[i].metric;
 217       beststate = i;
 218     }
 219   }
 220   if((i = bitcnt % 8) != 6)
 221     state[beststate].path <<= 6-i;
 222
 223   *data++ = state[beststate].path >> 24;
 224   *data++ = state[beststate].path >> 16;
 225   *data++ = state[beststate].path >> 8;
 226   *data = state[beststate].path;
 227   //printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric);
 228   *metric = state[beststate].metric;
 229   return 0;
 230 }
 231
 232
 233 void
 234 viterbi_chunks_init(struct viterbi_state* state) {
 235   // Initialize starting metrics to prefer 0 state
 236   int i;
 237   state[0].metric = 0;
 238   state[0].path = 0;
 239   for(i=1;i<64;i++)
 240     state[i].metric = -999999;
 241 }
 242
 243 void
 244 viterbi_butterfly8(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1)
 245 {
 246   unsigned int bitcnt;
 247   int mets[4];
 248
 249   struct viterbi_state *state, *next;
 250   state = state0;
 251   next = state1;
 252   // Operate on 16 symbols (8 bits) at a time
 253   for(bitcnt = 0;bitcnt < 8;bitcnt++){
 254     // Read input symbol pair and compute all possible branch metrics
 255     mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
 256     mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
 257     mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
 258     mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
 259     symbols += 2;
 260
 261     // These macro calls were generated by genbut.c
 262     BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
 263     BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
 264     BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
 265     BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
 266     BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
 267     BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
 268     BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
 269     BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
 270
 271     // Swap current and next states
 272     if(bitcnt & 1){
 273       state = state0;
 274       next = state1;
 275     } else {
 276       state = state1;
 277       next = state0;
 278     }
 279   }
 280 }
 281
 282 void
 283 viterbi_butterfly2(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1)
 284 {
 285   //unsigned int bitcnt;
 286   int mets[4];
 287
 288   struct viterbi_state *state, *next;
 289   state = state0;
 290   next = state1;
 291   // Operate on 4 symbols (2 bits) at a time
 292
 293   // Read input symbol pair and compute all possible branch metrics
 294   mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
 295   mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
 296   mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
 297   mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
 298
 299   // These macro calls were generated by genbut.c
 300   BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
 301   BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
 302   BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
 303   BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
 304   BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
 305   BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
 306   BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
 307   BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
 308
 309   state = state1;
 310   next = state0;
 311
 312   // Read input symbol pair and compute all possible branch metrics
 313   mets[0] = mettab[0][symbols[2]] + mettab[0][symbols[3]];
 314   mets[1] = mettab[0][symbols[2]] + mettab[1][symbols[3]];
 315   mets[2] = mettab[1][symbols[2]] + mettab[0][symbols[3]];
 316   mets[3] = mettab[1][symbols[2]] + mettab[1][symbols[3]];
 317
 318   // These macro calls were generated by genbut.c
 319   BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2);
 320   BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1);
 321   BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2);
 322   BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1);
 323   BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0);
 324   BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3);
 325   BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0);
 326   BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3);
 327 }
 328
 329 unsigned char
 330 viterbi_get_output(struct viterbi_state *state, unsigned char *outbuf) {
 331   // Produce output every 8 bits once path memory is full
 332   //  if((bitcnt % 8) == 5 && bitcnt > 32) {
 333
 334   //  Find current best path
 335   unsigned int i,beststate;
 336   int bestmetric;
 337
 338   bestmetric = state[0].metric;
 339   beststate = 0;
 340   for(i=1;i<64;i++)
 341     if(state[i].metric > bestmetric) {
 342       bestmetric = state[i].metric;
 343       beststate = i;
 344     }
 345   *outbuf =  state[beststate].path >> 24;
 346   return bestmetric;
 347 }
 348
 349
 350 //printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric);
 351 // In tail, poison non-zero nodes
 352 //if(bits_out > packet_size-7)
 353 //  for(i=1;i<64;i += 2)
 354 //    state[i].metric = -9999999;
 355