14e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* K=15 r=1/6 Viterbi decoder in portable C 24e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Copyright Mar 2004, Phil Karn, KA9Q 34e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * May be used under the terms of the GNU Lesser General Public License (LGPL) 44e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 54e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <stdio.h> 64e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <stdlib.h> 74e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <memory.h> 84e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <limits.h> 94e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include "fec.h" 104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yitypedef union { unsigned long w[512]; unsigned char c[2048];} decision_t; 124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yitypedef union { unsigned long w[16384]; } metric_t; 134e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yistatic union branchtab615 { unsigned long w[8192]; } Branchtab615[6] __attribute__ ((aligned(16))); 154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yistatic int Init = 0; 164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* State info for instance of Viterbi decoder */ 184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yistruct v615 { 194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi metric_t metrics1; /* path metric buffer 1 */ 204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi metric_t metrics2; /* path metric buffer 2 */ 214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision_t *dp; /* Pointer to current decision */ 224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision_t *decisions; /* Beginning of decisions for block */ 244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi}; 254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Create a new instance of a Viterbi decoder */ 274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yivoid *create_viterbi615_port(int len){ 284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct v615 *vp; 294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(!Init){ 314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int polys[6] = { V615POLYA,V615POLYB,V615POLYC,V615POLYD,V615POLYE,V615POLYF }; 324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi set_viterbi615_polynomial_port(polys); 334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if((vp = (struct v615 *)malloc(sizeof(struct v615))) == NULL) 354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return NULL; 364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if((vp->decisions = malloc((len+14)*sizeof(decision_t))) == NULL){ 374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(vp); 384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return NULL; 394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi init_viterbi615(vp,0); 414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return vp; 424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yivoid set_viterbi615_polynomial_port(int polys[6]){ 454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int state; 464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int i; 474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(state=0;state < 8192;state++){ 494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<6;i++) 504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi Branchtab615[i].w[state] = (polys[i] < 0) ^ parity((2*state) & abs(polys[i])) ? 255 : 0; 514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi Init++; 534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Initialize Viterbi decoder for start of new frame */ 564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yiint init_viterbi615_port(void *p,int starting_state){ 574e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct v615 *vp = p; 584e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int i; 594e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 604e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(p == NULL) 614e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return -1; 624e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<16384;i++) 634e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->metrics1.w[i] = 1000; 644e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 654e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->old_metrics = &vp->metrics1; 664e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->new_metrics = &vp->metrics2; 674e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->dp = vp->decisions; 684e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->old_metrics->w[starting_state & 16383] = 0; /* Bias known start state */ 694e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return 0; 704e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 714e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 724e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Viterbi chainback */ 734e213d510f437769f8a28578dd4f786fb7d16c4Bill Yiint chainback_viterbi615_port( 744e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi void *p, 754e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi unsigned char *data, /* Decoded output data */ 764e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi unsigned int nbits, /* Number of data bits */ 774e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi unsigned int endstate){ /* Terminal encoder state */ 784e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct v615 *vp = p; 794e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision_t *d; 804e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 814e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(p == NULL) 824e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return -1; 834e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi d = (decision_t *)vp->decisions; 844e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi endstate %= 16384; 854e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 864e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* The store into data[] only needs to be done every 8 bits. 874e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * But this avoids a conditional branch, and the writes will 884e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * combine in the cache anyway 894e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 904e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi d += 14; /* Look past tail */ 914e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi while(nbits-- != 0){ 924e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int k; 934e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 944e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi k = (d[nbits].c[endstate/8] >> (endstate%8)) & 1; 954e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi endstate = (k << 13) | (endstate >> 1); 964e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data[nbits>>3] = endstate >> 6; 974e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 984e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return 0; 994e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 1004e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1014e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Delete instance of a Viterbi decoder */ 1024e213d510f437769f8a28578dd4f786fb7d16c4Bill Yivoid delete_viterbi615_port(void *p){ 1034e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct v615 *vp = p; 1044e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1054e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(vp != NULL){ 1064e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(vp->decisions); 1074e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(vp); 1084e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1094e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 1104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* C-language butterfly */ 1124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#define BFLY(i) {\ 1134e213d510f437769f8a28578dd4f786fb7d16c4Bill Yiunsigned long metric,m0,m1,m2,m3,decision0,decision1;\ 1144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi metric = ((Branchtab615[0].w[i] ^ syms[0]) + (Branchtab615[1].w[i] ^ syms[1])\ 1154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi +(Branchtab615[2].w[i] ^ syms[2]) + (Branchtab615[3].w[i] ^ syms[3])\ 1164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi +(Branchtab615[4].w[i] ^ syms[4]) + (Branchtab615[5].w[i] ^ syms[5]));\ 1174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi m0 = vp->old_metrics->w[i] + metric;\ 1184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi m1 = vp->old_metrics->w[i+8192] + (1530 - metric);\ 1194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi m2 = vp->old_metrics->w[i] + (1530-metric);\ 1204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi m3 = vp->old_metrics->w[i+8192] + metric;\ 1214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision0 = (signed long)(m0-m1) >= 0;\ 1224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision1 = (signed long)(m2-m3) >= 0;\ 1234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->new_metrics->w[2*i] = decision0 ? m1 : m0;\ 1244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->new_metrics->w[2*i+1] = decision1 ? m3 : m2;\ 1254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi d->c[i/4] |= ((decision0|(decision1<<1)) << ((2*i)&7));\ 1264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 1274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Update decoder with a block of demodulated symbols 1284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Note that nbits is the number of decoded data bits, not the number 1294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * of symbols! 1304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 1314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yiint update_viterbi615_blk_port(void *p,unsigned char *syms,int nbits){ 1334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct v615 *vp = p; 1344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi void *tmp; 1354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi decision_t *d; 1364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int i; 1374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(p == NULL) 1394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return -1; 1404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi d = (decision_t *)vp->dp; 1414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi while(nbits--){ 1424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memset(d,0,sizeof(decision_t)); 1434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<8192;i++) 1444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi BFLY(i); 1454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi syms += 6; 1474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi d++; 1484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Swap pointers to old and new metrics */ 1494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi tmp = vp->old_metrics; 1504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->old_metrics = vp->new_metrics; 1514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->new_metrics = tmp; 1524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi vp->dp = d; 1544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return 0; 1554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 1564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 157