2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Витерби декодер....
Сообщение19.04.2012, 10:53 
Аватара пользователя
Всем привет!

На днях нашёл на китайском сайте вроде как декодер Витерби, однако работает он как-то странно. Слишком уж много конфигурационных параметров он требует.

Вот код:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
// Description: Viterbi decoder, hard decision decoding. For a
//              rate-1/n convolutional code. Hamming metric.
//
// Maximum of 1024 states; max. truncation length = 1024
//
 
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <time.h>

#define MAX_RANDOM LONG_MAX

// Use the compiling directive -DSHOW_PROGRESS to see how the decoder
// converges to the decoded sequence by monitoring the survivor memory
#ifdef SHOW_PROGRESS
#define DELTA 1
#endif

int k2=1, n2, m2;
int NUM_STATES, OUT_SYM, NUM_TRANS;
long TRUNC_LENGTH;

double RATE;
double INIT_SNR, FINAL_SNR, SNR_INC;
long NUMSIM;

FILE *fp, *fp_ber;

int g2[10][10];
unsigned int memory2, output;            /* Memory and output */
unsigned int data2;                      /* Data */

unsigned long seed;                      /* Seed for random generator */
unsigned int data_symbol[1024];          /* 1-bit data sequence */
long index;                              /* Index for memory management*/
double transmitted[10];                  /* Transmitted signals/branch */
double snr, amp;
double received[10];                     /* Received signals/branch */

int fflush();

// Data structures used for trellis sections and survivors
struct trel {
  int init;                /* initial state */
  int data;                /* data symbol */
  int final;               /* final state */
  double output[10];  /* output coded symbols (branch label) */
};
struct surv {
  double metric;           /* metric */
  int data[1024];  /* estimated data symbols */
  int state[1024];  /* state sequence */
};

// A trellis section is an array of branches, indexed by an initial
//   state and a k_2-bit input data. The values read
//   are the final state and the output symbols
struct trel trellis[1024][100];

/* A survivor is a sequence of states and estimated data, of length
   equal to TRUNC_LENGTH, together with its corresponding metric.
   A total of NUM_STATES survivors are needed */

struct surv survivor[1024], surv_temp[1024];

/* Function prototypes */
void encoder2(void);           /* Encoder for C_{O2} */
int random_data(void);         /* Random data generator */
void transmit(void);           /* Encoder & BPSK modulator */
void awgn(void);               /* Add AWGN */
void viterbi(void);            /* Viterbi decoder */
double comp_metric(double rec, double ref); /* Metric calculator */
void open_files(void);         /* Open files for output */
void close_files(void);        /* Close files */


