2022年线性分组码编码的分析与实现 .pdf

课程设计任务书20112012学年第一学期专业： 通信工程学号：080110501 姓名： 李琼课程设计名称 ：信息论与编码课程设计设计题目 ：线性分组码编码的分析与实现完成期限 ：自 2011 年 12 月 19 日至 2011 年 12 月 25 日共 1 周一设计目的1、深刻理解信道编码的基本思想与目的；2、理解线性分组码的基本原理与编码过程；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用 MATLAB 或其他语言进行编程。二设计内容给定消息组 M 及生成矩阵 G，编程求解其线性分组码码字。三设计要求编写的函数要有通用性。四设计条件计算机、 MATLAB 或其他语言环境五参考资料1曹雪虹，张宗橙 .信息论与编码 .北京：清华大学出版社， 2007. 2王慧琴 .数字图像处理 .北京：北京邮电大学出版社，2007. 指导教师（签字）：教研室主任（签字）：批准日期：年月日精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 19 页摘要该系统是（ 6，3）线性分组码的编码的实现，它可以对输入的三位的信息码进行线性分组码编码。当接收到的六位码字中有一位发生错误时，可以纠正这一位错码；当接收到的码字有两位发生错误时， 只能纠正一位错误， 但同时能检测出另一位错误不能纠正。只有特定位有两位错误时， 才能纠正两位错误。 这样就译出正确的信息码组，整个过程是用MATLAB 语言实现的。关键词： 编码；MATLAB ；纠错精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 19 页目录1 课程描述 . 0 2 设计原理 . 1 2.1 线性分组码的编码 . 1 2.1.1 生成矩阵 . 1 2.1.2 校验矩阵 . 3 2.2 伴随式与译码 . 4 2.2.1 码的距离及纠检错能力 . 4 2.2.2 伴随式与译码 . 4 3 设计过程 . 5 3.1 编码过程 . 5 3.2 仿真程序 . 7 3.4 结果分析 . 11 总 结 . 13 致谢 . 14 参考文献 . 15 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 19 页0 1 1 1 0 1 1 1 0 1 课程描述线性分组码具有编译码简单， 封闭性好等特点， 采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。对线性分组码的讨论都在有限域GF(2)上进行，域中元素为 0,1, 域中元素计算为模二加法和模二乘法。分组码是一组固定长度的码组，可表示为（n , k） ，通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时， k 个信息位被编为 n 位码组长度，而 n-k 个监督位的作用就是实现检错与纠错。对于长度为 n 的二进制线性分组码，它有种2n可能的码组，从 2n种码组中，可以选择 M=2k个码组（ kn）组成一种码。这样，一个k 比特信息的线性分组码可以映射到一个长度为n 码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。要设计一个（ 6，3）线性分组码的编译码程序，最基本的是要具备对输入的信息码进行编码， 让它具有抗干扰的能力。 同时，还要让它具有对接收到的整个码组中提取信息码组的功能。 但是，在实际的通信系统中， 由于信道传输特性不理想以及加性噪声的影响， 接收到的信息中不可避免地会发生错误，影响通信系统的传输可靠性， 因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码， 并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组。针对给定的矩阵Q= 完成如下的工作：1 完成对任意信息序列的编码2 根据生成矩阵，形成监督矩阵；3 根据得到的监督矩阵，得到伴随式，并根据它进行译码；4 验证工作的正确性。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 19 页2 设计原理2.1 线性分组码的编码2.1.1 生成矩阵线性分组码（ n，k）中许用码字（组）为2k个。定义线性分组码的加法为模二加法，乘法为二进制乘法。 即 1+1=0、 1+0=1、 0+1=1、 0+0=0； 1 1=1、 1 0=0、0 0=0、0 1=0。且码字与码字的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质（n，k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为 n、信息码元为 k 位、监督码元为 rnk 位的分组码，常记作（ n，k）码，如果满足 2r1n，则有可能构造出纠正一位或一位以上错误的线性码。下面我们通过（ 7，3）分组码的例子来说明如何具体构造这种线性码。设分组码（ n，k）中， k = 3，为能纠正一位误码，要求r3 。现取 r4，则 nkr7。该例子中，信息组为(c6c5c4),码字为 (c6c5c4c3c2c1c0).当已知信息组时，按以下规则得到四个校验元，即c3=c6+c4c2=c6+c5+c4 （2-1）c1=c6+c5c0=c5+c4 这组方程称为校验方程。（7，3）线性分组码有23（8）个许用码字或合法码字，另有27-23个禁用码字。发送方发送的是许用码字， 若接收方收到的是禁用码字，则说明传输中发生了错误。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。 由于每个码字都是一个二进制的n 重，及二进制 n 维线性空间 Vn 中的一个矢量，因此码字又称为码矢。线性分组码的一个重要参数是码率r=k/n,它说明在一个码字中信精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 19 页c1c2ck息位所占的比重， r 越大，说明信息位所占比重越大，码的传输信息的有效性越高。由于(n,k)线性分组，线性分组码的 2k个码字组成了 n 维线性空间 Vn 的一个K 维子空间。因此这2k个码字完全可由 k 个线性无关的矢量所组成。设此 k 个矢量为 c1,c2,ck,有生成矩阵形式为G= （2-2）(n,k)码字中的任一码字ci,均可由这组基底的线性组合生成，即ci=miG=mn-1 mn-2 mn-k G 式中， mi=mn-1 mn-2mn-k 是 k 个信息元组成的信息组。表 2-1 （7，3）线性分组码信息组码字000 0000000 001 0011101 010 0100111 011 0111010 100 100110 101 1010011 110 1101001 111 1110100 对于表 2-1 给出的（ 7，3）线性分组码，可将写成矩阵形式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 19 页c6 c5 c4 c3 c2 c1 c0=c6 c5 c4101110011100100111001故（7，3）码的生成矩阵为G= 101110011100100111001可以看到，从 （7， 3） 码的 8个码字中，挑选出 k=3个线性无关的码字（1001110 ）（0100111 ） ， （00111101 ）作为码的一组基底，用c=mG 计算得码字。一个系统码的生成矩阵G，其左边 k 行 k 列应是一个 k 阶单位方阵 Ik，因此生成矩阵 G 表示为G=IkP（ 2-3）式中， P是一个 k(n-k)阶矩阵。2.1.2 校验矩阵表 2-1 所示的（ 7，3）线性分组码的四个校验元由式（2-1）所示的线性方程组决定的。把（ 2-1）移相，有c6+c4+c3=0 c6+c5+c4+c2=0 c6+c1+c5=0 （2-4）c5+c4+c0=0 上式的矩阵形式为10001101100011001011100011010123456ccccccc= 0000这里的四行七列矩阵称为（7，3）码的一致校验矩阵，用H 表示，即精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 19 页1000110110001100101110001101H= （2-5）由 H 矩阵得到 (n,k)线性分组码的每一码字ci,(i=1,2,2k),都必须满足由 H 矩阵各行所确定的线性方程组，即ciHT=0.（7，3）码的生成矩阵 G 中每一行及其线性组合都是（ n,k）码的码字，所以有GHT=0。由 G 和 H 构成的行生成的空间互为零空间，即 G 和 H 彼此正交。H=PT Ir其右边 r 行 r 列组成一个单位方阵。2.2 伴随式与译码2.2.1 码的距离及纠检错能力1码的距离两个码字之间，对应位取之不同的个数，称为汉明距离，用d 表示。一个吗的最小距离 dmin定义为 dmin=mind(ci,cj),ij,ci,cj(n,k), 两个码字之间的距离表示了它们之间差别的大小。 距离越大， 两个码字的差别越大， 则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。2. 线性码的纠检错能力对于任一个（ n,k）线性分组码，若要在码字内（1） 检测出 e个错误，则要求码的最小距离 de+1;(2) 纠正 t 个错误，则要求码的最小距离d2t+1;(3)纠正t 个错误同时检测e(t)个错误，则要求dt+e+1；2.2.2 伴随式与译码假设接收端收到的码字为B，那么它和原来发送端发送的码字A 之间就有可能存在着误差。即在码组A=a6 a5 a4 a3 a2 a1 a0 中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样E，在错误图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 19 页样中， 0 代表对应位没有传错， 1 代表传输错误。实际上错误图样E 就是收序列与发送序列的差。所以在译码中用接收到的码字B 模尔加错误图样E 就可以得到发送端的正确码字A。因此译码的过程就是要找到错误图样E。定义：校正子 S S = B * HT= ( A + E ) * HT = A * HT+ E * HT = E * HT因为 A 是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为0。显然， S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子S，也就可以找到 E。而与发送的码字无关。若E=0，则 S=0；因此根据 S 是否为 0 可进行码字的检错。如果接收码字 B 中只有一位码元发生错误，又设错误在第i 位。即 Ei-1=1,其他的 Ei均为 0。 在后面的译码程序中，建立了一个校正子S 与错误图样 E 对应的表。也就是收到一个 B 序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样E，再通过 B 模尔加上 E，就可以得到正确的码字A。因为在不同的错误序列B 中，同一位码元错误时对应的E 是一样的，所以可以利用 0000000这个正确的码字让它每位依次错误，来求得它的八个校正子。 而这时的矩阵 B 就是错误图样 E。这样就算得了 8 个校正子 S。而这时的错误序列B，就是错误图样 E，所以有：E 与 S都已经得到，这时就可以建立一个表来将它们一一对应起来。3 设计过程3.1 编码过程监督矩阵 H与生成矩阵 G的关系：由 H与 G的分块表示的矩阵形式H =P In-k （3-1）G=Ik Q （3-2）(3-2) (3-1) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 19 页01 1 10 1 1 1 0 10 0 0 1 1 01 0 1 0 1 0 0 1 1 1 0 01 1 1 0 0 10 1 0 1 0 1 1 0 0 0 1 00 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 P=QT （3-3）则有 G HT=0 （3-4）或 H GT=0 （3-5）已知给出的（ 6，3）码的 Q 矩阵Q= （3-6）则可以根据 G=Ik Q求出生成矩阵G= （3-7）由P=QT 和H =P In-k 可求出监督矩阵H为H= 有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLAB 函数为：C=rem(I*G,2); （3-8）其中 C为编码后的结果， I 为信息矩阵， G为生成矩阵。则编码的所有情况为：编码序列：信息位 | 监督位 C= （3-9）(3-3) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 19 页3.2 仿真程序% H 监督矩阵% G 生成矩阵% C 编码矩阵% I 输入信息序列% R 信道输出码% A 纠错输出码序列% E 错码矩阵% S 校验子矩阵% M 校验子的行的十进制序列%信道编码程序clear all close all H=0 1 1 1 0 0; 1 0 1 0 1 0; 1 1 0 0 0 1; %监督矩阵 H G=gen2par(H); %求 H 阵的生成矩阵 G I=0 0 0;0 0 1;0 1 0;0 1 1;1 0 0;1 0 1;1 1 0;1 1 1; C=rem(I*G,2); %求码字 C disp(所得的编码结果为 :C=); %显示输出码字 C disp(C); %信道译码程序clear all; close all; H=0 1 1 1 0 0; 1 0 1 0 1 0; 1 1 0 0 0 1; %监督矩阵 H B=input(请输入接收码组 B:); a,b=size(B); %返回数组 B 的维数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 19 页E=0 0 0 0 0 0;0 0 0 0 0 1;0 0 0 0 1 0;0 0 0 1 0 0; 0 0 1 0 0 0;0 1 0 0 0 0;1 0 0 0 0 0;1 0 0 1 0 0; S=rem(B*H,2); %求校验子 S i=1; for i=1:1:a M(i,1)=S(i,1).*4+S(i,2).*2+S(i,3); %求校验子所表示的十进制整数end for i=1:1:a switch(M(i,1) case 0 A(i,:)=B(i,:)+E(1,:); case 1 A(i,:)=B(i,:)+E(2,:); case 2 A(i,:)=B(i,:)+E(3,:); case 3 A(i,:)=B(i,:)+E(4,:); case 4 A(i,:)=B(i,:)+E(5,:); case 5 A(i,:)=B(i,:)+E(6,:); case 6 A(i,:)=B(i,:)+E(7,:); case 7 A(i,:)=B(i,:)+E(8,:); end end 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 19 页for i=1:1:a switch(M(i,1) case 0 disp( 没有出现错误！ ); case 1 disp( 注意：第 1 位出现一个错误！请纠正！ ); case 2 disp( 注意：第 2 位出现一个错误！请纠正！ ); case 3 disp( 注意：第 3 位出现一个错误！请纠正！ ); case 4 disp( 注意：第 4 位出现一个错误！请纠正！ ); case 5 disp( 注意：第 5 位出现一个错误！请纠正！ ); case 6 disp( 注意：第 6 位出现一个错误！请纠正！ ); case 7 disp( 注意：第 6 位和第 3 位出现两个错误！请纠正！ ); end end A=rem(A,2); %求出正确的编码disp(检纠错后的码组 A=); disp(A); %显示正确的编码j=1; while j=3 %提取信息位I(:,j)=A(:,j); j=j+1; end disp(译出的信息序列 I=); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 19 页disp(I); %显示原信息码3.3 仿真结果图1输出编码结果及输入正确接收码的译码结果,根据仿真程序得出仿真结果如下图所示：图 3-1 输出编码结果和正确输入时显示图2输入一位错误时的结果显示图图 3-2 有一位错误输入时的显示图3输入两位特定位错误时的结果显示精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页图 3-3 有两位特定位错误输入时的显示图3.4 结果分析1输出编码结果及输入正确接收码的译码结果分析由图 3-1 输出编码结果和正确输入时显示图所示的结果可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的，可以见得程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B： ” ，然后从提示符后输入：0 0 0 1 0 0，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位， 即信息位， 由结果看出译码过程是正确的，并没有出现错译的情况，可见程序的译码片段是正确的。2输入一位错误时的结果分析对于纠错过程而言，当界面显示“请输入接收码组B： ” 。然后从提示符后输入：1 1 1 1 1 0，由图 3-2 有一位错误输入时的显示图所知，接收码组的第五位发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的，以上结果进一步证实了， 系统译码程序的正确性。3输入两位特定位错误时的结果分析精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 19 页由图 3-3 有两位特定位错误输入时的显示图知，当输入B=1 0 0 1 0 0时，校正子是 111，错误图样是 100100，所以结果显示与理论相符。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 19 页总 结通过对线性分组码中的线性分组码的编码编程实现，了解到线性分组码的构成方式是把信息序列分成每k 个码元一段，并由这 k 个码元按一定规则产生r 个校验位，组成长度为 n=k+r 的码字，用 (n ，k) 表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的 . 对于码组长度为 n、信息码元为 k 位、监督码元为 rnk 位的分组码，如果满足 2r1n，则有可能构造出纠正一位或一位以上错误的线性码。就像本设计的（ 6，3）分组码的（ n，k）中，n=6，k = 3，r3 能纠正一位误码，检测到两位误码。运用 MATLAB语言进行编程，可以较明显的知道编码的过程和译码时出现的错误，码字的最小距离是3 时，可以纠正一位错误，当输入特定的两位错误时，该码字还可以纠正这两位错误，这种情况在编程结果的命令窗口中可以明显看到。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 19 页致谢我的设计任务较顺利地完成了。通过查阅资料， 我仔仔细细研究了几天， 终于明白了线性分组码的构成方式是把信息序列分成每k 个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r 的码字，用 (n ，k) 表示。信息码元与校验位之间为线性关系，利用书上公式算出生成矩阵和监督矩阵，然后用信息组与生成矩阵相乘得到所要编码的码字，译码是编码的逆过程， 我的码间最小距离是 3，检错一位错误的同时可以纠正一位错误，当输入特定的两位错误时，该码字还可以纠正这两位错误， 这种情况在编程结果的命令窗口中可以明显看到。理论的知识弄懂后，我用MATLAB 软件仿真， MATLAB 语言简单，使用性好，通过这次课设， 使我渐渐了解了 MATLAB 的很多函数用法， 提高了我的编程能力。总之，此次课设使我学到很多东西，不仅提高了我的动手能力及自学能力，还知道了我的不足之处， 今后应加强。 这次课设能进展如此顺利， 多亏了李老师不辞辛苦， 不厌其烦的耐心指导， 同学们之间互相协作， 还有我使用的参考书的编者们的帮助，在此我诚挚地感谢您们！精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 19 页参考文献1曹雪虹，张宗橙 .信息论与编码 .北京：清华大学出版社， 2007. 2王慧琴 .数字图像处理 .北京：北京邮电大学出版社，2007. 3 孙丽华编 . 信息论与纠错编码 . 电子工业出版社 . 2005 ，3 4 苏金明 阮沈勇编 . MATLAB实用教程（第二版） . 电子工业出版社 . 2008.2 5 梅志红 杨万铨编 . MATLAB程序设计基础及其应用 . 清华大学出版社 .2005 6 王华 李有军编 . MATLAB 电子仿真与应用教程 ( 第二版 ). 国防工业出版社 . 2007.3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 19 页