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

《线性分组码纠错能力的分析.pdf》由会员分享，可在线阅读，更多相关《线性分组码纠错能力的分析.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘摘要要近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。目前，几乎所有得到实际应用的纠错码都是线性的。线性分组码的应用上越来越广泛，首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。再编制 MATLAB程序对其纠错能力进行仿真。关键词：关键词：纠错；线性分组码；MATLAB目目录录1 课题描述.12 设计原理.12.1 线性分组码的基本原理.12.2 线性分组码编码过程.23

2、设计过程.53.1 设计思路.53.2 设计内容.6总结.8参考文献.9课程设计1 1 课题描述课题描述数字通信最主要的优点之一是抗干扰能力强,采用各种差错控制编码进一步改善传输质量,因此差错控制编码是对数字信号进行抗干扰编码,目的是提高数字通信的可靠性.随着差错控制编码理论和数字技术的发展,差错控制编码在各种通信系统中得到了广泛的应用.差错控制编码的方法很多,线性分组码是其中的一种重要方法.线性分组码的检错和纠错能力由检错和纠错定理给出.现有的教科书在证明该定理时直接把一个码字看成一个点,这在逻辑上是不成立的.在分组码中,把两个码组对应位上数字不同的位数称为码组的距离,简称码距,又称汉明(H

3、am2ming)码距.一种编码的最小码距 dmin的大小直接关系着这种编码的检错和纠错能力,因而最小码距是信道编码的一个重要参数,在一般情况下,对于分组可以通过检错编码定理进行计算，同样可以编写matlab 程序进行仿真。2 2 设计原理设计原理2.12.1 线性分组码的基本原理线性分组码的基本原理 c0，1、在长为 n 的二元序列集中c1，cn选出与消息序列数 2k相同数-1目的码元序列，并使两者一一对应。几个概念：码字：对应于消息的长 n 的 2k个码元序列，用c表示。选出的 2k个码元序列称为许用码组，另外的 2n-2k个为禁用码组。码：所有码字的集合，用 C 表示。字：所有长为 n 的

4、二元序列。u消息：长为 k 的二元码元序列，用表示。2、消息u与码字的映射关系（函数关系），uk-1 c0 f0u0，u1，c fu，u，1101，uk-1，uk-1cn1 fn1u0，u1，c第 1 页 共 9 页课程设计线性分组码c0，c1，cn-1与u0，u1，uk-1呈线性关系（fi为线性函数）。编码规则：对于如下的线性分组码 c0 u0c u10cn 1 u0u0 0,u0 1,nc 00 0c 111k=1，故为（n，1）码，称（n，1）重复码。码率：R=1/n。2.22.2 线性分组码编码过程线性分组码编码过程线性分组码是一类奇偶校验码，它可以由（n，k）形式表示。编码器将一个

5、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 为码率.对于长

6、度为 n 的二进制分组码，可以表示成（n，k），通常用于前向纠错。在分组码中，监督位加到信息位之后，形成新码，在编码中，k 个信息位，被编为 n 位长度，（n-k）个监督码的作用是实现检错和纠错。k 比特信息形成 2k 个不同的信息序列，称为k 元组（k 比特序列），同样，n 比特可以形成 2n 个序列，称为 n 元组。编码过程就是将每个k 元组映射到 2n 个 n 元组中的一个。分组码是一一对应的编码，即2k 个 k 元组唯一映射到 2k 个 2 元组，映射可以通过一个查询表实现。对于线性码，映射当然是线性的。信源所给出的二元信息序列首先分成等长的各个信息组，每组的信息位长度第 2 页 共

