viterbi.cpp

自己编写的viterbi译码算法

//****************************************************************
//(2,1,2)卷积码编码器与viterbi译码算法的实现
//该码的生成电路见课本P393，图10-9，G（D）=[1，1+D+D^2]；
//****************************************************************
//通信与信息系统专业    詹锐鑫   07212439	2008年1月24日
//****************************************************************

#include <iostream.h>
#include <stdlib.h>

const int length=20;				//表示卷积码的输出长度；显然，输出长度为输入长度的2倍；
int m[length/2]={1,0,1,1,1,0,0,0,1,1};	//输入序列，其长度为输出码字的一半；
int code[length]={0};				//编码器的输出序列，其长度为输入的2倍；
										
int rs[length]={1,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,1,0,0};
									//经过信道后，译码器的输入信息；可能有若干位出错；
int ds[length/2]={0};				//译码器的输出，可纠正若干错误位；

//****************************************
void coding(int *in_m,int * out_d);	//编码器函数；

void viterbi(int *rs,int *ds);		//veterbi译码器函数；
//****************************************

void main()
{
	int i=0;
	
	//对于给定的输入信息，输出其编码；
	coding(m,code);					//若想改变测试数据，可修改前面的m和length值；
									//可以得到不同的测试数据；
	for(i=0;i<length/2;i++)
		cout<<m[i];
	cout<<"  输入信息元（未编码）"<<endl;
	for(i=0;i<length;i++)
		cout<<code[i];
	cout<<"  输出编码码字（编码器输出）"<<endl;
	
	//对于给定的译码器输入，输出其译码值；
	viterbi(rs,ds);					//可由上面的编码器输出，随机修改N位，测试其译码器的输出；
									//也可以采用rand()函数，随机改变N位数据
									//作为信道传输错误的仿真；
	
	for(i=0;i<length;i++)
		cout<<rs[i];
	cout<<"  译码器的输入序列，含有N位随机或突发错误；"<<endl;
	for(i=0;i<length/2;i++)
		cout<<ds[i];
	cout<<" 译码器的输出,可能修改出现的错误,也可能译码失败,但仍输出误差最小的译码"<<endl;

}

//(2,1,2)卷积码编码器；
//采用状态机编程思想；划分为四个状态，并按输入，进行状态转移；
void coding(int * in_m,int * out_d)		
{
	int state=0;					//当前状态；
	int next_state=0;				//下一状态值；

	for(int i=0;i<(length)/2;i++)	//有length/2个输入，就有length/2次状态转移；
	{
		if(state==0)				//状态0；
		{
			if(in_m[i]==0)				//输入0，仍处于状态0，输出：00；
			{
				next_state=0;
				out_d[2*i]=0;
				out_d[2*i+1]=0;
			}
			else if(in_m[i]==1)			//输入1，跳到状态1，输出：11；
			{
				next_state=1;
				out_d[2*i]=1;
				out_d[2*i+1]=1;
			}
		}

		else if(state==1)			//状态1
		{
			if(in_m[i]==0)				//输入0，跳到状态2，输出：10；
			{
				next_state=2;
				out_d[2*i]=1;
				out_d[2*i+1]=0;
			}
			else if(in_m[i]==1)			//输入1，跑到状态3，输出：01；
			{
				next_state=3;
				out_d[2*i]=0;
				out_d[2*i+1]=1;
			}
		}

		else if(state==2)			//状态2
		{
			if(in_m[i]==0)				//输入0，跳到状态0，输出：11；
			{
				next_state=0;
				out_d[2*i]=1;
				out_d[2*i+1]=1;
			}
			else if(in_m[i]==1)			//输入1，跳到状态1，输出：00；
			{
				next_state=1;
				out_d[2*i]=0;
				out_d[2*i+1]=0;
			}
		}
		else if(state==3)			//状态3
		{
			if(in_m[i]==0)				//输入0，跳到状态2，输出：01；
			{
				next_state=2;
				out_d[2*i]=0;
				out_d[2*i+1]=1;
			}
			else if(in_m[i]==1)			//输入法1，跳到状态3，输出：10；
			{
				next_state=3;
				out_d[2*i]=1;
				out_d[2*i+1]=0;
			}
		}
		state=next_state;			//跳到下一状态；
	}
	return;							//编码结束；
}

