循环码的编译码方法.doc

*实践教学*兰州理工大学计算机与通信学院2013年秋季学期计算机通信课程设计题 目：(15,7)循环码的编译码方法专业班级： 通信工程一班 姓 名： 学 号： 指导教师： 成 绩： 摘要本次课程设计研究的是（15,7）循环码的编译码方法，在设计过程中，首先要介绍了线性分组码的编码和译码原理，并介绍了循环码的定义及其相关内容；其次由给定的生成多项式求解出了生成矩阵和监督矩阵，并且利用MATLAB编写循环码的编码器和译码器代，实现编码及译码功能；求出该码的最小码距，并分析讨论该码的纠错能力以及在高斯信道下的误码性能。关键词: 循环码；编码；译码；MATLAB目录一 前言1二 循环码编译码的基本原理22.1循环码的简介22.1.1循环码的定义22.1.2线性分组码与循环码的区别32.1.3循环码的最小码距32.1.4循环码的检纠错能力32.2 循环码编译码原理及过程42.2.1循环码的编译码原理42.2.2 循环码编译码的5三 系统分析73.1 循环码编译码方法的实现框图73.2 循环码编译码实现过程8四 系统设计104.1生成矩阵和监督矩阵104.2循环码的编码104.3循环码的的译码114.4循环码在高斯信道下的误码性能13总结14参考文献15附录16致谢23一 前言随着社会经济的迅速发展和科学技术的全面进步，计算机事业的飞速发展，以计算机与通信技术为基础的信息系统正处于蓬勃发展的时期。随着经济文化水平的显著提高，人们对生活质量及数据通信的要求也越来越高。数字信号在传输中往往由于各种原因，会使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。通过信道编码这一环节，对数码流进行相应的处理，使通信系统具有一定的纠错能力和抗干扰能力，可以极大地避免码流传送中误码的发生。信道编码的本质是增加通信的可靠性。误码的处理技术有纠错、交织、线性内插等。提高数据传输速率，降低误码率是信道编码的任务。在计算机通信信息码中循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有许多特殊的代数性质，它使计算机通信以一种以数据通信形式出现，实现了在计算机与计算机之间或计算机与终端设备之间进行有效的与正确地信息传递，它使得现代通信的可靠性与有效性实现了质的飞跃。它是现代计算机技术与通信技术飞速发展的产物，在日常生活通信领域、武器控制系统等领域都被广泛应用。此次设计中的仿真分析采用了MATLABLE，它是美国Mathworks公司推出的一套高性能的数值分析和计算软件。MATLABLE仿真分析平台提供了良好的可视化开发环境，被广泛的应用于信号和图像处理、通信、控制系统设计、测试和测量等众多领域。二 循环码编译码的基本原理2.1循环码的简介更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。它是线性分组码的一种，所以它具有线性分组码的一般特性，此外还具有循环性。循环码的编码和解码设备都不太复杂，检、纠错能力强，而且性能好。它不但可以检测随机的错误，还可以检测突发的错误。循环码可以检测长为或更短的任何突发错误，包括首尾相接突发错误。循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图中的邻接条件，即相邻两个数码之间只有一位码元不同（码元就是组成数码的单元）。循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循环码又称格雷码（Gray Code）。2.1.1循环码的定义设C是某线性分组码的码字集合，如果对任何，它的循环移位也属于C，则称该码为循环码。该码在结构上有另外的限制，即一个码字任意循环移位后的结果仍是一个有效码字。其特点是：可以用反馈移位寄存器很容易实现编码和伴随式的计算；由于循环码有很多固有的代数结构，从而可以找到各种简单使用的译码办法。如果一个线性码具有以下的属性，则称为循环码：如果n元组是子空间S的一个码字，则经过循环移位之后得到的也同样是子空间S中的一个码字；或者，一般来说，经过j次循环移位之后得到的也是子空间S中的一个码字。2.1.2线性分组码与循环码的区别线性分组码是同时具有分组特性（码字和消息长度恒定）和线性特性（消息相加后的编码等于各自编码后相加）的纠错码。每个监督码元都是码组中某些信息码元的线性相加得到的。将q元符号按每k个分为一组然后通过编码得到n-k个q元符号作为冗余校验符号，最后由校验符号和信息符号组成有n个q元符号的码字符号。得到的码字可以纠正t个错误，编码效率为k/n。两个属于该码的码字之和仍是一个属于该码的码字，全零码字总是一个码字，一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量。循环码是采用循环移位特性界定的一类线性分组码。是线性分组码的一个重要子类；BCH码是其主要的一大类；汉明码、R-M码、RS码等可变换；纳入循环码内，Goppa码的一个子类也属于循环码；用反馈线性移位寄存器可容易的实现其编码和得到伴随式；由于数学上的特性，译码方法简单。循环码的特点有两点：一是封闭性（如果c1，c2，是与消息m1，m2对应的码字，则c1+c2必定是与m1+m2对应的码字）；二是循环性（任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组）。2.1.3循环码的最小码距对于分组码一般用符号（n，k）表示，其中n是码组的总位数，又称为码组的长度即码长，k是码组中信息码元的数目，nk为码组中的监督码元数目，用字母r表示。分组码（n，k）当信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。在分组码中，把码组中“1”的个数目称为码组的重量，简称码重。编码中所有码字重量的集合形成该码的重量分布。如果全部M个码字都具有相同的重量，这种码叫做固定重量码，或叫恒重码。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距，码距又称汉明距离。一般而言，对于任意一种编码，其中各个码组之间的距离不一定相等。这时，将其中最小的距离称为最小码距，用dmin来表示。2.1.4循环码的检纠错能力一种编码的纠错，检错能力决定于最小码距dmin的值。下面将用几何关系证明纠错，检错能力和最小码距的关系。为了能检测e个错码，要求最小码距： (2-1)纠正t个错误，要求最小码距 (2-2)为纠正t个错码，同时检测e个错码，则要求最小码距 (2-3)本课程设计中采用（15,7）循环码由生成矩阵可得其最小码距dmin为5，由最小码距可以出其纠检错能力，其最多可检4位错，可纠2位错。2.2 循环码编译码原理及过程循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统的构造这类码，且易于实现，所以循环码受到人类的高度重视，在前向纠错系统（FEC）中得到了广泛的应用。2.2.1循环码的编译码原理循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组，也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。循环码的生成多项式写为,它是循环码码集中唯一的，幂次为的码多项式，则是一个幂次为的码多项式。按模运算，此时：（2-4）即，且因也是次幂，故。由于它是循环码，故按模运算后的“余式”也是循环码的一个码字，它必能被整除，即：（2-5）由以上两式可以得到：（2-6）（2-7）从上式中可以看出，生成多项式应该是的一个因式，即循环码多项式应该是的一个次因式。由生成多项式可以得出相应的典型生成矩阵及标准监督矩阵：（2-8）（2-9）例如已知（7，4）循环码的生成多项式和校验多项式分别为：，。写得其生成矩阵和校验矩阵分别为：（2-10） （2-11）2.2.2 循环码编译码的循环码的编译码过程如下：（1）编码过程第一步：将信息码字表示为，其最高次幂为；第二步：将与求模得出相应的余式；第三步：编码结果为。（2）译码过程第一步：由接收码字与监督矩阵相乘得出错误图样；第二步：判断是否为零。若不为零，则出错。在假定至多只有一位错的情况下，可以有效地译出相应的信息码字。第三步：在出错的情况下，将与标准监督矩阵对比，得出错误的比特位并进行更正得出前四位为信息码字。三 系统分析3.1 循环码编译码方法的实现框图是采用循环移位特性界定的一类线性分组码。是线性分组码的一个重要子类。循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现。循环码编译码方法的实现框图如图3-1所示：由生成多项式得到生成矩阵及监督矩阵根据g(x)和h(x)求出余式r(x)输入信息序列编码求出伴随式及错误图样译码调试及仿真分析图3-1 循环码编译码实现框图3.2 循环码编译码实现过程循环码的编码和解码设备都不太复杂，检、纠错能力强，而且性能好。它不但可以检测随机的错误，还可以检测突发的错误。（n,k）循环码可以检测长为n-k或更短的任何突发错误，包括首尾相接突发错误。循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组，也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。首先根据给定的(n,k)值以及给定的生成多项式g(x)，求出生成矩阵以及监督矩阵。利用MATLAB软件编写循环码的编码器以及译码器，根据要求输入消息序列，从仿真图形中观察分析编译码是否正确，讨论循环码的纠检错能力及高斯信道下的误码性能。（1）循环码编码实现流程如图3-2所示输入消息m（x）如1 1 1 0 0 0 1确定余式r(x): 确定c(x): 输出码字C（x）开 始结 束图3-2循环码编码流程图（2）循环码译码实现流程如图3-3所示：由接收信号r确定伴随式s：s=r*h S是否为0由S确定错误图样e纠错输出码字c是否结 束开 始图3-3循环码译码流程图（3）循环码误码性能实现框图如图3-4所示：信号源（15,7）循环码编码（15,7）循环码译码误码分析加入不 同 信 噪比 的 高斯 白 噪声图3-4循环码误码性能实现框图图四 系统设计4.1生成矩阵和监督矩阵已知（15,7）循环码的生成多项式为g(x)=x8+x7+x6+x4+1,由其生成多项式求出其生成矩阵G(X)为：由于h(x)g(x)=xn+1，求出的h(x)=x7+x6+x4+1,进而得到监督矩阵H(X)为：H=4.2循环码的编码encode函数功能：编码函数语法：code=encode(msg,N,K,method,opt)说明：用method指定的方法完成纠错编码。其中msg代表信息码元，是一个K列矩阵，N是编码后的码字长度；K是信息位的长度；opt是有些编码方式需要的参数。运行编码程序，在工作窗口内按照文字提示输入消息序列,本次设计中需要输入的消息序列是一串长为7为的二进制码字。运行结果如图4-1所示：图4-1循环码的编码从图中可以看出，当输入消息序列为：1110001时，编码结果为：01110111111000。输入信号经过编码，增加了校验位，使信号变得复杂，提高了通信的可靠性。4.3循环码的的译码decode函数功能：译码函数语法：msg=decode（code，N，K，method，opt1,opt2,opt3,opt4）； 说明：这个函数对接收到的码字进行译码，恢复出原始的信息，译码参数和方式必须和编码时采用的严格相同。它对接收到的码字，按method指定的方式进行译码；opt1，opt4是可选项的参数。（1）使用编出的码字去执行译码程序，译码结果如图4-2所示：图4-2 循环码的译码由上图可以看出，用编出的码字去执行译码程序，译出的码字为：1110001，与输入的码字完全一致，没有发现错误。验证了译码程序的正确性。（2）将4-1中编出的码字改变一位作为译码程序的输入，译码程序输出中如图4-3所示：图4-3循环码的检纠错将编码输出序列中的第二位由1变为0，然后运行译码程序，从图4-3中可以看出是第二位发生错误，但可以看出译码输出仍为1110001，与输入码字一致，可见，此程序可以纠一位错。4.4循环码在高斯信道下的误码性能图4-4信源序列编译码输出图形 图4-5循环码在不同信噪比下的误码率总结本次课程设计的题目是（15,7）循环换码的编译码方法。使用的仿真工具是MATLAB。在做之前，我搜集了大量循环码的相关资料，知道了循环码的定义、循环码的编译码原理以及过程、码距、检纠错能力、与线性分组码的区别及联系等知识。这其中有我以前学习过的，还有新接触到的知识，在回顾掌握的同时又学习到了新的东西，令设计不再枯燥乏味。首先根据任务书中给定的(n,k)值以及给定的生成多项式g(x)，所有多项式T(x)都能被g(x)整除。根据这条原则可以对给定的信息位进行编码。设m(x)为信息码多项式，其次数小于k。用xn-k 乘m(x)，得到的xn-k m(x)次数必定小于n。用g(x)除xn-k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n-k)。将此余式r(x)加在信息位后作为监督为，即将r(x)和xn-k m(x)相加，得到的多项式必定是一个码多项式。循环码的译码可按以下三个步骤进行：1.接收到的y(x)计算伴随式式s(x)；2.根据伴随式s(x)找到对应的估值错误图样(x)；3.计算=y(x)+(x),得到估值码字(x)。若(x)=c(x),则译码正确，否则，若(x)c(x),则译码错误。通过对线性分组码中的循环码的编译码编程实现，了解到线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r的码字，用(n，k)表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的。循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。参考文献1陈运主编.信息论与编码. 电子工业出版社2孙丽华主编.信息论与纠错编码. 电子工业出版社3李勇、徐震，MATLAB辅助现代工程数字信号处理，西安电子科技大学出版社4刘树棠译.数字信号处理使用MATLAB.西安:西安交通大学出版社5罗军辉等编著.MATLAB7.0在数字信号处理中的应用.北京：机械工业出版社附录%3（15,7）循环码的编码的程序：clear;clc;a=input(请输入消息矢量：);%高次项系数在前的生成多项式Gx=1 1 1 0 1 0 0 0 1;%将数组a的高位依次放在数组Data的低位 Data=zeros(1,15); Data(1)=a(7); Data(2)=a(6); Data(3)=a(5); Data(4)=a(4); Data(5)=a(3); Data(6)=a(2); Data(7)=a(1); %Data除以Gx得到余数Rx Qx,Rx=deconv(Data,Gx); b=Rx+Data; %将数组b的高位放在后面 c=b(1); b(1)=b(15); b(15)=c; c=b(2); b(2)=b(14); b(14)=c; c=b(3); b(3)=b(13); b(13)=c; c=b(4); b(4)=b(12); b(12)=c; c=b(5); b(5)=b(11); b(11)=c; c=b(6); b(6)=b(10); b(10)=c; c=b(7); b(7)=b(9); b(9)=c; %将数组b校正 for i=1:15 if rem(abs(b(i),2)=0 b(i)=0;end endfor i=1:15 if rem(abs(b(i),2)=1 b(i)=1;endenddisp(输入序列：);adisp(编码输出序列：);%4相对应的译码和纠错程序：clear;clc;r=0 1 1 1 0 1 1 1 1 1 1 0 0 0 1;h=1,0,0,0,0,0,0,0;1,1,0,0,0,0,0,0;0,1,1,0,0,0,0,0;1,0,1,1,0,0,0,0;0,1,0,1,1,0,0,0;0,0,1,0,1,1,0,0;0,0,0,1,0,1,1,0;1,0,0,0,1,0,1,1;0,1,0,0,0,1,0,1;0,0,1,0,0,0,1,0;0,0,0,1,0,0,0,1;0,0,0,0,1,0,0,0;0,0,0,0,0,1,0,0;0,0,0,0,0,0,1,0;0,0,0,0,0,0,0,1;b=flipud(h);s=r*b;for i=1:8 if rem(abs(s(i),2)=0 s(i)=0;end endfor i=1:8 if rem(abs(s(i),2)=1 s(i)=1;endend if s=0 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; elseif s=1 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 1; elseif s=1,1,0,0,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; elseif s=0,1,1,0,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 1 0 0; elseif s=1,0,1,1,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 1 0 0 0; elseif s=0,1,0,1,1,0,0,0 e=0 0 0 0 0 0 0 0 0 0 1 0 0 0 0; elseif s=0,0,1,0,1,1,0,0 e=0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; elseif s=0,0,0,1,0,1,1,0 e=0 0 0 0 0 0 0 0 1 0 0 0 0 0 0; elseif s=1,0,0,0,1,0,1,1 e=0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; elseif s=0,1,0,0,0,1,0,1 e=0 0 0 0 0 0 1 0 0 0 0 0 0 0 0; elseif s=0,0,1,0,0,0,1,0 e=0 0 0 0 0 1 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,1,0,0,0,1 e=0 0 0 0 1 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,1,0,0,0 e=0 0 0 1 0 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,0,1,0,0 e=0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; elseif s=0,0,0,0,0,0,1,0 e=0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; else s=0,0,0,0,0,0,0,1 e=1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; endu=r+e;for i=1:15 if rem(abs(u(i),2)=0 u(i)=0;end endfor i=1:15 if rem(abs(u(i),2)=1 u(i)=1;endendData=zeros(1,7); Data(1)=u(9); Data(2)=u(10); Data(3)=u(11); Data(4)=u(12); Data(5)=u(13); Data(6)=u(14); Data(7)=u(15);if e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 disp(没有错误：) k=0,else disp(第几位错误：) k=find(e) enddisp(接收码字)r disp(译码输出序列：)Data%4将编码输出改错一位之后，验证程序的纠错能力clear;clc;r=0 0 1 1 0 1 1 1 1 1 1 0 0 0 1;h=1,0,0,0,0,0,0,0;1,1,0,0,0,0,0,0;0,1,1,0,0,0,0,0;1,0,1,1,0,0,0,0;0,1,0,1,1,0,0,0;0,0,1,0,1,1,0,0;0,0,0,1,0,1,1,0;1,0,0,0,1,0,1,1;0,1,0,0,0,1,0,1;0,0,1,0,0,0,1,0;0,0,0,1,0,0,0,1;0,0,0,0,1,0,0,0;0,0,0,0,0,1,0,0;0,0,0,0,0,0,1,0;0,0,0,0,0,0,0,1;b=flipud(h);s=r*b;for i=1:8 if rem(abs(s(i),2)=0 s(i)=0;end endfor i=1:8 if rem(abs(s(i),2)=1 s(i)=1;endend if s=0 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; elseif s=1 0 0 0 0 0 0 0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 0 1; elseif s=1,1,0,0,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; elseif s=0,1,1,0,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 0 1 0 0; elseif s=1,0,1,1,0,0,0,0 e=0 0 0 0 0 0 0 0 0 0 0 1 0 0 0; elseif s=0,1,0,1,1,0,0,0 e=0 0 0 0 0 0 0 0 0 0 1 0 0 0 0; elseif s=0,0,1,0,1,1,0,0 e=0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; elseif s=0,0,0,1,0,1,1,0 e=0 0 0 0 0 0 0 0 1 0 0 0 0 0 0; elseif s=1,0,0,0,1,0,1,1 e=0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; elseif s=0,1,0,0,0,1,0,1 e=0 0 0 0 0 0 1 0 0 0 0 0 0 0 0; elseif s=0,0,1,0,0,0,1,0 e=0 0 0 0 0 1 0 0 0 0 0 0 0 0 0; els