7、9 页课程设计为 k，记为：m=m=(m7m6)。由上可知，信息组 mm 可能有 22种取值。编码器按一定规则，将输入的信息组编制成长为 8 的码字，记为：c=c=(c7c6 c5 c4 c3c2 c1c0)。码字的前 2 位为信息元，分别与信息组的 2 个信息元依此一一对应相等；码字的后 8-2=6 个码元为校验元。如果各校验元与前 2 个信息元之间的关系是线性的（即可用一次方程描述），则称这样的码为(8,2)线性分组码。表给出了一个（8,2）线性分组码的例子。该例子中，信息组为（c7 c6），码组为(c7c6 c5 c4 c3c2 c1c0)，当已知信息组时，按以下规则得到六个校验元，即：

8、c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6（2-1）该组方程称为校验方程，由该方程组可知校验元与信息元之间的线性关系，且校验元具有重复特性：第一位校验元与第四位校验元相同，第二位校验元与第五位校验元相同，第三位校验元与第六位校验元相同。同时，第一位校验元、第四位校验元与信息组第一位相同，第二位校验元、第五位校验元与信息组第二位相同，第三位、第六位校验元均为信息组两位码元作模二和得到的结果。信息组的取值不同，得到的校验元也不相同，从而得到不同的编码组合。当信息元分别取值为：00、01、10、11 时，可得如表 2-1 所示的线性分组码的所有 4 个码字：信息组c7c

9、600011011码字c7c6c5c4c3c2c1c000000000010110111010110111110110表 2-1 线性分组码第 3 页 共 9 页课程设计从表 2-1 中可知该线形分组码有 22（4）个许用码字或合法玛字，另有 2822个禁用码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发生了错误。(n,k)线性分组码中每个码字都是一个二进制的 n 重，即二进制 n 维线性空间中的一个矢量该线性分组码的编码就是从 8 维线性空间 V8中，找出满足一定要求的，由 22个 2 维线性子空间；或者说在满足一定条件下，如何根据已知的 2个信息元求得 82 个校验元

10、。而组成 2 维线性子空间的 22个码字可由 2 个线性无关的矢量所组成的基底所张成3。对于(8,2)线性分组码，可将式改写为：c7=c7c6=c6c5=c7c4=c6c3=c7+c6c2=c7c1=c6c0=c7+c6写成矩阵形式：1 0 1 0 1 1 0 10 1 0 1 1 0 1 1（2-2）c7c6 c5 c4 c3c2 c1c0=c7 c6（2-3）表中所示的该线性分组码的 6 个校验元是由式所示的线性方程组决定的。把式移项，可得：c7+c5=0c6+c4=0c7+c6+c3=0c7+c2=0c6+c1=0c7+c6+c0=0由上述可得该线性分组码的生成矩阵 G G 和校验矩阵

11、H H 分别为：（2-4）第 4 页 共 9 页课程设计G G1 0 1 0 1 1 0 10 1 0 1 1 0 1 1H H1 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 1因此，当信息组 mm=(m7 m6 m5 m4)时，相应的码字 c c 为:c cmm G G(c7c6 c5 c4c3c2 c1c0)3 3 设计过程设计过程3.13.1 设计思路设计思路设发送端送入信道的长为 n 的码字序列：c c=(cn-1 cn-2 c1 c0)。通过信道传输，到译

12、码器输入端的接收序列为：y y=(yn-1 yn-2 y1 y0)。由于信道中噪声的影响，y y 序列中的某些码元可能与 c c 序列中对应码元的值不同，即传输中产生了错误。在二进制序列中，错误为 1 错成 0 或者 0 错成 1。因此，信道中的干扰可以用二进制序列 e e=(en-1 en-2 e1 e0)表示，相应于有错的各位 ei，取值为 1，无错的各位 ei，取值为 0，则有 y y=c c+e e，并称 e 为信道的错误图样。当 e e=0(即 ei=0,i=n-1,n-2,，0)时，y y=c c，表示译码器接收序列 y y 无错；否则，当 e e0 时，y yc c，表示接收序列

