* viterbi.cpp jdg 2005/04/20 
一個(k,n,K)的卷積碼的維特比譯碼算法 
*/
#define k 1 //一次輸入序列的長度
#define n 3 //一次輸出序列的長度
#define K 3 //約束長度
#define DECODER_STATES 4 //狀態數2^(K-1)*k
#define BRANCH_NUM 2 //從一個狀態延伸的分支數
#define PATH_LENGTH 16 //路徑保留長度
#include <stdlib.h>
#include "stdafx.h"
//#include "viterbi.h"
//#include "encode.cpp"
//#include "randsource.cpp"

/* 多項式生成 g1=1[00000001](1) ,
g2=x^2+1[00000101](5),
g3=x^2+x^1+1[00000111](7) 

*/

int g[n][K*k]={1,0,0,
1,0,1,
   1,1,1 };

//-------------------------------分支結構定義
struct branch
{
int state_index,//狀態索引
     input[k],//輸入信息
     output[n];//輸出碼子
double cm; //量度
};

//------------------------------狀態結構定義
struct state
  { 
double sum_cm;//累積量度
struct branch branchs[BRANCH_NUM];//下一個狀態數組
       int   survivor[PATH_LENGTH]; //幸存路徑
   struct branch best_branch; //到達的2^k條分支中最好的一條

}; 
state states[DECODER_STATES];

//------------------------------二進制隨機信源生成函數

int randsource(int *x,int length)
{ int i;
printf("正在生成長度為 %d 的二進制的隨機數序列x[] 。。。\n",length);
for(i=0; i<length; i++) 
{
   if (i%10==0) printf("\n");
*(x+i)= rand() % 2;
   printf("%d,", *(x+i) );
}
return 0; 
}

//------------------------------把整數變成數組向量函數
int int_to_vector(int x,int *vector,int vlength)
{
  int i;
  for(i=0;i<vlength;i++)
   *(vector+i)=x>>i&1;
  return 0;
}

//------------------------------計算分支量度，cm=cm+Rjm*(2*Cjm-1);
double compute_cm(int *r,int *c) 
{
  int x;
  double cm=0.0;
  for(x=0;x<n;x++) 
    cm+=r[x]*(2*c[x]-1);
    //cm+=(r>>x)*(2*(c>>x)-1);
  return cm;
}

//編碼函數，input輸入，ilength輸入長度，output輸出，olength輸出長度，，currentstate當前狀態
int con_encode(int *input ,int ilength,int *output,int olength ,int *currentstate)
{
  int out[n],
    i,j,x,p=0, //循環變量
    reg[K*k]; //移位寄存器
  for(i=0;i<ilength/k;i++) //對每k位輸入bit循環
  {
    for(j=0;j<k;j++) //把輸入的k位bit送入移位寄存器 
     reg[j]=*(input+i+j); 
    for (j=k;j<K*k;j++) //把當前狀態放人移位寄存器
      reg[j]=*(currentstate+j-k); 
    for(j=0;j<K*k;j++) //生成輸出的n位bit信息 
    {
      for(x=0;x<n;x++)
        out[x]+=g[x][j]^reg[j];
    }
    for(x=0;x<n;x++)
    {
*(output+p)=out[x];
     p++;
      if (p>olength) 
        printf("\n 輸出長度超過預定義輸出數字長度，請檢查輸出數組定義！\n");
    }

    for(j=0;j<(K-1)*k;j++)
*(currentstate+j)=reg[j];
  }

  return 0;

}

/* Viterbi算法解卷積碼函數，參數說明
r:解調輸出序列，
rlength:r的長度
decode:解碼后的序列
dlength:decode的長度
*/
int ViterbiDecode(int *r,int rlength,int *decoded,int dlength)
{
  int i,j,x,y;
  int rm[n],//接收向量
    cur_state[(K-1)*k];//當前狀態向量
  double temp_cm,temp_sum_cm[DECODER_STATES];//臨時量度
int *temp_input[DECODER_STATES];//臨時變量
  int one=0,zero=0;
  //各狀態初始化
  for (i=0;i<DECODER_STATES;i++)
  {
states[i].sum_cm=-65535;
    for(j=0;j<BRANCH_NUM;j++)
    {
      states[i].branchs[j].state_index=i<<k^j;
     int_to_vector(j,states[i].branchs[j].input,k);
      int_to_vector(i,cur_state,(K-1)*k);
con_encode(states[i].branchs[j].input,k,states[i].branchs[j].output,n ,cur_state);
    }

    for(j=0;j<PATH_LENGTH;j++)
      states[i].survivor[j]=-1;
  }
states[0].sum_cm=0.0;
//-----------------------------初始化完畢
//-----------------------------對每個接收的n維矢量循環
for (x=0;x<rlength/n;x++) 
  { 
  
    for (i=0;i<n;i++) //從接收序列中取出一個碼子的長度
      rm[i]=*(r+x+i);

for (i=0;i<DECODER_STATES;i++) //對每個狀態循環
  {
for (j=0;j<DECODER_STATES;j++)
      {
for(y=0;y<BRANCH_NUM;y++)
        {
          if (states[j].branchs[y].state_index==i)
          {
            //計算分支量度
            temp_cm=states[j].sum_cm+compute_cm(rm,states[j].branchs[y].output);
if (temp_sum_cm[i]<temp_cm) 
            {
              temp_sum_cm[i]=temp_cm;
temp_input[i]=states[j].branchs[y].input;
            }
            break;
          }
        }
      }

    }
     for(i=0;i<k;i++)
     *(decoded+x+i)=states[0].survivor[PATH_LENGTH-1-i];
for (i=0;i<DECODER_STATES;i++) 
     {
       states[i].sum_cm=temp_sum_cm[i];
       for(j=PATH_LENGTH-1;j>k-1;j--)
       states[i].survivor[j]=states[i].survivor[j-k];
       for (j=0;j<k;j++)
         states[i].survivor[k-1-j]=*(temp_input[i]+j);
     }
  }
return 0;

}

