/* 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 */intviterbi37(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;}