13、 y y 有错。当 c c 序列长为 n n 时，信道可能产生的错误图样共有 2n种。而译码器的任务就是要从收到的序列 y y 中得到 c c 的估值码字和 e e 的估值错误图样。若估值码字与 c c 相等，则译码正确，否则错误。(n,k)码的任一码字，均满足 ciHT=0(i=n-1,n-2,，0;HT为校验矩阵的转置矩阵),因此可将接收码字 y y 用上式检验,可得：y yHT=(c c+e e)HT=c cHT+e eHT=e eHT若 e e=0,则 y yHT=0；若 e e 0，则 y yHT0。因此，y yHT仅与错误图样有关，而与发送的是哪一个码字无关。令 s s=y yHT

14、=e eHT，称为接受序列的伴随式或校正子。第 5 页 共 9 页课程设计3.23.2 设计内容设计内容某（7，4）汉明码的生成矩阵为 G，用 MATLAB 仿真编码过程。其中 G 为：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

15、函数如下：function c=groupCoding(m,G)%m 为信息组，G 为生成矩阵，均为十进制row,col=size(G);%G 的行数为 k,;列数为 nif length(m)=rowdisp(信息组尺寸与生成矩阵不一致);return;endr=mod(m*G,2);%m*G 得到 m 的码字%将码字转化为二进制tempSum=0;for i=1:length(r)if r(i)=1tempSum=tempSum+2(length(r)-i);endendc=dec2bin(tempSum);第 6 页 共 9 页课程设计程序运行结果如下:图 3 原始序列及得到的相应编码分

16、析结果：在程序运行过程中，当输入为10 时，输出图形中可看出编码为10101101；当输入为 01 时，编码为 01011011，同样，当输入为00 和 11 时，也可得到表中对应的码字，而在图 39 所示的波形中，也可找到信源与编码正确的对应结果。由此可见，编码器能够正确地进行编码，所设计的(7,4)线性分组码编码器正确，程序运行结果符合要求。第 7 页 共 9 页课程设计总总结结每一次课程设计都是一种自我学习的过程，因为在以前的学习中，我们往往可以对自己所学得的知识得到扩展和巩固，同时对使用软件的熟悉让我们可以较快完成任务。但是这一次的课程设计，尤其是是陌生的软件和并不熟悉的编程语言让我们

17、一时无从下手。课程设计的初期，对我来说，似乎大部分时间都在荒废而课题上未能有丝毫进展。由于第一次开设数字信号处理课程设计，同时对汇编语言没有更深的学习，我对自己的任务倍感艰辛。在网上和书中大面积的搜索源代码及相关知识无果后，我开始专心研究线性分组码编码理论并且逐步重温汇编语言的语法特性与指令功能，经过一个星期的摸索，我可以较为系统地描述(8,2)线性分组码的编译码原理和特性，论文也得以展开。但是，理论的获得对我来说是不够的，之前所做的只是准备工作，将理论转化为具有可行性的过程才是我的目的所在。经过老师的帮助，我们明白了线性分组码的编码过程其实就是矩阵相乘的结果，而在程序体现最多则是模二加运算。

18、有了明确的思路，我可以编出看似功能符合要求的程序。很显然，对于信息论编码书中很多关于线性编组码的纠错方面上经历了许多坎坷。为此，我多次向老师咨询，同时与其他同学加强在此方面的交流，并且借鉴了与课题内容具有共同之处的源代码，在老师的耐心的教导和同学们热性的帮助下，我的程序每一次经过调试之后都会离要求更进一步，在为数不多的几次修改之后，我的程序可以成功的运行并且符合设计要求，此时我想到了一句话，“磨刀不误砍柴工”。正是如此，我付出的努力才有了回报。而回顾两周的时光，我发现我和同学们嘴边常说的是关于学习方面的内容。第 8 页 共 9 页课程设计参考文献参考文献1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.3 薛年喜,MATLAB在数字信号处理中的应用.北京：清华大学出版社,20034 陈怀琛，吴大正，高西全.MATLAB及在电子信息课程中的应用.北京：电子科技大学出版社，2003.第 9 页 共 9 页