//實現（2，1，6）卷積碼的維特比譯碼源程序，采用了最大似然算法 
//介紹了軟判決維特比譯碼算法過程的三個步驟：初始化，度量更新和回溯譯碼
#include<stdio.h>
unsigned long Trans_table[32]={0}; //一個單元32位，每兩個存儲單元存儲一個時刻的64狀態(tài)幸存信息
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};  //編碼器連續(xù)輸入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};  //編碼器連續(xù)輸入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狀態(tài)
    int aft[64]={0};    //后64狀態(tài)
    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狀態(tài)開始，任意賦一個初值
    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個狀態(tài)，32個蝶形，兩個蝶形為一組，共循環(huán)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變?yōu)闇pt0,原來加t1變?yōu)闇pt1
          	  	  	  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變?yōu)闇pt0,原來加t1變?yōu)闇pt1
          	  	  	  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個狀態(tài)分兩組存儲
      }
      
      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狀態(tài)
	  	printf("state=%x\n",state);
	  	
	    //下面分兩部分操作，前一部分處理前32狀態(tài)，后一部分處理后32狀態(tài)
		  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;
}