求viterbi算法实例

jftaoh · 发表于 2005-10-19 23:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

求viterbi算法实例！

[ 本帖最后由 xinyuxf 于 2007-6-7 10:11 编辑 ]

NASA · 发表于 2005-10-20 08:20

不知道你说的算法实例是什么意思？是viterbi的应用程序？还是viterbi算法的源程序？ /* 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++) reg[j]=*(input+i+j); for (j=k;j<K*K;J++) 把当前状态放人移位寄存器 reg[j]=*(currentstate+j-k); for(j=0;j<K*K;J++) { 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.sum_cm=-65535; for(j=0;j<BRANCH_NUM;J++) { states.branchs[j].state_index=i<<K^J; 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;j<PATH_LENGTH;J++) states.survivor[j]=-1; } states[0].sum_cm=0.0; //-----------------------------初始化完毕 //-----------------------------对每个接收的n维矢量循环 for (x=0;x<RLENGTH { for (i=0;i<N;I++) 从接收序列中取出一个码子的长度 rm=*(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<TEMP_CM) { temp_sum_cm=temp_cm; temp_input=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.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<K;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; }

jftaoh · 发表于 2005-10-20 19:49

谢谢！

adminftp · 发表于 2005-10-20 20:58

孙健的博士论文中有一个命名实体识别的实例其识别过程用的就是viterbi算法，你可以找来看看

[此贴子已经被作者于2005-10-20 20:58:15编辑过]

tinie · 发表于 2006-4-20 23:37

上面的例子有些地方不太完整，看不太明白，恳请发送完整的源程序！不胜感激！！！！

账号		自动登录	找回密码
密码			我要加入

[经典算法] 求viterbi算法实例

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（jftaoh）求viterbi算法实例！！！！

先得谢谢你，最好是应用实例！

回复：（jftaoh）求viterbi算法实例！！！！

求卷积码的viterbi译码算法实例！！！！