卷积吗检纠错编码

PAGEPAGE22摘要卷积码是一种性能优越的信道编码，它的编码器和译码器都比较容易实现，同时它具有较强的纠错能力，随着纠错编码理论的研究不断深入，卷积码的实际应用越来越广泛。本文不仅对卷积码和卷积码的编译码有一个简单的介绍，而且对（212）卷积码进行了编码和译码，最后，通过MATLAB对（212）卷积码进行编译的仿真，对仿真结果进行了解释。关键字：卷积码、信道编码、卷积码编译码、MATLAB仿真

目录摘要 1一、引言 31.1发展历史及研究状况 31.2设计目的和意义 31.3设计方法 4二、卷积码编译码原理 52.1卷积码编码原理 52.2编码器 62.3卷积码译码原理 72.4VITEBI译码的关键步骤 82.4.1输入与同步单元 82.4.2支路量度计算 82.4.3路径量度的存储与更新 82.4.4信息序列的存储与更新 82.4.5判决与输出单元 8三、卷积码编码实现 93.1编码原理分析 93.2卷积码编码流程图 10四、卷积码译码实现 114.1译码编程思路 114.2卷积码译码流程图 11五、卷积码编译码程序的编译及仿真波形 125.1卷积码编码仿真 135.2卷积码译码仿真 135.3卷积码纠错码仿真 15六、总结 16七、参考文献 17附录 18一、引言1.1发展历史及研究状况1948年，Bell实验室的C.E.Shannon发表的《通信的数学理论》，是关于现代信息理论的奠基性论文，它的发表标志着信息与编码理论这一学科的创立。20世纪40年代，R.Hamming和M.Golay提出了第一个实用的差错控制编码方案，使编码理论这个应用数学分支的发展得到了极大的推动。分组码所存在的固有缺点可以通过采用其他的编码方法来改善，这种编码方法就是卷积码。卷积码是Elias等人在1955年提出的。卷积码与分组码的不同在于：它充分利用了各个信息块之间的相关性。通常卷积码记为(n，k，N)码。卷积码的编码过程是连续进行的，依次连续将每k个信息元输入编码器，得到n个码元，得到的码元中的检验元不仅与本码的信息元有关，还与以前时刻输入到编码器的信息元(反映在编码寄存器的内容上)有关。同样，在卷积码的译码过程中，不仅要从本码中提取译码信息，还要充分利用以前和以后时刻收到的码组．从这些码组中提取译码相关信息，而且译码也是可以连续进行的，这样可以保证卷积码的译码延时相对比较小。通常，在系统条件相同的条件下，在达到相同译码性能时，卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小，相应译码复杂性也小一些。卷积码的译码通常有如下几个比较流行的译码算法：由Wozencraft和Reiffen在1961年提出，Fano和Jelinek分别在1963年和1969年进行改进了的序贯译码算法。该算法是基于码字树图结构的一种次最优概率译码算法。由Massey在1963年提出的门限译码算法。这个算法利用码字的代数结构进行代数译码。由Viterbi在1967年提出的Viterbi算法是基于码字格图结构的一种最大似然译码算法，是一种最优译码算法。在Viterbi译码算法提出之后，卷积码在通信系统中得到了极为广泛的应用。如GSM、3G、商业卫星通信系统等。1.2设计目的和意义因为信道中信号不可避免会受到干扰而出错。为实现可靠性通信，主要有两种途径:一种是增加发送信号的功率，提高接收端的信号噪声比;另一种是采用编码的方法对信道差错进行控制。前者常常受条件限制，不是所有情况都能采用。而编码理论可以解决这个问题，使得成本降低，实用性增强。随着现代通信的发展，卷积码以其高速性和可靠性在实际应用中越来越广泛。1967年Viterbi译码算法的提出，使卷积码成为信道编码中最重要的编码方式之一。在卷积码中，因为Viterbi算法效率高，速度快，结构相对简单等特点，被广泛应用于各种数据传输系统。特别是深空通信、卫星通信系统中。因此采用Viterbi译码算法具有非常现实的意义。1.3设计方法本文在分析卷积码编译码器原理的基础上，通过基于MATLAB对卷积编码，解码进行仿真。通过仿真可以更清楚的认识到卷积码的编码，解码的各个环节，并对仿真结果进行了分析。得出卷积码Viterbi译码的误比特性能和回溯长度，码率，约束长度的关系。

二、卷积码编译码原理2.1卷积码编码原理2.1.1卷积码简介积码，又称连环码，是由伊莱亚斯于1955年提出来的一种非分组码。若以（n,k,m）来描述卷积码，其中k为每次输入到卷积编码器的bit数，n为每个k元组码字对应的卷积码输出n元组码字，m为编码存储度，也就是卷积编码器的k元组的级数，称m+1=K为编码约束度m称为约束长度。卷积码将k元组输入码元编成n元组输出码元，但k和n通常很小，特别适合以串行形式进行传输，时延小。与分组码不同，卷积码编码生成的n元组不仅与当前输入的k元组有关，还与前面m-1个输入的k元组有关，编码过程中互相关联的码元个数为n*m。卷积码的纠错性能随m的增加而增大，而差错率随N的增加而指数下降。在编码器复杂性相同的情况下，卷积码的性能优于分组码。卷积码编码的当前输出v(l)不仅与当前输入消息u(l)相关，还与此去前输入的m个消息u(l-1),…,u(l-m)相关，即v(l)=f(u(l),u(l-1),…,u(l-m)),l=0,1,2…卷积编码电路中移位寄存器初态可设定为全0，电路为按段工作方式，即对每段k比特输出入，产生一段n比特输出。任意一输入段u(l-h)与输出v(l)的关系都是一个特殊的线性分组码的编码关系，即存在k*n的二元矩阵,使得,h=0,1,2,…,m因此对于消息段序列u=(u(0),u(1),…，u(m),u(m+1),…),相应的输出端序列为v=(v(0),v(1),…,v(m)，v(m+1),…),并满足卷积编码电路在按段工作方式下只需存储或者记忆m段的消息输入，电路中输入移位寄存器最多只有个有效的寄存器单元，而输出移位寄存器仅起一个并串转换作用。因此称参量m为卷积码的记忆长度（段）。二元（n，k，m）卷积码共有个不同的状态，记为当状态为（或）时,输入段（或u）产生编码输出端（或v）并使该状态改变（或称为转移）到新的状态(或)。到的转移过程称为一个转移分支，记为（，）或（，）并标记转移过程为或v/u。以状态为结点，转移分支为有向边描述卷积码的所有不同状态转移的有向图，称为卷积码的状态转移图。2.2编码器2．2.1编码器的一般结构卷积码的编码器一般都比较简单。图2-1是一般情况下的卷积码编码器框图。它包括NK级的输入移位器，一组n个模2和加法器和n级的输出移位寄存器[6]。对应于每段k比特的输入序列，输出n个比特。由图可知，n个输出比特不但与当前的k个输入比特有关，而且与以前的(N-1)k个输入信息比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器和模2加法器的连接方式所决定的另一个序列的卷积，卷积码由此得名。本文采用的是冲击响应描述法编码思想。2.2．2编码器的参数⑴有k个输入信息端，n个输出端（k<n）,K-1节移位寄存器（共需k(K-1)个寄存器单元），称做（n,k,K）卷积码。⑵通常称K为约束长度（一般来说，约束长度越大，则码字纠错性能越好）。⑶码的效率：k/n⑷编码前，k(K-1)个寄存器单元全部复位清零。⑸由于一段消息不仅影响当前段的编码输出，还影响其后m段的编码输出，所以称参量为卷积吗的约束比特长度为注意进入卷积编码器的最后m段消息仍是要编码输出的消息，对这最后m段消息的编码处理，称作卷积编码的结尾处理。一种常见的结尾处理方法是额外输入m段无效的0数据比特，一方面将存储的m段消息编码全部推出，另一方面保证编码器回到全0的初态。2.3卷积码译码原理维特比算法的基本思想是把接收到的矢量，和网格图上诸种可能的路径比较，删去距离大的路径，保留距离小的路径，以距离最小路径作为发码的估值。它的原理是将接收到的信号序列,选择其中汉明距离最小的序列作为现在的发送信号序列。为简便,讨论(n,k,N)卷积码当k=1的情形,从全0。由卷积码网格图的前N-1,即最初的2N-r条路径各不相同;当到达第N级时,每条路径都有2N-1N级上;而第N级上的每2条支路又都汇聚在一个节点上。第N级以后的网格图图形完全是重复第N级的图形。在维特比算法中,把汇聚在每个节点上的2条路径的对数似然函数累加值进行比较;然后把具有较大对数似然函数累加值的路径保存下来,称此部分路径为幸存路径,而丢弃另一条路径;经挑选后,第N级只留下2N-r条幸存路径,选出的路径连同它们的对数似然函数累加值一起被存储起来。因每个节点引出2N-1条支路,因此以后各级中路径的延伸都增大一倍;但比较它们的似然函数累加值后,丢弃一半,结果留存下来的路径总数保持常数(等于其状态数)。由此可见,上述译码过程中的基本操作是“加→比→选”。即每级求出对数似然函数累加值,然后两两比较并做出选择。有时会出现2条路径的对数似然函数累加值相等的情形,此时可任意选择其中一条作为“幸存路径”。每一级都有条幸存路径,则当序列发送完毕后，为判断其最后结果,通常要在网格图的终结处加上一些结束信息。通常结束信息为N-1个已知信息,当然结束信息大于N-1也可以。在此信息到来时,因每一个状态只有与已知发送信息相符的那条支路被延伸,因而在每级比较后,幸存路径减少一半。因此,在接收到N-1个已知信息后,整个网格图中只有惟一的一条幸存路径保留下来。这就是译码所得到的路径,这条译码路径和发送序列是最相似的。从上述卷积码的译码过程可以看出:约束长度为N时,需要存储和计算条路径的参量。由此可见,维特比算法的复杂度随约束长度N按指数形式增长2N。故维特比算法适合约束长度较小(N≤10)的编码。当编码约束度不太大(≤10)或者误码率要求不太高(>)时,它的设备比较简单,用硬件译码计算速度快。Viterbi译码的缺点是随着约束长度的增加算法的复杂度增加很快。约束长度N为7时要比较的路径就有64条，为8时路径变为128条。(2<<(N-1))。所以Viterbi译码一般应用在约束长度小于10的场合中。2.4VITEBI译码的关键步骤2.4.1输入与同步单元输入同步单元为译码器提供正确的支路同步，每次正确地输出属于一条支路的n个比特。显然，当支路定时失步时，译码过程中将会出现大量的差错，只要能检测出这种状态，即能有效地调整支路同步。一种方法是监视路径量度的增长率；另一种方法是检查网格图的路径合并性质。当译码器出现失步时，网格图中幸存路径合并的速率比同步时慢得多[2]。2.4.2支路量度计算每当接收到一条新支路的一组n个量度值(硬判决时为n比特)，支路量度计算单元就对网格图中每一条不同的支路确定一新的量度值。对R=k/n码来说，每次将有2个不同的量度值。在软判决Viterbi译码时，支路量度值不但随支路不同而异，而且还与接收信号的量化值有关[2]。2.4.3路径量度的存储与更新在此单元中，支路量度与以前所存储的路径量度相加，然后对汇聚到同一节点处的支路进行路径量度比较，选择一条路径量度最小的路径保留下来。2.4.4信息序列的存储与更新一种最佳的也是最常用的方法是基于最大似然译码。对于R=1/n卷积码而言，每接收一组新的支路信息，在各个状态的路径存储器中存入经“加一比一选”电路选出的一位假想信息比特，同时将最先存入路径存储器的一位比特输出给判决单元。因此，每接收到一条新支路，路径存储器就更新一次它所存储的假想信息序列。2.4.5判决与输出单元在R=1/n卷积码最佳译码时，应选择具有最小路径量度的假想信息序列中最早存入的一个比特做译码输出。三、卷积码编码实现3.1编码原理分析以(2，1，2)卷积码为例，其生成多项式为：G=QUOTE(3-1)QUOTE状态转移方程为：(3-2)下面以图3.1的编码器所编出的码为例，来说明卷积码编码的方法和过程。为了使过程更加清晰，这里给出该码的状态图，如图3.2所示。图3.1（2,1,2）卷积码编码器图3.2（2,1,2）卷积码状态转移图由上面状态转移图得到状态转移的4个状态，每一个状态的转移都与当前输入消息的状态有关。而每一个对应的输出不仅与当前输入的m个消息有关，还与此前输入的相关，即根据该码的状态转移图可以列出其状态转移表，如表3.1所示。表3.1（2,1,2）卷积码状态转移表u()()()()()()()()(00)(01)(10)(11)0(00)(00)(10)(11)(00)(10)(10)(01)1(01)(11)(11)(00)(01)(01)(11)(10)3.2卷积码编码原理卷积码译码流程图如下，首先输入n位信息序列，然后根据前两位的输入信息及当前信息计算输出序列，输出2n位信息编码。流程图（3.3）开始开始输入n位信息序列依据前两位输入信息及当前信息计算输出序列输出2n位信息编码结束

四、卷积码译码实现4.1译码编程思路译码总体上是先通过“加-比-选”来得到最优路径，然后根据状态转移图来得到解码后的码字。在整个过程中需要记录的是到达各个状态的累计最小汉明距离及路径。用D(i)=hamming_distance(W(i,:),word(1:chip*2))实现与出错码字对比得到汉明距，用[val,index]=sort(D)来实现val中存汉明距从小到大排列，index中存对应val数据所在位置。首先初始化选前n时刻来比较汉明距，选出最小的4~8条路径，而后每条被选出的路径每次加一时刻进行迭代运算，选出新的汉明距最小的4~8条路径，依次循环，直至迭代至码组结束。最后选出4~8条路径中最小的一条来进行译码。开始输入2m位编码序列计算到达各个状态的累计最小汉明距离及路径开始输入2m位编码序列计算到达各个状态的累计最小汉明距离及路径初始化前n时刻比较汉明距选出最小的6条路径迭代至码组结束？加一时刻迭代运算选出汉明距最小的一条路径进行译码结束

上图所示的是卷积码的译码流程图，卷积码译码原理开始的时候,是首先输入2m的编码序列，然后计算到达各个状态的累计最小汉明距离及其路径，然后初始化前n时刻，计较汉明距离。选出最小的6条路径，迭代至码组结束，选出汉明距离最小的一条路径进行译码，译码结束，若在迭代至码组结束时判断没有结束，则加一时刻的迭代运算，在初始化前n时刻比较汉明距离之后继续执行，知道迭代至码组结束。

