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

课程设计任务书20112012学年第一学期专业： 通信工程 学号： 姓名： 课程设计名称： 信息论与编码课程设计 设计题目： 线性分组码纠错能力的分析 完成期限：自2011年 12 月 19 日至 2011 年 12 月 25 日共 1 周一设计目的1、理解线性分组码的基本原理与编码过程；2、掌握线性分组码的最小距离与纠检错能力的关系；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。二设计内容 给定码字集合，编程求其最小距离，并分析纠检错能力。三设计要求1、编写的函数要有通用性。四设计条件计算机、MATLAB或其他语言环境五参考资料1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.2王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要近年来，随着计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，人们对数据传输和存储系统的可靠性提出了越来越高的要求。因此，如何控制差错、提高数据传输和存储的可靠性，成为现代数字通信系统设计工作者面临的重要课题。目前，几乎所有得到实际应用的纠错码都是线性的。线性分组码的应用上越来越广泛，首先介绍有关纠错码的基本概念，然后重点论述线性分组码的定义及其编译码理论。再运用仿真软件CCS平台对其纠错能力进行仿真。关键词： 纠错；线性分组码；CSS仿真目 录1.课题描述12.设计原理1 2.1.线性分组码的基本原理1 2.2.线性分组码编码过程23.设计过程5 3.1.设计思路5 3.2.设计内容6 3.3.关于程序中最小距离及纠检错能力的分析83.3.1.线性分组码的生成矩阵和校验矩阵83.3.2.最小距离、纠错能力的分析8总 结10参考文献11课程设计说明书（论文）1. 课题描述要设计一个线性分组码的码字集合程序，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。同时，还要让它具有对接收到的整个码组中提取信息码组的功能。但是，在实际的通信系统中，由于信道传输特性不理想以及加性噪声的影响，接收到的信息中不可避免地会发生错误，影响通信系统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组。本课题主要是对给定码字集合，编程求其最小距离，并分析纠检错能力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 从表中可知该线形分组码有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. 设计内容某（8，2）汉明码的生成矩阵为H，用仿真软件CCS平台编码过程。其中H为 100011101001100010101000101 1：H=1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1主程序如下所示：title cyclencode .mmregs .def _c_int00STACK .usect STACK,10H .bss M_BUFF,2;输入2比特数 .bss O_BUFF,8;输出8比特数 .bss P_BUFF,16;存放生成矩阵 .dataP_MATRIX .word 1,0;存放生成矩阵的具体内容，同时以列的方式进行排序 . word 0,1 . word 1,0 . word 0,1 . word 1,1 . word 1,0 . word 0,1 . word 1,1 . text_c_int00: STM #0,SWWSR STM #STACK+10H,SP STM #P_BUFF,AR1 RPT #15;设定一组源码与生成矩阵中各个元素相乘的次数为16次 MVPD P_MATRIX,*AR1+ START: NOP;加入输入显示 STM #O_BUFF,AR2 STM #P_BUFF,AR5 STM #7,AR6;设定输出为8个码字LOOP: STM #M_BUFF,AR3 CALL SUM BANZ LOOP,*AR6- NOP;加入输出显示 B STARTSUM: RPTZ A,#1;设定datain文件中源码的读取方式为每次两个 MAC *AR3+,*AR5+,A AND #0001H,A STL A,*AR2+ RET end程序运行结果如下:图3.1 输入（8,2）汉明码的序列图形 图3-2 编码后的（8,2）输出波形波形分析：在程序运行过程中，当输入为10时，输出图形中可看出编码为10101101；当输入为01时，编码为01011011，同样，当输入为00和11时，也可得到表中对应的码字，而在图39所示的波形中，也可找到信源与编码正确的对应结果。由此可见，编码器能够正确地进行编码，所设计的（8，2）线性分组码编码器正确，程序运行结果符合要求。3.3. 关于程序中最小距离及纠检错能力的分析3.3.1. 线性分组码的生成矩阵和校验矩阵线性分组码码空间C是由k个线性无关的基底gk-1,.,g1,g0张成的k维n重子空间，码空间的所有元素（即码字）都可以写成k个基底的线性组合，即c=mk-1gk-1+m1g1+m0go,这种线性组合特征正是线性分组码名称的来历。3.3.2. 最小距离、纠错能力的分析任何最小距离的线性分组码，其检错能力为（-1），纠错能力t为最小距离表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力自然越强，因此成了衡量分组码性能最重要指标之一。估算最小距离的纠检错设计的必要步骤，最原始的方法是逐一计算两两码字之间距离，找出其中最小者。线性分组码的最小距离等于码集中时非零码字的最小重量，即=minw(ci) Ci及Ci0式中，符号w(ci)表示Ci重量（的个数）。这里利用了群的封闭性，由于分组码是群码，任意两码字之和扔是码字，即C因此任意两码字之间的汉明距离其实必是另一码字的重量，表示为d（Cj,Ck）=W(Ci)，mind(C j,Ck)=min W(Ci)。（n,k）线性分组码最小距离等于的必要条件是：效验矩阵H中有（-1）列线性无关。（n,k）线性分组码的最小距离必定小于等于（n-k+1），即（n-k+1）若某码的最小距离达到了可能取得的最小距离，但还需说明的另外一点是码的总体纠错能力不仅仅与有关。总 结在自己独立完成此次课程设计的过程中，通过查找课本以及相关资料，使我更加理解线性分组码的基本原理，并能够通过运用仿真软件CCS平台进行编码译码，在线性分组码编码过程中掌握了线性分组码的最小距离与纠检错能力的关系，我可以在给定码字集合，编程求其最小距离，并分析纠检错能力。c=mk-1gk-1+m1g1+m0go,这种线