main(int argc, char *argv[])
{

register int i, j, k;
int init, data, final, output;
register int error;
unsigned long error_count;
char name1[40], name2[40];

  // Command line processing
  if (argc != 8)
    {
      printf("Usage %s file_input file_output truncation snr_init snr_final snr_inc num_sim\n", argv[0]);
      exit(0);
    }

  sscanf(argv[1],"%s", name1);
  sscanf(argv[2],"%s", name2);
  sscanf(argv[3],"%ld", &TRUNC_LENGTH);
  sscanf(argv[4],"%lf", &INIT_SNR);
  sscanf(argv[5],"%lf", &FINAL_SNR);
  sscanf(argv[6],"%lf", &SNR_INC);
  sscanf(argv[7],"%ld", &NUMSIM);

printf("\nSimulation of Viterbi decoding over an AWGN channel with hard decisions\n");
printf("%ld simulations per Eb/No (dB) point\n", NUMSIM);


  fp_ber = fopen(name2,"w");

  /* Open file with trellis data */
  if (!(fp = fopen(name1,"r")))
    {
    printf("Error opening file!\n");
    exit(1);
    }

  fscanf(fp, "%d %d", &n2, &m2);
  fprintf(stderr,"SCAN n2=%d m2=%d\n",n2,m2);
  RATE = 1.0 / (double) n2;
  fprintf(stderr,"RATE: %f\n",RATE);

  fscanf(fp, "%d %d %d", &NUM_STATES, &OUT_SYM, &NUM_TRANS);

  for (j=0; j<n2; j++)
    fscanf(fp, "%x", &g2[j][0]);

  printf("\n%d-state rate-1/%d binary convolutional encoder\n",
          NUM_STATES, n2);
  printf("with generator polynomials ");
  for (j=0; j<n2; j++) printf("%x ", g2[j][0]); printf("\n");
  printf("\n\nDecoding depth = %ld\n\n", TRUNC_LENGTH);

  /* =================== READ TRELLIS STRUCTURE ==================== */

  for (j=0; j<NUM_STATES; j++) /* For each state in the section */
    for (k=0; k<NUM_TRANS; k++) /* and for each outgoing branch */
      {
        /* Read initial state, input data and final state */
        fscanf(fp,"%d %d %d", &trellis[j][k].init, &trellis[j][k].data,
        &trellis[j][k].final);
        /* Read the output symbols of the branch */
        for (i=0; i < OUT_SYM; i++)
          {
             fscanf(fp,"%d", &data);
             trellis[j][k].output[i] = (double) data;
          }
      } /* end for states */
      /* end for branches */
 
  fclose(fp);
 
#ifdef PRINT
  for (j=0; j<NUM_STATES; j++)   /* For each state in the section */
    for (k=0; k<NUM_TRANS; k++)  /* and for each outgoing branch */
      {
        printf("%3d %3d %3d  ", trellis[j][k].init,
        trellis[j][k].data, trellis[j][k].final);
        for (i=0; i < OUT_SYM; i++)
          printf("%2.0lf ", trellis[j][k].output[i]);
        printf("\n");
       } /* end for states */
      /* end for branches */
#endif



  snr = INIT_SNR;

  /* ======================== SNR LOOP ============================= */

  while ( snr < (FINAL_SNR+1.0e-6) )
    {
      amp = sqrt( 2.0 * RATE * pow(10.0, (snr/10.0)) );

      /* Random seed from current time */
      time(&seed);
      srandom(seed);
     
      /* Initialize transmitted data sequence */
     
      for (i=0; i<TRUNC_LENGTH; i++)
        data_symbol[i]=0;
     
      /* Initialize survivor sequences and metrics */
     
      for (i=0; i<NUM_STATES; i++)
        {
          survivor[i].metric = 0.0;             /* Metric = 0 */
          for (j=0; j<TRUNC_LENGTH; j++)
            {
              survivor[i].data[j] = 0;        /* Estimated data = 0 */
              survivor[i].state[j] = 0;       /* Estimated state = 0 */
            }
        }
     

      /* Index used in simulation loop */
      index = 0;
     
      /* Initialize encoder memory */
      memory2 = 0;

      /* Error counter */
      error_count = 0;


      /* ===================== SIMULATION LOOP ========================= */
     
      while (index < NUMSIM)
        {
       
          /* GENERATE a random bit */
          data_symbol[index % TRUNC_LENGTH] = random_data(); /* */
         
          /* ENCODE AND MODULATE (BPSK) data bit */
          transmit();
         
          /* ADD ADDITIVE WHITE GAUSSIAN NOISE */
          awgn();

          /* VITERBI DECODE */
          viterbi();
         
          index += 1;           /* Increase simulation index */
         
          /* COMPUTE ERRORS */
          error = survivor[0].data[index % TRUNC_LENGTH]
                                      ^ data_symbol[index % TRUNC_LENGTH];
          if (error)
            error_count++;
         
#ifdef SHOW_PROGRESS
          if ( (index % DELTA) == 0 )
            {
              for (j=0; j<NUM_STATES; j++)
                {
                  printf("%3d %2d   ", (index % TRUNC_LENGTH), j);
                  for (i=0; i<TRUNC_LENGTH; i++)
                    printf("%x", survivor[j].data[i]);
                  printf(" %ld\n", error_count);
                }
            }
#endif
        }
     
      printf("%f  %10.4e\n",snr, ((double) error_count/(double) index) );
     
      fprintf(fp_ber, "%f %10.4e\n", snr, ((double)error_count /(double)index));
             

      fflush(stdout);
      fflush(fp_ber);

      snr += SNR_INC;
     
    }
 
  fclose(fp_ber);
}


int random_data()
{
  /* Random bit generator */
  return( (random() >> 5) & 1 );
}


void transmit()
{
  /* Encode and modulate a 1-bit data sequence */
  int i;

  encoder2(); /* */

  /* Modulate: {0,1} --> {+1,-1} */
  for (i=(OUT_SYM-1); i >=0; i--)
    if ( (output >> i) & 0x01 )
      transmitted[OUT_SYM-1-i] = -1.0;  /* if bit = 1 */
    else
      transmitted[OUT_SYM-1-i] =  1.0;  /* if bit = 0 */
}






