📄 sdvd.cpp
字号:
/* SOFT-DECISION VITERBI DECODER */
/* Copyright (c) 1999, 2001 Spectrum Applications, Derwood, MD, USA */
/* All rights reserved */
/* Version 2.2 Last Modified 2001.11.28 */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
//#include <values.h>
#include "vdsim.h"
//#define DEBUG
#define SLOWACS
#undef FASTACS
#define NORM
#define MAXMETRIC 128
#define MAXINT 32767
void deci2bin(int d, int size, int *b);
int bin2deci(int *b, int size);
int nxt_stat(int current_state, int input, int *memory_contents);
void init_quantizer(void);
void init_adaptive_quant(double es_ovr_n0);
int soft_quant(double channel_symbol);
int soft_metric(int data, int guess);
int quantizer_table[256];
void sdvd(int g[2][K], double es_ovr_n0, long channel_length, double *channel_output_vector, int *decoder_output_matrix)
{
int i, j, l, ll; /* loop variables */
long t; /* time */
int memory_contents[K]; /* input + conv. encoder sr */
int input[TWOTOTHEM][TWOTOTHEM]; /* maps current/nxt sts to input */
int output[TWOTOTHEM][2]; /* gives conv. encoder output */
int nextstate[TWOTOTHEM][2]; /* for current st, gives nxt given input */
double accum_err_metric[TWOTOTHEM][2]; /* accumulated error metrics */
int state_history[TWOTOTHEM][K * 5 + 1]; /* state history table */
int state_sequence[K * 5 + 1]; /* state sequence list */
int *channel_output_matrix; /* ptr to input matrix */
int binary_output[2]; /* vector to store binary enc output */
int branch_output[2]; /* vector to store trial enc output */
double x, xx;
int m, n, number_of_states, depth_of_trellis, step, branch_metric, sh_ptr, sh_col, h, hh, next_state, last_stop; /* misc variables */
/* ************************************************************************** */
/* n is 2^1 = 2 for rate 1/2 */
n = 2;
/* m (memory length) = K - 1 */
m = K - 1;
/* number of states = 2^(K - 1) = 2^m for k = 1 */
number_of_states = (int) pow(2.0, 1.0*m);
/* little degradation in performance achieved by limiting trellis depth
to K * 5--interesting to experiment with smaller values and measure
the resulting degradation. */
depth_of_trellis = K * 5;
/* initialize data structures */
for (i = 0; i < number_of_states; i++) {
for (j = 0; j < number_of_states; j++)
input[i][j] = 0;
for (j = 0; j < n; j++) {
nextstate[i][j] = 0;
output[i][j] = 0;
}
for (j = 0; j <= depth_of_trellis; j++)
{
state_history[i][j] = 0;
}
/* initial accum_error_metric[x][0] = zero */
accum_err_metric[i][0] = 0.0;
/* by setting accum_error_metric[x][1] to MAXINT, we don't need a flag */
/* so I don't get any more questions about this: */
/* MAXINT is simply the largest possible integer, defined in values.h */
accum_err_metric[i][1] = MAXINT;
// printf("i = %d\n",i);
}
/* generate the state transition matrix, output matrix, and input matrix
- input matrix shows how FEC encoder bits lead to next state
- next_state matrix shows next state given current state and input bit
- output matrix shows FEC encoder output bits given current presumed
encoder state and encoder input bit--this will be compared to actual
received symbols to determine metric for corresponding branch of trellis */
for (j = 0; j < number_of_states; j++) {
for (l = 0; l < n; l++) {
next_state = nxt_stat(j, l, memory_contents);
/* this function calculates the next state of the convolutional encoder, given
the current state and the input data. It also calculates the memory
contents of the convolutional encoder.
int nxt_stat(int current_state, int input, int *memory_contents)
*/
input[j][next_state] = l;
/* now compute the convolutional encoder output given the current
state number and the input value */
branch_output[0] = 0;
branch_output[1] = 0;
for (i = 0; i < K; i++) {
branch_output[0] ^= memory_contents[i] & g[0][i];
branch_output[1] ^= memory_contents[i] & g[1][i];
}
/* next state, given current state and input */
nextstate[j][l] = next_state;
/* output in decimal, given current state and input */
output[j][l] = bin2deci(branch_output, 2);
} /* end of l for loop */
} /* end of j for loop */
#ifdef DEBUG
printf("\nInput:");
for (j = 0; j < number_of_states; j++) {
printf("\n");
for (l = 0; l < number_of_states; l++)
printf("%2d ", input[j][l]);
} /* end j for-loop */
printf("\nOutput:");
for (j = 0; j < number_of_states; j++) {
printf("\n");
for (l = 0; l < n; l++)
printf("%2d ", output[j][l]);
} /* end j for-loop */
printf("\nNext State:");
for (j = 0; j < number_of_states; j++) {
printf("\n");
for (l = 0; l < n; l++)
printf("%2d ", nextstate[j][l]);
} /* end j for-loop */
#endif
channel_output_matrix = new int [channel_length];
if (channel_output_matrix == NULL) {
printf( "\nsdvd.c: Can't allocate memory for channel_output_matrix! Aborting...");
exit(1);
} /* now we're going to rearrange the channel output so it has n rows,
and n/2 columns where each row corresponds to a channel symbol for
a given bit and each column corresponds to an encoded bit */
channel_length = channel_length / n;
/* interesting to compare performance of fixed vs adaptive quantizer */
/* init_quantizer(); */
init_adaptive_quant(es_ovr_n0);
/* quantize the channel output--convert double to short integer */
/* channel_output_matrix = reshape(channel_output, n, channel_length) */
for (t = 0; t < (channel_length * n); t += n) {
for (i = 0; i < n; i++)
*(channel_output_matrix + (t / n) + (i * channel_length) ) = soft_quant( *(channel_output_vector + (t + i) ) );
} /* end t for-loop */
/* ************************************************************************** */
/* End of setup. Start decoding of channel outputs with forward
traversal of trellis! Stop just before encoder-flushing bits. */
for (t = 0; t < channel_length - m; t++) {
if (t <= m) /* assume starting with zeroes, so just compute paths from all-zeroes state */
step = (int) pow(2.0, 1.0*(m - t * 1));
else
step = 1;
/* we're going to use the state history array as a circular buffer so
we don't have to shift the whole thing left after each bit is
processed so that means we need an appropriate pointer */
/* set up the state history array pointer for this time t */
sh_ptr = (int) ( ( t + 1 ) % (depth_of_trellis + 1) );
/* repeat for each possible state */
for (j = 0; j < number_of_states; j+= step) {
/* repeat for each possible convolutional encoder output n-tuple */
for (l = 0; l < n; l++) {
branch_metric = 0;
/* compute branch metric per channel symbol, and sum for all
channel symbols in the convolutional encoder output n-tuple */
#ifdef SLOWACS
/* convert the decimal representation of the encoder output to binary */
deci2bin(output[j][l], n, binary_output);
/* compute branch metric per channel symbol, and sum for all
channel symbols in the convolutional encoder output n-tuple */
for (ll = 0; ll < n; ll++) {
branch_metric = branch_metric + soft_metric( *(channel_output_matrix +
( ll * channel_length + t )), binary_output[ll] );
} /* end of 'll' for loop */
#endif
#ifdef FASTACS
/* this only works for n = 2, but it's fast! */
/* convert the decimal representation of the encoder output to binary */
binary_output[0] = ( output[j][l] & 0x00000002 ) >> 1;
binary_output[1] = output[j][l] & 0x00000001;
/* compute branch metric per channel symbol, and sum for all
channel symbols in the convolutional encoder output n-tuple */
branch_metric = branch_metric + abs( *( channel_output_matrix +
( 0 * channel_length + t ) ) - 7 * binary_output[0] ) +
abs( *( channel_output_matrix +
( 1 * channel_length + t ) ) - 7 * binary_output[1] );
#endif
/* now choose the surviving path--the one with the smaller accumulated error metric... */
if ( accum_err_metric[ nextstate[j][l] ] [1] > accum_err_metric[j][0] + (double)branch_metric ) {
/* save an accumulated metric value for the survivor state */
accum_err_metric[ nextstate[j][l] ] [1] = accum_err_metric[j][0] + (double) branch_metric;
/* update the state_history array with the state number of the survivor */
state_history[ nextstate[j][l] ] [sh_ptr] = j; // 表示nextstate是从j state来的
} /* end of if-statement */
} /* end of 'l' for-loop */
} /* end of 'j' for-loop -- we have now updated the trellis */
/* for all rows of accum_err_metric, move col 2 to col 1 and flag col 2 */
for (j = 0; j < number_of_states; j++) {
accum_err_metric[j][0] = accum_err_metric[j][1];
accum_err_metric[j][1] = MAXINT; // accum_err_metric[j][1]的初始值是MAXINT
} /* end of 'j' for-loop */
/* now start the traceback, if we've filled the trellis */
if (t >= depth_of_trellis - 1) {
/* initialize the state_sequence vector--probably unnecessary */
for (j = 0; j <= depth_of_trellis; j++)
state_sequence[j] = 0;
/* find the element of state_history with the min. accum. error metric */
/* since the outer states are reached by relatively-improbable runs
of zeroes or ones, search from the top and bottom of the trellis in */
x = MAXINT;
for (j = 0; j < ( number_of_states / 2 ); j++) {
if ( accum_err_metric[j][0] < accum_err_metric[number_of_states - 1 - j][0] ) {
xx = accum_err_metric[j][0];
hh = j;
}
else {
xx = accum_err_metric[number_of_states - 1 - j][0];
hh = number_of_states - 1 - j;
}
if ( xx < x) {
x = xx;
h = hh;
}
} /* end 'j' for-loop */
#ifdef NORM
/* interesting to experiment with different numbers of bits in the
accumulated error metric--does performance decrease with fewer bits? */
/* if the smallest accum. error metric value is > MAXMETRIC, normalize the
accum. errror metrics by subtracting the value of the smallest one from
all of them (making the smallest = 0) and saturate all other metrics
at MAXMETRIC */
if (x > MAXMETRIC) {
for (j = 0; j < number_of_states; j++) {
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -