《维特比译码》由会员分享,可在线阅读,更多相关《维特比译码(4页珍藏版)》请在金锄头文库上搜索。
1、维特比译码的介绍与仿真实现维特比译码是将接收到的序列和所有可能的发送序列作比较,选择其中汉明 距离最小的序列当作是现在的发送序列的一种算法。译码器从某个状态,例如从 状态出发,每次向右延伸一个分支,并与接收数字相应分支进行比较,计算它们之 间的距离,然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状 态的各条路径的距离累积值进行比较,保留距离值最小的一条路径,称为幸存路 径(当有两条以上取最小值时,可任取其中之一)。这种算法所保留的路径与接 收序列之间的似然概率为最大,所以又称为最大似然译码。所以,维特比译码的过程可以简单的理解为:接收端使用相同的网格图,从 同一状态开始猜测发送端可
2、能的编码序列,然后与接收到的码组比较,其中与接 收到的码组最近的猜测序列即使为译码序列,也就是码距最小的序列。白. 00 .yo141144000ni X 01L、00011 k OidGOno加101 101那么对应的网格图为上图所示。由网格图可见,沿路径每一级有4种状态a, b, c和d。每种状态只有两条 路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8条路径和接 收序列之间的汉明距离。比较到达每个状态的两条路径的汉明距离,将距离小的 一条路径保留,也就是幸存路径。这样,就剩下4 条路径了。继续考察接收序列 中的后继的比特,最后得出总的汉明距离最小的路径,也就是发送序列。假设现
3、在的发送信息位为 1101编码后的发送序列:111 110 010 100 001 011 000接收序列:111 010 010 110 001 011 000 (红色为错码)发送序列的约束长度为N = m + 1 = 3最后的幸存路径画出的网格图示于下图中,图中粗线路径是距汉明离最小等于 2)的路径。在上例中卷积码的约束长度为 N = 3,需要存储和计算 8 条路径的参量。由 此可见,维特比算法的复杂度随约束长度N按指数形式2N增长。故维特比算法 适合约束长度较小(N 10)的编码。卷积码的维特比译码是根据接收码字序列寻找编码时通过网格图最佳路径 的过程,找到最佳路径即完成了译码过程,并可
4、以纠正接收码字中的错误比特。 维特比译码算法步骤如下描述:1)根据接收码符号R,计算出相应的分支量度值BM(R/ Cj),j = 1、2;2)进入某一状态的2条分支量度BM (R/ Cj)与其前状态路径量度PM累加求和;3) 比较到达当前状态的 2 条新的路径量度 PM 的大小,选择最大者作为新 的状态路径量度存储起来,并保存与此路径对应的码字;4) 对所有的256个状态都实施上述加、比、选(ACS)运算;5) 在每一译码时刻,满足延时就从 256 条留存路径中,选择路径量度最大的一条路径作为译码数据输出;进入下一译码时刻,重复以上步骤,直至译码结束。维特比算法的复杂度随约束长度N按指数形式2
5、N增长。故维特比算法适合 约束长度较小(N 10)的编码。本文对维特比译码进行仿真,随机输入一组数,进行编码后输出,再进行维 特比译码,程序如下:clear alltemp=-3 -1 1 3;N=30;sent1=zeros(1,N+1);addgain=zeros(1,4);addgain1=zeros(1,4);result2=zeros(4,N);result2(:,1)=-3 -1 1 3;result1=zeros(4,N);yy0=-2.4 -0.8 0.8 2.4;yy=-0.6 -1.8 -3 -4.2;1 -0.2 -1.4 -2.6;2.6 1.4 0.2 -1;4.2
6、3 1.8 0.6;SNR_dB=100;sigma=10(-SNR_dB/20)*sqrt(5)()Z *X*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*info=ceil(rand(1,N)*4);sent=temp(info)sent1(1,2:end)=sent(1,1:end);()Z *X*x*x*x*x*x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x*x*x*x*x*x*x*x*x*x*x*for i=1:
7、Nii=i+1;y(i)=sent1(ii)*(0.8)+sent1(i)*(-0.6);endy;noise=randn(1,N)*sigma;y=y+noise;()Z *X*x*x*x*x*x*x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x*x*x*x*x*x*x*x*x*x*addgain=(yy0-y(l).2;()Z *X*x*x*x*x*x*x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x*
8、*x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x*x*x*x*x*x*x*x*x*x*for i=2:1:Nfor ii=1:4xx=addgain+(yy(ii,:)-y(i).2;minval,minnum=min(xx);xxx=minval-addgain(minnum);addgain1(ii)=addgain(minnum)+xxx;result1(ii,:)=result2(minnum,:); result1(ii,i)=temp(ii);endaddgain=addgain1;result2=result1;
9、endminval,minnum=min(addgain);receive=result2(minnum,:)仿真结果如下图所示:Command WindowQ) New to MATLAB? Watch this Vidl已6 see 立 or read GEttiw Started.sigma 二2.2361e-005sent =Columns 1 through 2131-13-1-3-3-31-311-3-3-1-31-3-31-3Columns 22 through 30-313-131-111receive =Columns 11 through 2131-13-1-3-3-31-311-3-3-1-31-3-31-3Columns 22 through 30-313-131-111可见输入一组序列译码后得到的输出序列与发送的一致。