卷积码的viterbi算法.c

中卷积码就是一种较好的信道编码方式。这种编码方式同样是把k个信息比特编成n个比特

/* 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 
#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 {
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 *(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;xcm+=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{
for(j=0;j reg[j]=*(input+i+j); 
for (j=k;jreg[j]=*(currentstate+j-k); 
for(j=0;j{
for(x=0;xout[x]+=g[x][j]^reg[j];
}
for(x=0;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{
states.sum_cm=-65535;
for(j=0;j{
states.branchs[j].state_index=i< int_to_vector(j,states.branchs[j].input,k);
int_to_vector(i,cur_state,(K-1)*k);
con_encode(states.branchs[j].input,k,states.branchs[j].output,n ,cur_state);
}

for(j=0;jstates.survivor[j]=-1;
}
states[0].sum_cm=0.0;
//-----------------------------初始化完毕
//-----------------------------对每个接收的n维矢量循环
for (x=0;x{ 

for (i=0;irm=*(r+x+i);

for (i=0;i{
for (j=0;j{
for(y=0;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{
temp_sum_cm=temp_cm;
temp_input=states[j].branchs[y].input;
}
break;
}
}
}

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