viterbi23.c

自己写的Viterbi Decoder 可以解码 213 417 码率

/*
	Viterbi decorder for convolution code [2 1 3]
	Code rate				1/2
	constrained len(K)		3
	Use hard decision

	jinle@2008.2.29
*/
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
#include "viterbi23.h"

/*#################################################################
Func:
	Viterbi decoder handler initialize function
Input:
	*this	viterbi decoder handler
Return:
	void
#################################################################*/
void viterbi_decoder_init(ViterbiDec *this)
{
	int i, j;

	this->column_pointer = 0;
	for(i=0; i<MAX_COLUMN; i++)
	{
		for(j=0; j<STATE_NUM; j++)
		{
			this->grids[i][j].acc_metric = 0;
			this->grids[i][j].lastgrid = 0;
		}
	}
	this->beInited = TRUE;
	fprintf(stderr, "Viterbi decoder for code[2 1 3], initialized.\n");
}

/*#################################################################
Func:
	Get last grid number or state number, with upper path or lower
Input:
	current		current state number
	pos			path position UPPER or LOWER
Return:
	ret			last grid number
#################################################################*/
static unsigned char get_last_state_number(int current, _Bool pos)
{
	return Viterbi23_last_state_table[current][pos];
}

/*#################################################################
Func:
	Get metric value of current input data, with upper path or lower
Input:
	current		current state number
	pos			path position UPPER or LOWER
	input		input data
Return:
	ret			path metric value
Note:
	Use hard decision
#################################################################*/
static unsigned char get_path_hard_metric(int current, _Bool pos, unsigned char input)
{
	int ret;
	ret = input^Viterbi23_output_table[current][pos];
	return (ret&0x01) + (ret>>1);
}

/*#################################################################
Func:
	Get output value with specified from and to
Input:
	from		from grid state number
	to			to grid state number
Return:
	ret			output value
#################################################################*/
static _Bool path2value(unsigned char from, unsigned char to)
{
	char check;

	check = Viterbi23_path2value[from][to];
	if(check == NOT_VALID)
	{
		fprintf(stderr, "Viterbi Decoder: path2value get invalid value! from %d to %d\n", from, to);
		check = 0;
	}
#ifdef VITERBI_DEBUG
	fprintf(stderr, "From %d to %d value %d\n", from, to, check);
	getchar();
#endif
	return (_Bool)check;
}

/*#################################################################
Func:
	Viterbi add-compare-sellect routine
Input:
	*this	viterbi decoder handler
	input	data input
Return:
	1:		Viterbi buffer not complete
	0:		Can trace back and output
#################################################################*/
static _Bool viterbi_acs(ViterbiDec *this, unsigned char input)
{
	int i;
	int row = STATE_NUM;
	int colomn = this->column_pointer;
	unsigned char upmetric, lowmetric;		//current path metric
	char uptmpaccm, lowtmpaccm;				//total acc metric of upper and lower path
	unsigned char uplastgrid, lowlastgrid;	//last grid number of upper and lower path
	int accm, lastgrid;
	/*For each grid in row, perform ACS*/
	//First let's handle first 2 columns
	if(this->column_pointer == 0)
	{
		this->grids[0][0].acc_metric = get_path_hard_metric(0, UPPER, input);
		this->grids[0][0].lastgrid = 0;
		this->grids[0][2].acc_metric = get_path_hard_metric(2, UPPER, input);
		this->grids[0][2].lastgrid = 0;
		//printf("%d %d\n", this->grids[0][0].acc_metric, this->grids[0][2].acc_metric);
	}
	else if(this->column_pointer == 1)
	{
		this->grids[1][0].acc_metric = get_path_hard_metric(0, UPPER, input) + this->grids[0][0].acc_metric;
		this->grids[1][0].lastgrid = 0;
		this->grids[1][1].acc_metric = get_path_hard_metric(1, UPPER, input) + this->grids[0][2].acc_metric;
		this->grids[1][1].lastgrid = 2;
		this->grids[1][2].acc_metric = get_path_hard_metric(2, UPPER, input) + this->grids[0][0].acc_metric;
		this->grids[1][2].lastgrid = 0;
		this->grids[1][3].acc_metric = get_path_hard_metric(3, UPPER, input) + this->grids[0][2].acc_metric;
		this->grids[1][3].lastgrid = 2;
		//printf("%d %d %d %d\n", this->grids[1][0].acc_metric, this->grids[1][1].acc_metric,this->grids[1][2].acc_metric, this->grids[1][3].acc_metric);
	}
	else
	{
		for(i=0; i<row; i++)
		{
			/*Get metric of two path*/
			upmetric = get_path_hard_metric(i, UPPER, input);
			lowmetric = get_path_hard_metric(i, LOWER, input);
			/*ADD*/
			uplastgrid = get_last_state_number(i, UPPER);
			lowlastgrid = get_last_state_number(i, LOWER);
			
			uptmpaccm = upmetric + this->grids[colomn-1][uplastgrid].acc_metric;
			//printf("up %d+%d=%d\n", upmetric, this->grids[colomn-1][uplastgrid].acc_metric, uptmpaccm);
			lowtmpaccm = lowmetric + this->grids[colomn-1][lowlastgrid].acc_metric;
			//printf("lo %d+%d=%d\n", lowmetric, this->grids[colomn-1][lowlastgrid].acc_metric, lowtmpaccm);
			
			/*COMPARE*/
			if(uptmpaccm <= lowtmpaccm)
			{
				accm = uptmpaccm;
				lastgrid = uplastgrid;
			}
			else
			{
				accm = lowtmpaccm;
				lastgrid = lowlastgrid;
			}
			/*SELLECT*/
			this->grids[colomn][i].acc_metric = accm;
			this->grids[colomn][i].lastgrid = lastgrid;
			//printf("%d\n", accm);
		}
		//printf("\n");
	}
	/*Update row complete, now add pointer*/
	this->column_pointer += 1;
	/*whether buffer is completed or not*/
	if(this->column_pointer == 6)
		return TRUE;
	else
		return FALSE;
}
/*#################################################################
Func:
	Trace back from smallest metric path, and output one bit
Input:
	*this	viterbi decoder handler
Return:
	one bit value
#################################################################*/
static _Bool trace_back(ViterbiDec *this)
{
	int i;
	unsigned char smallest_metric = 0xFF;
	unsigned char smallest_grid = 0;
	unsigned char from, to;
	
	/*Get current row smallest metric grid*/
	for(i=0; i<STATE_NUM; i++)
	{
		if(this->grids[5][i].acc_metric<smallest_metric)
		{
			smallest_metric = this->grids[5][i].acc_metric;
			smallest_grid = i;
		}
	}
	/*Trace back, and get output value*/
	//printf("BT\n");
	//printf("%d", smallest_grid);
	for(i=MAX_COLUMN-1; i>=1; i--)
	{
		smallest_grid = this->grids[i][smallest_grid].lastgrid;
		//printf("%d", smallest_grid);
	}
	//printf("\n");
	//Output path from and to
	//Also means from column-1 to column0
	from = this->grids[0][smallest_grid].lastgrid;
	to = smallest_grid;
	return path2value(from, to);
}
/*#################################################################
Func:
	when decoder was output one bit data, move left inorder to
	receive next data
Input:
	*this	viterbi decoder handler
Return:
	void
#################################################################*/
static void move_left(ViterbiDec *this)
{
	int i, j;
	
	for(i=0; i<MAX_COLUMN-1; i++)
	{
		for(j=0; j<STATE_NUM; j++)
		{
			this->grids[i][j].acc_metric = this->grids[i+1][j].acc_metric;
			this->grids[i][j].lastgrid = this->grids[i+1][j].lastgrid;
		}
	}
	this->column_pointer--;
}

