VITERBI.cpp

/* Viterbi decoder for arbitrary convolutional code
 * viterbi27 and viterbi37 for the r=1/2 and r=1/3 K=7 codes are faster
 * Copyright 1999 Phil Karn, KA9Q
 * May be used under the terms of the GNU Public License
 */

#include "viterbi.h"

//@@@
#define NDECODERS 5

/* 8-bit parity lookup table, generated by partab.c */
unsigned char Partab[] = {
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
 0, 1, 1, 0, 1, 0, 0, 1,
 0, 1, 1, 0, 1, 0, 0, 1,
 1, 0, 0, 1, 0, 1, 1, 0,
};

inline int parity(int x)
{
  x ^= (x >> 16);
  x ^= (x >> 8);
  return Partab[x & 0xff];
}

void __fastcall Viterbi::SetParm(int n, int k)
{
   N = n;
   K = k;

   if(K>=6) D =	(1 << (K-6));
   else D = 1;

   if(N==2)
   {
       //if(K==5)  {Polys[0]=0x17;   Polys[1]=0x19;  }    /* k=5 */
       if(K==5)  {Polys[0]=0x1f;   Polys[1]=0x1d;  }    /* k=5 (G3PLX QPSK31) */
       if(K==7)  {Polys[0]=0x6d;   Polys[1]=0x4f;  }    /* k=7; very popular with NASA and industry  */
       if(K==9)  {Polys[0]=0x1af;  Polys[1]=0x11d; }    /* k=9; used in IS-95 CDMA  */
       if(K==15) {Polys[0]=042631; Polys[1]=047245;}    /* k=15 on Mars Pathfinder */
   }
   else if(N==3)
   {
       if(K==5)  {Polys[0]=0x1f;   Polys[1]=0x1b;  Polys[2]=0x15;   } /* k = 5 */
       if(K==7)  {Polys[0]=0x4f;   Polys[1]=0x57;  Polys[2]=0x6d;   } /* k = 7; also popular with NASA and industry  */
       if(K==9)  {Polys[0]=0x1ed;  Polys[1]=0x19b; Polys[2]=0x127;  } /* k = 9; used in IS-95 CDMA  */
       if(K==15) {Polys[0]=042631; Polys[1]=047245;Polys[2]=073363; } /* k=15 on Mars Pathfinder */
   }
   else if(N==6)
   {
       // currently are dummy polinomials!
       if(K==5)  {Polys[0]=0x1f;   Polys[1]=0x1b;  Polys[2]=0x15;  Polys[3]=0x1f;    Polys[4]=0x1b;  Polys[5]=0x15;  }
       if(K==7)  {Polys[0]=0x4f;   Polys[1]=0x57;  Polys[2]=0x6d;  Polys[3]=0x4f;    Polys[4]=0x57;  Polys[5]=0x6d;  }
       if(K==9)  {Polys[0]=0x1ed;  Polys[1]=0x19b; Polys[2]=0x127; Polys[3]=0x1ed;   Polys[4]=0x19b; Polys[5]=0x127; }
       if(K==15) {Polys[0]=042631; Polys[1]=047245;Polys[2]=073363; Polys[3]=056507; Polys[4]=077267; Polys[5]=064537; } /* k=15 on Mars Pathfinder */
   }

  int i,j,sym;

  /* build symbol table */
  for(i=0;i<(1<<K);i++)
  {
     sym = 0;
     for(j=0;j<N;j++)
     {
       sym = (sym << 1) + parity(i & Polys[j]);
     }
     Syms[i] = sym;
  }

  // calculate metric table likelyhood (255=max likelyood, 0=no likelyhood)
  for(i=0;i<256;i++)
  {
     mettab[0][i] = 128 - i;
     mettab[1][255-i] = 127 - i;
  }

  // reset decoder counter
  input_table_counter=0;
  for(i=0;i<128;i++) dummy_table[i]=128;

  InitDecoder();
  ready = false;
  PathSize = NDECODERS;
}

void __fastcall Viterbi::SetPathSize(int ps)
{
   PathSize = ps;
}

/* Convolutionally encode data into binary symbols */
AnsiString __fastcall Viterbi::encode(AnsiString data)
{
  int i,j,bit;
  unsigned int symbol;
  int nbits = data.Length();
  AnsiString Symbols;

  for(i=0;i<nbits;i++)
  {
     bit = (data[i+1]=='1');
     encstate = (encstate << 1) | bit;
     for(j=0;j<N;j++)
     {
        symbol = parity(encstate & Polys[j]);
        Symbols += (symbol==1 ? "1" : "0" );
     }
  }
  return Symbols;
}