//viterbi译码算法实现；
void viterbi(int *rs,int *ds)
{
	struct	unit 					//各时刻各状态记录
		{
			unsigned	last_point;			//本状态的上一最优状态
			unsigned	weight;			//到本状态的总重量
			unsigned	over;			//本状态是否走过
		};					//（length/2）+1个时刻,4个状态
	unit point[(length/2)+1][4];

	int i,j;		      
	for(i=0;i<(length/2)+1;i++)
		for (j=0;j<4;j++)
			{							//初始化清零所有时刻状态
				point[i][j].last_point=0;
				point[i][j].weight=0;
				point[i][j].over=0;
			}
	point[0][0].over=1;				//从零时刻零状态开始
	
//上一时刻此状态到本时刻此状态，其重量的改变，采用^按位异或
//t=1时刻：
	point[1][0].weight=point[0][0].weight+(rs[0]^0)+(rs[1]^0);
	point[1][1].weight=point[0][0].weight+(rs[0]^1)+(rs[1]^1);
	point[1][0].last_point=0;
	point[1][1].last_point=0;

//如果只有两输入，则结束译码过程：
	if(length==2)
	{
		if(point[1][0].weight<point[1][1].weight)
		{
			ds[0]=0;
		}
		else ds[0]=1;
			return;
	}
			
//t=2时刻：
//有多于两个输入，继续译码过程：
	point[2][0].weight=point[1][0].weight+(rs[2]^0)+(rs[3]^0);
	point[2][1].weight=point[1][0].weight+(rs[2]^1)+(rs[3]^1);
	
	point[2][0].last_point=0;
	point[2][1].last_point=0;

	point[2][2].weight=point[1][1].weight+(rs[2]^1)+(rs[3]^0);
	point[2][3].weight=point[1][1].weight+(rs[2]^0)+(rs[3]^1);
			
	point[2][2].last_point=1;
	point[2][3].last_point=1;

	point[1][0].over=1;
	point[1][1].over=1;

//有多于6个输入，则继续译码，否则结束译码过程：
	unsigned	p1,p2; //到达本时刻本状态的两条路径的各自重量；
	if(length>=6)
	{
//t=3,4,5,6……时刻：
		for	(i=3;i<=length/2;i++)
		{
			p1=point[i-1][0].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^0);	//处于状态0
			p2=point[i-1][2].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^1);	//两条输入路径各自重量；
																		//总距离p1,p2,取最短者
			if (p1>p2) 
			{  	
				point[i][0].last_point=2;
				point[i][0].weight=p2;
				point[i-1][2].over=1;
			} 
            else 
			{ 
				point[i][0].last_point=0;
				point[i][0].weight=p1;
				point[i-1][0].over=1;
			}

			p1=point[i-1][0].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^1);	//state=1
			p2=point[i-1][2].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^0);
			if (p1>p2) 
			{  
				point[i][1].last_point=2;
				point[i][1].weight=p2;
				point[i-1][2].over=1;
			} 
            else 
			{ 
				point[i][1].last_point=0;
				point[i][1].weight=p1;
				point[i-1][0].over=1;
			}

			p1=point[i-1][1].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^0);	//state=2
			p2=point[i-1][3].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^1);
			if (p1>p2) 
			{  
				point[i][2].last_point=3;
				point[i][2].weight=p2;
				point[i-1][3].over=1;
			} 
            else 
			{ 
				point[i][2].last_point=1;
				point[i][2].weight=p1;
				point[i-1][1].over=1;
			}

			p1=point[i-1][1].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^1);	//state=3
			p2=point[i-1][3].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^0);
			if (p1>p2) 
			{  
				point[i][3].last_point=3;
				point[i][3].weight=p2;
				point[i-1][3].over=1;
			} 
            else 
			{ 
				point[i][3].last_point=1;
				point[i][3].weight=p1;
				point[i-1][1].over=1;
			}
		}//t=3,4,5,6……
	}
	unsigned	path[(length/2)+1]={0};			//记录状态转移路径
	unsigned	result[length/2]={0};			//记录解码信息位输出
	unsigned	last;							//最近的状态，递推回去的变量；

	//判断最后一个节点的总重量最低者，作为译码的最后一个状态；作为递推回去的出发点；
	last=point[length/2][0].weight;
	path[length/2]=0;
	for(i=1;i<=3;i++)
	{
		if(point[length/2][i].weight<last)
		{
			last=point[length/2][i].weight;
			path[length/2]=i;
		}
	}

	//递推回到出发点，最佳路径的每个节点状态；
	for(i=(length/2)-1;i>=0;i--)
	{
		last=point[i+1][path[i+1]].last_point;
		path[i]=last;
	}
		
	//根据每个点的最佳状态，推出其输入码位，主要根据状态转移图判断；
	for	(i=1;i<=length/2;i++)
	{
		if	((path[i]==0) || (path[i]==2))			
				result[i-1]=0;
		else	if	((path[i]==1) || (path[i]==3))	
				result[i-1]=1;
	}


	for(i=0;i<=(length/2)-1;i++)
		ds[i]=result[i];							//结果作为译码输出；
}