int _tmain(int argc, _TCHAR* argv[])
{
  //int i;
  int x[100];
  randsource(x,100);
  /*
  printf("encoded stream...\n");
  for(i=0;i<100;i++)
  {  
  printf(" %d " ,con_encode(1));
  }
  printf("\n decoded stream...\n");
  for(i=0;i<100;i++)
  {  
   printf(" %d",ViterbiDecode(con_encode(1)));
  }
  */

  return 0;
} 


//


我把我的viterbi程序貼出來，歡迎高手指教
//文件名：Viterbi216.h
//作 用：對1/2碼率，N＝7的卷積碼進行維特比譯碼（硬判決）
//作 者：蔣巖
//時 間：2005.7.25
//版 本：VC－－1.0
//說 明：
/*(n0,k0,m)卷積碼的字母定義：
*n0——每個時刻編碼器輸出碼元個數
*k0——每個時刻編碼器輸入信息元個數
*m——輸入的信息組在編碼器中的存儲的單位時間
*N＝m+1——編碼約束度，編碼過程中相互約束的子碼個數
*df＝10——自由距離，由卷積碼的生成多項式決定
*維特比譯碼輸出信息元誤碼率算法
*Pme＝2^df * Pe^(df/2)——(Pe為信道的誤碼率)
*例：Pe＝10^-2，則Pme＝10^-7
*/

//---------------------------------------------------------------------------
#ifndef VITERBI_216_H
#define VITERBI_216_H

#define  G1  0x6d  //G1 = 1101101
#define  G2  0x4f  //G2 = 1001111

//---------------------------------------------------------------------------
class CViterbi_216
{
private:
  
protected:
  
public:
  int Decode_States;  //狀態數 2^m*k0
  int Branch_Num;    //從一個狀態延伸的分支數 n0
  int Path_Length;  //路徑保留長度 5*m < L < 10*m
  int Path_Num;    //保存幸存路徑個數
  int Init_Num;    //幸存路徑預裝載個數，Init_Num 的計算方法如下 2^Init_Num = Path_Num
  int First_Use;    //是否第一次處理緩存的標志

  //-----分支緩存定義-----
  //Branch_Tab[Decode_States][Branch_Num]
  //移位寄存器在各個狀態下輸入“0”或“1”對應的輸出結果表
  unsigned char Branch_Tab[64][2];

  //-----幸存路徑結構定義-----
  //同時也是距離寄存器和信息序列寄存器
  struct Survivor {
    int Sum_d;//幸存路徑的累積距離
    unsigned int H_m32;//幸存路徑的信息存儲變量，高32比特
    unsigned int L_m32;//幸存路徑的信息存儲變量，低32比特
  };
  Survivor Survivor_Save[64];
  //保存幸存路徑的結構緩存(結構緩存個數 = Path_Num)
  Survivor Survivor_Temp[128];
  //臨時幸存路徑的結構緩存(結構緩存個數 = Path_Num * Branch_Num)

public:
CViterbi_216();
  virtual ~CViterbi_216();
  void Initial(void);

  int Encode_216(unsigned char * InBuf, int InLength, unsigned char * OutBuf, int Now_State);
  //編碼正確返回編碼后移位寄存器的狀態；編碼出錯則返回0xff；
  int  Viterbi216(unsigned char * InBuf, int InLength, unsigned char * OutBuf, int Star_Mode);
  //Star_Mode 表示啟動該函數的方式，
  //Star_Mode ＝＝ 0 表示處理非連續卷積碼編碼數據
  //Star_Mode ＝＝ 1 表示處理連續卷積碼編碼數據
  
};
//---------------------------------------------------------------------------
#endif

//-----以下為函數部分-----
//---------------------------------------------------------------------------
CViterbi_216::CViterbi_216()
{
  Decode_States = 64;  //狀態數 2^m*k0
  Branch_Num = 2;    //從一個狀態延伸的分支數 n0
  Path_Length = 64;  //路徑保留長度 5*m < L < 10*m
  Path_Num = 32;    //保存幸存路徑個數
  First_Use = 1;
  
  Initial();
}
//---------------------------------------------------------------------------
CViterbi_216::~CViterbi_216()
{
  ;
}
//---------------------------------------------------------------------------
void CViterbi_216:nitial(void)
{
  unsigned char NowStates;
  int OneNum;
  int i, j;

  //狀態發生器：產生2^k0*m_個狀態和分支值
  for(i=0; i<Decode_States; i++){
    for(j=0; j<Branch_Num; j++){
      NowStates = (i<<1) | j;
      OneNum = WeightInt(NowStates & G1);
      Branch_Tab[i][j] = OneNum % 2;
      OneNum = WeightInt(NowStates & G2);
      Branch_Tab[i][j] = (Branch_Tab[i][j] << 1) | (OneNum % 2);
    }
  }
  Init_Num = 0;//幸存路徑預裝載個數，Init_Num 的計算方法如下 2^Init_Num = Path_Num
  i = Path_Num;
  while(i > 1){
    Init_Num++;
    i = i / 2;
  }
}
//---------------------------------------------------------------------------
int CViterbi_216::Viterbi216(unsigned char * InBuf, int InLength, unsigned char * OutBuf, int Star_Mode)
{