线性分组码纠错能力的分析.doc

课程设计摘 要近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。目前，几乎所有得到实际应用的纠错码都是线性的。线性分组码的应用上越来越广泛，首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。再编制MATLAB程序对其纠错能力进行仿真。关键词： 纠错；线性分组码；MATLAB2目 录1 课题描述12设计原理12.1 线性分组码的基本原理12.2 线性分组码编码过程23设计过程53.1设计思路53.2设计内容6总 结8参考文献91 课题描述数字通信最主要的优点之一是抗干扰能力强 ,采用各种差错控制编码进一步改善传输质量 ,因此差错控制编码是对数字信号进行抗干扰编码 ,目的是提高数字通信的可靠性.随着差错控制编码理论和数字技术的发展 ,差错控制编码在各种通信系统中得到了广泛的应用.差错控制编码的方法很多 ,线性分组码是其中的一种重要方法.线性分组码的检错和纠错能力由检错和纠错定理给出.现有的教科书在证明该定理时直接把一个码字看成一个点 ,这在逻辑上是不成立的.在分组码中 ,把两个码组对应位上数字不同的位数称为码组的距离 ,简称码距 ,又称汉明 (Ham2ming)码距.一种编码的最小码距 dmin的大小直接关系着这种编码的检错和纠错能力 ,因而最小码距是信道编码的一个重要参数 ,在一般情况下 ,对于分组可以通过检错编码定理进行计算，同样可以编写matlab程序进行仿真。2设计原理2.1 线性分组码的基本原理1、在长为n的二元序列集中 选出与消息序列数2k相同数目的码元序列，并使两者一一对应。 几个概念：码字：对应于消息的长n的2k个码元序列，用 表示。 选出的2k个码元序列称为许用码组，另外的2n - 2k个为禁用码组。 码：所有码字的集合，用C表示。 字：所有长为n的二元序列。 消息：长为k的二元码元序列，用 表示。 2、消息 与码字 的映射关系（函数关系） 线性分组码与 呈线性关系（fi为线性函数） 。 编码规则：对于如下的线性分组码 k = 1，故为（n，1）码，称（n，1）重复码。码率：R = 1/n 。2.2 线性分组码编码过程线性分组码是一类奇偶校验码，它可以由（n，k）形式表示。编码器将一个k比特信息分组（信息矢量）转变为一个更长的由给定元素符号集组成的n比特编码分组。当这个符号集包含两个元素（0和1），与二进制相对，称为二进制编码。 分组码是对每段k 位长的信息组，以一定规则增加 r = n - k个检验元，组成长为n 的 序列：( cn-1,cn-2, . . . , c1,c 0) ，称这个序列为码字。在二进制情况下，信息组总共有2 k 个( q 进制为q k个) ，因此通过编码器后，相应的码字也有2k 个。称这2k 个码字集合为( n , k) 分组码。n长序列的可能排列总共有 2n 种。称被选取的2k 个 n重为许用码组，其余 2n - 2k 个为禁用码组。称R = k / n为码率. 对于长度为n的二进制分组码，可以表示成（n，k），通常用于前向纠错。在分组码中，监督位加到信息位之后，形成新码，在编码中，k个信息位，被编为n位长度，（n-k）个监督码的作用是实现检错和纠错。 k 比特信息形成2k个不同的信息序列，称为k元组（k比特序列），同样，n比特可以形成2n个序列，称为n元组。编码过程就是将每个k元组映射到2n个n元组中的一个。分组码是一一对应的编码，即2k个k元组唯一映射到2k个2元组，映射可以通过一个查询表实现。对于线性码，映射当然是线性的。信源所给出的二元信息序列首先分成等长的各个信息组，每组的信息位长度为k，记为：m=( m7 m6)。由上可知，信息组m可能有22种取值。编码器按一定规则，将输入的信息组编制成长为8的码字，记为：c=(c7 c6 c5 c4 c3 c2 c1 c0)。码字的前2位为信息元，分别与信息组的2个信息元依此一一对应相等；码字的后8-2=6个码元为校验元。如果各校验元与前2个信息元之间的关系是线性的（即可用一次方程描述），则称这样的码为(8,2)线性分组码。表给出了一个（8,2）线性分组码的例子。该例子中，信息组为（c7 c6），码组为(c7 c6 c5 c4 c3 c2 c1 c0)，当已知信息组时，按以下规则得到六个校验元，即：c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-1）该组方程称为校验方程，由该方程组可知校验元与信息元之间的线性关系，且校验元具有重复特性：第一位校验元与第四位校验元相同，第二位校验元与第五位校验元相同，第三位校验元与第六位校验元相同。同时，第一位校验元、第四位校验元与信息组第一位相同，第二位校验元、第五位校验元与信息组第二位相同，第三位、第六位校验元均为信息组两位码元作模二和得到的结果。信息组的取值不同，得到的校验元也不相同，从而得到不同的编码组合。当信息元分别取值为：00、01、10、11时，可得如表2-1所示的线性分组码的所有4个码字：信息组码字c7c6c7c6c5c4c3c2c1c00000000000010101101110101011011111110110 表2-1 线性分组码从表2-1中可知该线形分组码有22（4）个许用码字或合法玛字，另有2822个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。(n,k)线性分组码中每个码字都是一个二进制的n重，即二进制n维线性空间中的一个矢量该线性分组码的编码就是从8维线性空间V8中，找出满足一定要求的，由22个2维线性子空间；或者说在满足一定条件下，如何根据已知的2个信息元求得82个校验元。而组成2维线性子空间的22个码字可由2个线性无关的矢量所组成的基底所张成3。对于(8,2)线性分组码，可将式改写为：c7=c7c6=c6c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-2）写成矩阵形式：1 0 1 0 1 1 0 10 1 0 1 1 0 1 1c7 c6 c5 c4 c3 c2 c1 c0= c7 c6（2-3）表中所示的该线性分组码的6个校验元是由式所示的线性方程组决定的。把式移项，可得：（2-4）c7+c5=0c6+c4=0c7+c6+c3=0c7+c2=0c6+c1=0c7+c6+c0= 0由上述可得该线性分组码的生成矩阵G和校验矩阵H分别为：G1 0 1 0 1 1 0 10 1 0 1 1 0 1 11 0 1 0 0 0 0 00 1 0 1 0 0 0 01 1 0 0 1 0 0 01 0 0 0 0 1 0 00 1 0 0 0 0 1 01 1 0 0 0 0 0 1H 因此，当信息组m=(m7 m6 m5 m4)时，相应的码字c为:cmG(c7 c6 c5 c4 c3 c2 c1 c0)3设计过程3.1设计思路设发送端送入信道的长为n的码字序列：c =(cn-1 cn-2 c1 c0)。通过信道传输，到译码器输入端的接收序列为：y =(yn-1 yn-2 y1 y0)。由于信道中噪声的影响，y 序列中的某些码元可能与c 序列中对应码元的值不同，即传输中产生了错误。在二进制序列中，错误为1错成0或者0错成1。因此，信道中的干扰可以用二进制序列e =(en-1 en-2 e1 e0)表示，相应于有错的各位ei ，取值为1，无错的各位ei ，取值为0，则有y=c+e，并称e为信道的错误图样。当e = 0(即ei=0,i=n-1,n-2,，0)时，y=c，表示译码器接收序列y无错；否则，当e0时，yc，表示接收序列y有错。当 c序列长为n时，信道可能产生的错误图样共有2n种。而译码器的任务就是要从收到的序列y中得到c的估值码字和e的估值错误图样。若估值码字与c相等，则译码正确，否则错误。(n,k)码的任一码字，均满足ciHT=0(i=n-1,n-2,，0;HT为校验矩阵的转置矩阵),因此可将接收码字y用上式检验,可得：yHT=( c+e ) HT=cHT+ eHT= eHT若e =0,则yHT=0；若e 0，则yHT0。因此，yHT仅与错误图样有关，而与发送的是哪一个码字无关。令s = yHT= eHT，称为接受序列的伴随式或校正子。3.2设计内容某（7，4）汉明码的生成矩阵为G，用MATLAB仿真编码过程。其中G为 100011101001100010101000101 1：G=1 0 0 0 1 1 1; 0 1 0 0 1 1 0; 0 0 1 0 1 0 1;0 0 0 1 0 1 1主程序如下所示：G=1 0 0 0 1 1 1; 0 1 0 0 1 1 0; 0 0 1 0 1 0 1; 0 0 0 1 0 1 1;%十进制生成矩阵m=1 0 0 0;%十进制数信息组result = groupCoding(m,G)%对信息组进行编码，得到的结果为二进制数其中groupCoding函数如下：function c = groupCoding(m,G) %m为信息组，G为生成矩阵，均为十进制row,col = size(G);%G的行数为k,;列数为nif length(m)= row disp(信息组尺寸与生成矩阵不一致);return;endr=mod(m*G,2);% m*G得到m的码字%将码字转化为二进制tempSum = 0;for i=1:length(r) if r(i) = 1 tempSum = tempSum +2(length(r)-i); endendc = dec2bin(tempSum);程序运行结果如下: 图3 原始序列及得到的相应编码分析结果：在程序运行过程中，当输入为10时，输出图形中可看出编码为10101101；当输入为01时，编码为01011011，同样，当输入为00和11时，也可得到表中对应的码字，而在图39所示的波形中，也可找到信源与编码正确的对应结果。由此可见，编码器能够正确地进行编码，所设计的(7,4)线性分组码编码器正确，程序运行结果符合要求。总 结每一次课程设计都是一种自我学习的过程，因为在以前的学习中，我们往往可以对自己所学得的知识得到扩展和巩固，同时对使用软件的熟悉让我们可以较快完成任务。但是这一次的课程设计，尤其是是陌生的软件和并不熟悉的编程语言让我们一时无从下手。课程设计的初期，对我来说，似乎大部分时间都在荒废而课题上未能有丝毫进展。由于第一次开设数字信号处理课程设计，同时对汇编语言没有更深的学习，我对自己的任务倍感艰辛。在网上和书中大面积的搜索源代码及相关知识无果后，我开始专心研究线性分组码编码理论并且逐步重温汇编语言的语法特性与指令功能，经过一个星期的摸索，我可以较为系统地描述(8,2)线性分组码的编译码原理和特性，论文也得以展开。但是，理论的获得对我来说是不够的，之前所做的只是准备工作，将理论转化为具有可行性的过程才是我的目的所在。经过老师的帮助，我们明白了线性分组码的编码过程其实就是矩阵相乘的结果，而在程序体现最多则是模二加运算。有了明确的思路，我可以编出看似功能符合要求的程序。很显然，对于信息论编码书中很多关于线性编组码的纠错方面上经历了许多坎坷。为此，我多次向老师咨询，同时与其他同学加强在此方面的交流，并且借鉴了与课题内容具有共同之处的源代码，在老师的耐心的教导和同学们热性的帮助下，我的程序每一次经过调试之后都会离要求更进一步，在为数不多的几次修改之后，我的程序可