五、卷积码编译码程序的编译及仿真波形5.1卷积码编码仿真请输入信息码序列：[1011101]msg=1011101word=11110100100101图5.1卷积码编码原理图5.2卷积码译码仿真请输入收到的编码：[11110100100101]word=11110100100101信息编码无错误msg=1011101图5.2卷积码译码原理5.3卷积码纠错码仿真请输入收到的编码：[11110100000101]word=11110100000101错误出现在第9位wordr=11110100100101msg=1011101图5.3卷积码纠错原理图

六、总结这次课程设计，对我的意义很大，让我的学习能力和动手能力都有所增加，在这次的课程设计中，让我对卷积码的编码和译码都有了一个比较深入的了解，对编译码用MATLAB进行仿真，让我对MATLAB的应用能力有了一个更深入的掌握，我想这对我以后的工作会有一个很大帮助。总体对卷积码的编码与译码，以及译码之后的错误纠正，让我对通信系统的总体原理也有一定的了解，也让我对信道的传输明白了其中的道理，明白了信息在信道中传输的原理。通过课程设计，让我知道了许多的生活道理，在刚刚收到老师发给我们的题目之后，感觉很是简单，但在真正的着手开始做的时候，才发现问题很多，而最重要的问题是在程序编译中，还有其中的原理有许多的地方不明白，对很多的名词不知道什么意思，之后，通过在图书馆借书，上网查资料，在课堂上问老师，和团队的同学进行讨论等等，我的问题终于一点点的解决，程序也一点点的编译了出来，仿真图像也很好的显示出来。这让我明白了几个道理，首先，我们不能小看一件小事情，所有的大事情都是在一件件的小事上建立起来的。其二，那些看是简单的事情，当我们真正开始做的时候，就会发现不是轻而易举就可以完成的，告诉我们更重要的是注重我们的动手能力。其三，我们都知道的是众人拾柴火焰高的道理，这次，让我更加的明白了它的含义，尤其是在这个竞争异常激烈的今天，我们更应该注重团队的力量，一个人单枪匹马，最终会被社会淘汰，而只有那些懂得团队的人才能立足。总之，这次课程设计对我的意义很大，不仅让我的知识增加了不少，同时也让我懂得了许多的道理，可谓是受益匪浅。最后，非常感谢郑玉峰老师的帮助，让我顺利的完成了这次课程设计。

