viterbi37.c

This package provides encoders and fast Viterbi decoders for the NASA standard rate 1/2 and rate 1/

/* Convolutional encoder and Viterbi decoder for K=7 rate=1/3 code
 * Copyright 1999 Phil Karn, KA9Q
 * May be used under the terms of the GNU Public License
 */

#include <memory.h>
#include "viterbi37.h"
#define NULL ((void *)0)

int Rate = 3;

extern unsigned char Partab[];	/* Parity lookup table */

/* Convolutionally encode data into binary symbols */
encode37(
unsigned char *symbols,
unsigned char *data,
unsigned int nbytes,
unsigned int startstate,
unsigned int endstate)
{
  int i;
  unsigned char encstate = startstate;

  while(nbytes-- != 0){
    for(i=7;i>=0;i--){
      encstate = (encstate << 1) | ((*data >> i) & 1);
      *symbols++ = Partab[encstate & POLYA];
      *symbols++ = Partab[encstate & POLYB];
      *symbols++ = Partab[encstate & POLYC];
    }
    data++;
  }
  /* Flush out tail */
  for(i=5;i>=0;i--){
    encstate = (encstate << 1) | ((endstate >> i) & 1);
    *symbols++ = Partab[encstate & POLYA];
    *symbols++ = Partab[encstate & POLYB];
    *symbols++ = Partab[encstate & POLYC];
  }
  return 0;
}