void encoder2()
{
  // Binary convolutional encoder, rate 1/n2
  register int i, j, result, temp;
 
  temp = memory2;
  output = 0;

  temp = (temp<<1) ^ data_symbol[index % TRUNC_LENGTH];

  for (i=0; i<n2; i++)
   {
     result = 0;
     for (j=m2; j>=0; j--)
       result ^= ( ( temp & g2[i][0] ) >> j ) & 1;
     output = ( output<<1 ) ^ result;
   }
  fprintf(stderr,"mem2: %d\n",memory2);
  memory2 = temp ;

}



void awgn()
{
  /* Add AWGN to transmitted sequence */
  double u1,u2,s,noise,randmum;
  int i;

  for (i=0; i<OUT_SYM; i++)
    {

      do
        {      
          randmum = (double)(random())/MAX_RANDOM;
          u1 = randmum*2.0 - 1.0;
          randmum = (double)(random())/MAX_RANDOM;
          u2 = randmum*2.0 - 1.0;
          s = u1*u1 + u2*u2;
        } while( s >= 1);
      noise = u1 * sqrt( (-2.0*log(s))/s );
      received[i] = transmitted[i] + noise/amp;
    }
}

void viterbi()
{
  double aux_metric, surv_metric[NUM_STATES];
  register int i,j,k;

  for (i=0; i<NUM_STATES; i++) /* Initialize survivor branch metric */
    surv_metric[i] = DBL_MAX;

  for (i=0; i<NUM_STATES; i++) /* Loop over inital states */
    {
      for (j=0; j<NUM_TRANS; j++) /* Loop over data */
        {

          /* Compute CORRELATION between received seq. and coded branch */
          aux_metric = 0.0;
          for (k=(OUT_SYM-1); k>=0; k--)
            aux_metric += comp_metric(received[k],trellis[i][j].output[k]);
          aux_metric += survivor[i].metric;

          /* compare with survivor metric at final state */
          /* We compare HAMMING DISTANCE*/

          if ( aux_metric < surv_metric[trellis[i][j].final] )
            { /* Good candidate found */

              surv_metric[trellis[i][j].final] = aux_metric;

              /* Update data and state paths */
              for (k=0; k<TRUNC_LENGTH; k++)
                {
                  surv_temp[trellis[i][j].final].data[k] =
                    survivor[i].data[k];
                  surv_temp[trellis[i][j].final].state[k] =
                    survivor[i].state[k];
                }
                  surv_temp[trellis[i][j].final].data[index%TRUNC_LENGTH] = j;
                  surv_temp[trellis[i][j].final].state[index%TRUNC_LENGTH] =
                    trellis[i][j].final;

            }
        }
    }
 
  for (i=0; i<NUM_STATES; i++)
    {
      /* Update survivor metrics */
      survivor[i].metric = surv_metric[i];
      for (k=0; k<TRUNC_LENGTH; k++)
        {
          survivor[i].data[k] = surv_temp[i].data[k];
          survivor[i].state[k] = surv_temp[i].state[k];
        }
    }

}

double comp_metric(double rec, double ref)
{ // HAMMING DISTANCE between received and reference values
// This is equivalent to hard decision + Hamming distance computation:
  if ( (rec<0.0)  && (ref<0.0) ) return(0.0);
  if ( (rec<0.0)  && (ref>0.0) ) return(1.0);
  if ( (rec>0.0)  && (ref<0.0) ) return(1.0);
  if ( (rec>0.0)  && (ref>0.0) ) return(0.0);
}
 



Файл1:(как смог так подогнал, документации к этим сорцам не было)

Код:
2 6 64 1 2 101010 101010 0 1 1


Главный вопрос такой, он вообще способен работать? Если да то как в него запихнуть мои данные, и зачем ему нужно столько много информации и решётчатой диаграмме? Разве полиномов, количества состояний глубины декодирования и начального состояния? Зачем на каждом шаге по решётке он просит начальное и конечное состояние? Писал какой-то китаец видимо, есть ли тут логика?


Мне нужно раскодировать с жётской метрикой последовательность из нулей и единиц, для k=6(64 состояния кодера)


Спасибо!!!

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group