/*#################################################################
Func:
	Viterbi decoder processing routine
Input:
	*this	viterbi decoder handler
	input	input data, n bits in dec
Return:
	output	output data in binary, or NOT_VALID(-1)
Note:
	i.e. rate 1/3, once input 3 bits, output 1 bit
#################################################################*/
char viterbi_decoder_process_data(ViterbiDec *this, unsigned char input)
{
	_Bool out_valid;
	_Bool outdata;
	//Process ACS routine
	out_valid = viterbi_acs(this, input);

	//Trace back if possable
	if(out_valid == TRUE)
	{
		outdata = trace_back(this);
		//When output is done All data structure move left
		move_left(this);
		return outdata;
	}
	else
	{
		return NOT_VALID;
	}
}

/*#################################################################
Func:
	Get current wrong bit number from decoder
Input:
	*this	viterbi decoder handler
Return:
	wrong bit number
Note:
	This number is the smallest metric, if no wrong transfer
	this number should be 0
#################################################################*/
int get_err_from_decoder(ViterbiDec *this)
{
	int i;
	unsigned char smallest_metric = 0xFF;
	
	/*Get current row smallest metric grid*/
	for(i=0; i<STATE_NUM; i++)
	{
		if(this->grids[0][i].acc_metric<smallest_metric)
		{
			smallest_metric = this->grids[5][i].acc_metric;
		}
	}
	return smallest_metric;
}


#if 1
//Main() for test
/*
	ENC in: 0  1  0  1  1  1  0  0  1  0  1  0  0  0  1  0  0
	ENC ou: 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 11
	Rec in: 00 11 11 00 01 10 01 11 11 10 00 00 11 00 11 10 11
	DEC Ou: 0  1  0  1  1  1  0  0  1  0  1  0  0  0  1  0  0
*/

int main(void)
{
	int i;
	char ret;
	ViterbiDec	dec;
	//unsigned char input[22]={0,3,2,0,1,2,1,3,3,2,0,2,3,0,3,2,3,0,0,0,0,0};	//Right
	//unsigned char input[22]={0,3,3,0,1,2,1,3,3,2,0,0,3,0,3,2,3,0,0,0,0,0};	//Wrong 2
	unsigned char input[22] = {0,3,2,0,1,2,1,3,3,2,0,2,3,0,3,2,3,0,0,0,0,0};
	viterbi_decoder_init(&dec);
	fprintf(stderr, "Viterbi decoder output: ");
	for(i=0; i<22; i++)
	{
		ret = viterbi_decoder_process_data(&dec, input[i]);
		if(ret != NOT_VALID)
			fprintf(stderr, "%d", ret);
	}
	fprintf(stderr, "\n");
	fprintf(stderr, "Total wrong bit %d\n", get_err_from_decoder(&dec));

	return 0;
}
#endif