/* Viterbi decoder for rate 1/3, k=7 code */
int
viterbi37(
unsigned long *metric,	/* Final path metric (returned value) */
unsigned char *data,	/* Decoded output data */
unsigned char *symbols,	/* Raw deinterleaved input symbols */
unsigned int nbits,	/* Number of output bits */
int mettab[2][256],	/* Metric table, [sent sym][rx symbol] */
int startstate,         /* Encoder starting state */
int endstate            /* Encoder ending state */
){
  int bitcnt = -6; /* K-1 */
  int i,mets[8];
  unsigned long dec,paths[(nbits+6)*2],*pp;
  long cmetric[64],nmetric[64];
	
  startstate &= 63;
  endstate &= 63;

  /* Initialize starting metrics */
  for(i=0;i<64;i++)
    cmetric[i] = -999999;
  cmetric[startstate] = 0;
  
  pp = paths;
  for(;;){
    /* Read input symbol triplet and compute branch metrics */
    mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]] + mettab[0][symbols[2]];
    mets[1] = mettab[0][symbols[0]] + mettab[0][symbols[1]] + mettab[1][symbols[2]];
    mets[3] = mettab[0][symbols[0]] + mettab[1][symbols[1]] + mettab[1][symbols[2]];
    mets[2] = mettab[0][symbols[0]] + mettab[1][symbols[1]] + mettab[0][symbols[2]];
    mets[6] = mettab[1][symbols[0]] + mettab[1][symbols[1]] + mettab[0][symbols[2]];
    mets[7] = mettab[1][symbols[0]] + mettab[1][symbols[1]] + mettab[1][symbols[2]];
    mets[5] = mettab[1][symbols[0]] + mettab[0][symbols[1]] + mettab[1][symbols[2]];
    mets[4] = mettab[1][symbols[0]] + mettab[0][symbols[1]] + mettab[0][symbols[2]];
    symbols += 3;
    
    /* These macro calls were generated by genbut.c
     * and rearranged by hand for speed
     */
    dec = 0;
    BUTTERFLY(0,0);
    BUTTERFLY(14,0);
    BUTTERFLY(2,7);
    BUTTERFLY(12,7);
    BUTTERFLY(1,6);
    BUTTERFLY(15,6);
    BUTTERFLY(3,1);
    BUTTERFLY(13,1);
    BUTTERFLY(4,5);
    BUTTERFLY(10,5);
    BUTTERFLY(6,2);
    BUTTERFLY(8,2);
    BUTTERFLY(5,3);
    BUTTERFLY(11,3);
    BUTTERFLY(7,4);
    BUTTERFLY(9,4);
    *pp++ = dec;
    dec = 0;
    
    BUTTERFLY(19,0);
    BUTTERFLY(29,0);
    BUTTERFLY(17,7);
    BUTTERFLY(31,7);
    BUTTERFLY(18,6);
    BUTTERFLY(28,6);
    BUTTERFLY(16,1);
    BUTTERFLY(30,1);
    BUTTERFLY(23,5);
    BUTTERFLY(25,5);
    BUTTERFLY(21,2);
    BUTTERFLY(27,2);
    BUTTERFLY(22,3);
    BUTTERFLY(24,3);
    BUTTERFLY(20,4);
    BUTTERFLY(26,4);
    *pp++ = dec;
    
    if(++bitcnt == nbits){
      *metric = nmetric[endstate];
      break;
    }
    
    /* Read input symbol pair and compute branch metrics */
    mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]] + mettab[0][symbols[2]];
    mets[1] = mettab[0][symbols[0]] + mettab[0][symbols[1]] + mettab[1][symbols[2]];
    mets[3] = mettab[0][symbols[0]] + mettab[1][symbols[1]] + mettab[1][symbols[2]];
    mets[2] = mettab[0][symbols[0]] + mettab[1][symbols[1]] + mettab[0][symbols[2]];
    mets[6] = mettab[1][symbols[0]] + mettab[1][symbols[1]] + mettab[0][symbols[2]];
    mets[7] = mettab[1][symbols[0]] + mettab[1][symbols[1]] + mettab[1][symbols[2]];
    mets[5] = mettab[1][symbols[0]] + mettab[0][symbols[1]] + mettab[1][symbols[2]];
    mets[4] = mettab[1][symbols[0]] + mettab[0][symbols[1]] + mettab[0][symbols[2]];
    symbols += 3;
    
    /* These macro calls were generated by genbut.c
     * and rearranged by hand for speed
     */
    dec = 0;
    BUTTERFLY2(0,0);
    BUTTERFLY2(14,0);
    BUTTERFLY2(2,7);
    BUTTERFLY2(12,7);
    BUTTERFLY2(1,6);
    BUTTERFLY2(15,6);
    BUTTERFLY2(3,1);
    BUTTERFLY2(13,1);
    BUTTERFLY2(4,5);
    BUTTERFLY2(10,5);
    BUTTERFLY2(6,2);
    BUTTERFLY2(8,2);
    BUTTERFLY2(5,3);
    BUTTERFLY2(11,3);
    BUTTERFLY2(7,4);
    BUTTERFLY2(9,4);
    *pp++ = dec;
    dec = 0;
    
    BUTTERFLY2(19,0);
    BUTTERFLY2(29,0);
    BUTTERFLY2(17,7);
    BUTTERFLY2(31,7);
    BUTTERFLY2(18,6);
    BUTTERFLY2(28,6);
    BUTTERFLY2(16,1);
    BUTTERFLY2(30,1);
    BUTTERFLY2(23,5);
    BUTTERFLY2(25,5);
    BUTTERFLY2(21,2);
    BUTTERFLY2(27,2);
    BUTTERFLY2(22,3);
    BUTTERFLY2(24,3);
    BUTTERFLY2(20,4);
    BUTTERFLY2(26,4);
    *pp++ = dec;
    
    if(++bitcnt == nbits){
      /* Or state with best metric, if no tail */
      *metric = cmetric[endstate];
      break;
    }
  }
  /* Chain back from terminal state to produce decoded data */
  if(data == NULL)
    return 0;/* Discard output */
  memset(data,0,(nbits+7)/8); /* round up in case nbits % 8 != 0 */
  for(i=nbits-1;i >= 0;i--){
    pp -= 2;
    if(pp[endstate >> 5] & (1 << (endstate & 31))){
      endstate |= 64;	/* 2^(K-1) */
      data[i>>3] |= 0x80 >> (i&7);
    }
    endstate >>= 1;
  }
  return 0;
}