viterbi216.c

一种应用比较广泛的维特比译码算法--（2

//实现（2，1，6）卷积码的维特比译码源程序，采用了最大似然算法 
//介绍了软判决维特比译码算法过程的三个步骤：初始化，度量更新和回溯译码
#include<stdio.h>
unsigned long Trans_table[32]={0}; //一个单元32位，每两个存储单元存储一个时刻的64状态幸存信息
unsigned long Tran;  //存储每个时刻的分支选择路径信息值，32位

void BFLY_A(int dp, int dm, int *p1, int *p2, int *p3);
void BFLY_B(int dp, int dm, int *p1, int *p2, int *p3);
void Tran_exchange();      //用于调整Tran中第2，3位的次序
int trace_back();

void main()
{
	//采用硬判决，1判为－1，0判为1
//  int sd[32]={-1,-1,1,-1,1,-1,-1,1,1,-1,1,1,-1,-1,-1,-1,
//         1,1,-1,1,-1,1,1,-1,-1,1,-1,-1,1,1,1,1};  //编码器连续输入8个1的输出
//  int sd[32]={-1,-1,1,-1,1,-1,-1,1,1,-1,1,1,1,1,-1,1,
//        -1,1,1,-1,-1,1,-1,-1,1,1,1,1,1,1,1,1};  //编码器输入11101100...的输出
    int sd[32]={-1,-1,1,-1,1,-1,-1,1,1,-1,1,1,1,1,-1,1,
    	    -1,1,1,-1,-1,1,-1,-1,1,1,1,1,1,1,1,1};  //编码器连续输入6个1的输出
//  int sd[32]={-1,-1,1,-1,-1,1,1,1,-1,1,1,-1,-1,-1,1,1,
//         -1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,1,1};  //编码器输入11010100...的输出

    int bef[64]={0};    //前64状态
    int aft[64]={0};    //后64状态
    int t0,t1;
    int n,i,j;
    int output;
    int *pb,*pa1,*pa2;
    int *pd,*p4;
    
    pd=sd;
    p4=Trans_table;
    bef[0]=100;  //从0状态开始，任意赋一个初值
    for(n=0;n<16;n++)
    {
    	pb=bef;
    	pa1=aft;
    	pa2=aft+2;
    	t1=*(pd++);
    	t0=t1+*pd;
    	t1=t1-*(pd++);
//    	printf("t0=%d,t1=%d\n",t0,t1);
      for(j=0;j<2;j++)  //每时刻64个状态，32个蝶形，两个蝶形为一组，共循环16次
      {
      	  Tran=0;
          for(i=0;i<8;i++)
          {
          	//计算两个蝶形运算中的第1，3分支度量值
          	  if(j==0)  //前半部分蝶形运算，分支度量使用因子t0,t1
          	  {
          	  	  if(i==2|i==3|i==4|i==5)  //前8个蝶形中，第2,3,4,5个蝶形实行翻转，即原来加t0变为减t0,原来加t1变为减t1
          	  	  	  BFLY_B(t0, t1, pb, pa1, pa2);
          	  	  else
          	  	  	  BFLY_A(t0, t1, pb, pa1, pa2);
          	  }
          	  else    //后半部分蝶形运算，分支度量使用因子t0,t1
          	  {
          	  	  if(i==2|i==3|i==4|i==5)  //后8个蝶形中，第0,1,6,7个蝶形实行翻转，即原来加t0变为减t0,原来加t1变为减t1
          	  	  	  BFLY_B(t1, t0, pb, pa1, pa2);
          	  	  else
          	  	  	  BFLY_A(t1, t0, pb, pa1, pa2);
          	  }
          	  
          	  pa1++;
              pa2++;
              //计算两个蝶形运算中的第1，3分支度量值
              if(j==0)  //前半部分蝶形运算，分支度量使用因子t0,t1
          	  {
          	  	  if(i==2|i==3|i==4|i==5)  
          	  	  {
          	  	  	  BFLY_A(t0, t1, pb, pa1, pa2);
          	  	  	  
          	  	  	  //调整Tran中第2，3位的次序
          	  	  	  Tran_exchange(); 
          	  	  }
          	  	  else
          	  	  {
          	  	  	  BFLY_B(t0, t1, pb, pa1, pa2);
          	  	  	  Tran_exchange();
          	  	  }
          	  }
          	  else    //后半部分蝶形运算
          	  {
          	  	  if(i==2|i==3|i==4|i==5)
          	  	  {  
          	  	  	  BFLY_A(t1, t0, pb, pa1, pa2);
          	  	  	  Tran_exchange();
          	  	  }
          	  	  else
          	  	  {
          	  	  	  BFLY_B(t1, t0, pb, pa1, pa2);
          	  	  	  Tran_exchange();
          	  	  }
          	  }
          	  
          	  pa1=pa1+3;  //进入下一组蝶形运算
      	      pa2=pa2+3;
      	      pb=pb+2;
      	  }//end of i
      	  *(p4++)=Tran;  //64个状态分两组存储
      }
      
      for(i=0;i<64;i++)
      	 bef[i]=aft[i];
    } 
  
    output=trace_back();
    printf("output=%x\n",output);  
}

