viterbi27.c

通信类程序

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

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

int Rate = 2;

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

/* Convolutionally encode data into binary symbols */
int
encode27(
unsigned char *symbols,
unsigned char *data,
unsigned int nbytes,
unsigned int startstate,
unsigned int endstate)
{
  int i;
  int 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];
    }
    data++;
  }
  /* Flush out tail */
  for(i=5;i>=0;i--){
    encstate = (encstate << 1) | ((endstate >> i) & 1);
    *symbols++ = Partab[encstate & POLYA];
    *symbols++ = Partab[encstate & POLYB];
  }
  return 0;
}

/* Viterbi decoder */
int
viterbi27(
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; 2*(nbits+6) input symbols will be read */
int mettab[2][256],	/* Metric table, [sent sym][rx symbol] */
unsigned int startstate,         /* Encoder starting state */
unsigned int endstate            /* Encoder ending state */
){
  int bitcnt = -6; /* K-1 */
  int i,mets[4];
  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 pair and compute branch metrics */
    mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]];
    mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
    mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
    mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
    symbols += 2;

    /* These macro calls were generated by genbut.c
     * and rearranged by hand for speed
     */
    dec = 0;
    BUTTERFLY(0,0);
    BUTTERFLY(6,0);
    BUTTERFLY(8,0);
    BUTTERFLY(14,0);
    BUTTERFLY(2,3);
    BUTTERFLY(4,3);
    BUTTERFLY(10,3);
    BUTTERFLY(12,3);
    BUTTERFLY(1,1);
    BUTTERFLY(7,1);
    BUTTERFLY(9,1);
    BUTTERFLY(15,1);
    BUTTERFLY(3,2);
    BUTTERFLY(5,2);
    BUTTERFLY(11,2);
    BUTTERFLY(13,2);
    *pp++ = dec;
    dec = 0;
    BUTTERFLY(19,0);
    BUTTERFLY(21,0);
    BUTTERFLY(27,0);
    BUTTERFLY(29,0);
    BUTTERFLY(17,3);
    BUTTERFLY(23,3);
    BUTTERFLY(25,3);
    BUTTERFLY(31,3);
    BUTTERFLY(18,1);
    BUTTERFLY(20,1);
    BUTTERFLY(26,1);
    BUTTERFLY(28,1);
    BUTTERFLY(16,2);
    BUTTERFLY(22,2);
    BUTTERFLY(24,2);
    BUTTERFLY(30,2);
    *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]];
    mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]];
    mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]];
    mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]];
    symbols += 2;
    
    /* These macro calls were generated by genbut.c
     * and rearranged by hand for speed
     */
    dec = 0;
    BUTTERFLY2(0,0);
    BUTTERFLY2(6,0);
    BUTTERFLY2(8,0);
    BUTTERFLY2(14,0);
    BUTTERFLY2(2,3);
    BUTTERFLY2(4,3);
    BUTTERFLY2(10,3);
    BUTTERFLY2(12,3);
    BUTTERFLY2(1,1);
    BUTTERFLY2(7,1);
    BUTTERFLY2(9,1);
    BUTTERFLY2(15,1);
    BUTTERFLY2(3,2);
    BUTTERFLY2(5,2);
    BUTTERFLY2(11,2);
    BUTTERFLY2(13,2);
    *pp++ = dec;
    dec = 0;
    BUTTERFLY2(19,0);
    BUTTERFLY2(21,0);
    BUTTERFLY2(27,0);
    BUTTERFLY2(29,0);
    BUTTERFLY2(17,3);
    BUTTERFLY2(23,3);
    BUTTERFLY2(25,3);
    BUTTERFLY2(31,3);
    BUTTERFLY2(18,1);
    BUTTERFLY2(20,1);
    BUTTERFLY2(26,1);
    BUTTERFLY2(28,1);
    BUTTERFLY2(16,2);
    BUTTERFLY2(22,2);
    BUTTERFLY2(24,2);
    BUTTERFLY2(30,2);
    *pp++ = dec;
    
    if(++bitcnt == nbits){
      *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;
}