七、参考文献[1].李建新.现代通信系统分析与仿真-MATLAB通信工具箱.西安：西安电子科技大学出版社，2000.[2].樊昌信.通信原理.北京：国防工业出版社,2002.[3].刘敏.MATLAB通信仿真与应用.北京：国防工业出版社.[4].曹志刚等著.现代通信原理.北京：清华大学出版社，2001.[5].吴伟陵等著.移动通信原理.北京：电子工业出版社，2005.[6]RodgerE.Ziemer，RogerL.Peterson著.尹长川，郝建军，罗涛等译.数字通信基础(IntroductiontoDigitalCommunication).原书第2版.北京：机械工业出版社，2005.1[7]邓华.Matlab通信仿真及应用实例详解.北京：人民邮电出版社，2003.9[8]陈国通.数字通信.哈尔滨：哈尔滨工业大学出版社，2002.4[9]孙祥Matlab7.0基础教程.北京：清华大学出版社，2005.5附录：decode.mclear;clc;word=input('请输入收到的编码：');wordmsg=decode_conv212(word);wordr=encode_conv212(msg);c=1;fori=1:1:length(word)ifword(i)~=wordr(i)c=0;s=i;endendifc==0fprintf('错误出现在第%1.0f位\n',s);wordrelsefprintf('信息编码无错误');endmsga=length(msg);x=.01:.01:a;[m,n]=size([msg]'*ones(1,100));y=reshape(([msg]'*ones(1,100))',1,m*n);subplot(2,1,2)plot(x,y)title('信息码序列')xlabel('t')ylabel('msg')axis([0length(msg)-0.51.5])b=length(word);x=.01:.01:b;[m,n]=size([word]'*ones(1,100));y=reshape(([word]'*ones(1,100))',1,m*n);subplot(2,1,1)plot(x,y)holdonifc==0z=reshape(([wordr]'*ones(1,100))',1,m*n);plot(x,z,'--r')endtitle('编码序列')xlabel('t')ylabel('word')axis([0length(word)-0.51.5])decode_conv212.mfunctionmsg=decode_conv212(word)chip=5;fori=1:2^chipM(i,:)=de2bi(i-1,chip);W(i,:)=encode_conv212(M(i,:));D(i)=hamming_distance(W(i,:),word(1:chip*2));end[val,index]=sort(D);ret_msg=zeros(1,length(word)/2);fori=1:6ret_msg(i,1:chip)=M(index(i),:);ret_dis(i)=D(index(i));enditer=(length(word)-chip*2)/2;fori=1:iterforj=1:6msg_temp1=[ret_msg(j,1:chip+i-1)0];msg_temp2=[ret_msg(j,1:chip+i-1)1];word_temp1=encode_conv212(msg_temp1);word_temp2=encode_conv212(msg_temp2);dis_temp1=hamming_distance(word_temp1,word(1:chip*2+2*i));dis_temp2=hamming_distance(word_temp2,word(1:chip*2+2*i));if(dis_temp1<dis_temp2)ret_msg(j,1:chip+i)