void BFLY_A(int dp, int dm, int *p1, int *p2, int *p3)
{
	int a,b,c,d;
	int i;
	
	a=*p1+dp;
	b=*(p1+1)-dm;
	c=*(p1+32)-dp;
	d=*(p1+33)+dm;
	
	Tran=Tran<<1;
	
	*p2=a;
	*p3=b;
	if(c>a)  //c路径标记为1，a路径标记为0
	{
		Tran=Tran|0x01;
		*p2=c;
	}
	
	Tran=Tran<<1;
	
	if(d>b)   //d路径标记为1，b路径标记为0
	{
		Tran=Tran|0x01;
		*p3=d;
	}
}

void BFLY_B(int dp, int dm, int *p1, int *p2, int *p3)
{
	int a,b,c,d;
	
	a=*p1-dp;
	b=*(p1+1)+dm;
	c=*(p1+32)+dp;
	d=*(p1+33)-dm;
	
	Tran=Tran<<1;
	
	*p2=a;
	*p3=b;
	if(c>a)  //c路径标记为1，a路径标记为0
	{
		Tran=Tran|0x01;
		*p2=c;
	}
	
	Tran=Tran<<1;
	
	if(d>b)   //d路径标记为1，b路径标记为0
	{
		Tran=Tran|0x01;
		*p3=d;
	}
}

void Tran_exchange()
{
	int x,y;
	x=((Tran&0x04)?1:0);  //取出Tran的第3位
	y=((Tran&0x02)?1:0);  //取出Tran的第2位
	if(x!=y)  //如果不等则交换
	{
		if(x>y)
			Tran=Tran-2;  //Tran的第2，3位互换
		else
			Tran=Tran+2;  //Tran的第2，3位互换
	}
}

int trace_back()
{
	  int *p4;
	  int state;
	  unsigned temp=0;
	  int i,num;
	  
	  p4=Trans_table+32;  //移到数组最后
	  state=0;
	  for(i=0;i<16;i++)
	  {
	  	p4--;
	  	p4--;  //两个单元为一个整体，前一个单元处理前32状态
	  	printf("state=%x\n",state);
	  	
	    //下面分两部分操作，前一部分处理前32状态，后一部分处理后32状态
		  if(state>=0&&state<32)
		  {
	  	    if(state&0x01)  //只有state为奇数时，输入才可能为1
	  		    temp=(temp>>1)|0x8000;
	        else
	    	    temp=(temp>>1);
	    	
	        num=31-state;
	        state=state>>1;   //回到前一时刻
	        if((*p4>>num)&0x01)
	    	    state=state+32;
      }
      else if(state>=32&&state<64)
		  {  
		  	  p4++;
	  	    if(state&0x01)  //只有state为奇数时，输入才可能为1
	  		    temp=(temp>>1)|0x8000;
	        else
	    	    temp=(temp>>1);
	    	
	        num=63-state;
	        state=state>>1;   //回到前一时刻
	        if((*p4>>num)&0x01)
	    	    state=state+32;
	    	    
	    	  p4--;
      }
	    	
//	    printf("temp=%x\n",temp);
	  }
	  return temp;
}