void __fastcall Viterbi::InitDecoder()
{
  // clear metric table and path table
  memset(cmetric,0,(1<<(K-1))*sizeof(unsigned int));
  memset(paths,0,xpath_array_size*sizeof(unsigned int));

  // starting path
  pp = paths;

  // no bits
  bitcount=0;
}

/* Viterbi decoder */
/* symbols=Raw deinterleaved input symbols */
/* nbits=number of output bits */
void __fastcall Viterbi::decode(unsigned char *symbols)
{
  int m0,m1;
  int i,j;
  unsigned int mask;

  bitcount++;

  /* Read input symbols and compute branch metrics */
  for(i=0;i<(1<<N);i++)
  {
    mets[i] = 0;
    for(j=0;j<N;j++)
    {
      mets[i] += mettab[(i >> (N-j-1)) & 1][symbols[j]];
    }
  }

  /* Run the add-compare-select operations */
  mask = 1;
  for(i=0;i< (1 << (K-1));i+=2)
  {
    int b1,b2;

    b1 = mets[Syms[i]];
    nmetric[i] = m0 = cmetric[i/2] + b1;
    b2 = mets[Syms[i+1]];
    b1 -= b2;
    m1 = cmetric[(i/2) + (1<<(K-2))] + b2;
    if(m1 > m0)
    {
      nmetric[i] = m1;
      *pp |= mask;
    }
    m0 -= b1;
    nmetric[i+1] = m0;
    m1 += b1;
    if(m1 > m0)
    {
      nmetric[i+1] = m1;
      *pp |= mask << 1;
    }
    mask <<= 2;
    if(mask == 0)
    {
      mask = 1;
      pp++;
    }
  }
  if(mask != 1)
  {
    pp++;
  }
  memcpy(cmetric,nmetric,cmetric_array_size*sizeof(int));
}

void __fastcall Viterbi::RebuildPath(int nbits)
{
  // chain back recostruct path
  metric = nmetric[0]; // metric[endstate] return value into parameter
  decoded_data[nbits]=0;
  static int endstate;

  for(int i=nbits-1;i>=0;i--)
  {
    pp -= D;
    if(pp[endstate >> 5] & (1 << (endstate & 31)))
    {
      endstate |= (1 << (K-1));
      decoded_data[i] = '1';
    }
    else
    {
      decoded_data[i] = '0';
    }
    endstate >>= 1;
  }
}

void __fastcall Viterbi::SymbolDecode(unsigned char symbol)
{
    // collect N symbols
    input_table[input_table_counter] = symbol;
    input_table_counter++;
    if(input_table_counter != N) return;

    decode(input_table);
    input_table_counter = 0;

    if(bitcount>=(PathSize*K))
    {
       for(int i=0;i<K;i++) decode(dummy_table);
       RebuildPath((PathSize*K)+K);
       //RebuildPath((PathSize*K));

       // write output
       output_nbits = PathSize*K;
       memcpy(output_bits,decoded_data,output_nbits);
       ready = true;
       InitDecoder();
    }
}

/******************************************************************************/

ParallelViterbi::ParallelViterbi()
{
   PathSize = NDECODERS;
   ndecoders = NDECODERS;
}

void __fastcall ParallelViterbi::SetParm(int n, int k)
{
    int t,i;
    for(t=0;t<ndecoders;t++) V[t].SetParm(n,k);
    N=n;
    K=k;

    Slice = PathSize*K / ndecoders;

    for(t=0;t<ndecoders;t++)
    {
       for(i=0;i<(t*Slice);i++)
       {
          for(int j=0;j<N;j++) V[t].SymbolDecode(128);
       }
    }
}

void __fastcall ParallelViterbi::SetPathSize(int ps)
{
/*
    int t,i;
    for(t=0;t<ndecoders;t++) V[t].SetPathSize(ps);
    PathSize = ps;
*/
}

void __fastcall ParallelViterbi::SymbolDecode(unsigned char symbol)
{
    int t;
    for(t=0;t<ndecoders;t++)
    {
       V[t].SymbolDecode(symbol);
    }

    for(t=0;t<ndecoders;t++)
    {
       if(V[t].ready)
       {
           V[t].ready = false;
           output_nbits = Slice;
           memcpy(output_bits,V[t].decoded_data,output_nbits);
           metric = V[t].metric;
           ready = true;
       }
    }
}