线性分组码编码的分析与实现

1、课程设计任务书2011 2012学年第一学期专业： 通信工程学号:080110501 姓名： 李琼课程设计名称：信息论与编码课程设计设计题目：线性分组码编码的分析与实现完成期限：自2011年12月19 日至2011年12月_25_日共 周一. 设计目的1、深刻理解信道编码的基本思想与目的；2、理解线性分组码的基本原理与编码过程；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。二. 设计内容给定消息组M及生成矩阵G,编程求解其线性分组码码字。三. 设计要求编写的函数要有通用性。四. 设计条件计算机、MATLAB或其他语言环境五. 参考资料1 曹雪虹，

2、张宗橙信息论与编码北京：清华大学出版社，2007.2 王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）： 教研室主任（签字）： 批准日期：年 月 日摘要该系统是（6, 3）线性分组码的编码的实现，它可以对输入的三位的信息码 进行线性分组码编码。当接收到的六位码字中有一位发生错误时，可以纠正这一位错码；当接收到 的码字有两位发生错误时，只能纠正一位错误，但同时能检测出另一位错误不能 纠正。只有特定位有两位错误时，才能纠正两位错误。这样就译出正确的信息码 组，整个过程是用MATLAB语言实现的。关键词：编码；MATLAB ;纠错目录1课程描述0.2设计原理.1.2.1 线

3、性分组码的编码 1.2.1.1生成矩阵1.2.1.2校验矩阵3.2.2伴随式与译码4.2.2.1码的距离及纠检错能力42.2.2伴随式与译码4.3设计过程5.3.1 编码过程5.3.2仿真程序7.3.4结果分析11总结13致谢14参考文献151课程描述线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提 高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。对线性分组码的讨论都在有限域 GF（2）上进行，域中元素为0,1,域中元素 计算为模二加法和模二乘法。分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的

4、码。在 编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错 与纠错。对于长度为n的二进制线性分组码，它有种 2n可能的码组，从2n种码组 中，可以选择M=2k个码组（kvn）组成一种码。这样，一个k比特信息的线性 分组码可以映射到一个长度为 n码组上，该码组是从 M=2k个码组构成的码集 中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。要设计一个（6, 3）线性分组码的编译码程序，最基本的是要具备对输入的 信息码进行编码，让它具有抗干扰的能力。同时，还要让它具有对接收到的整个 码组中提取信息码组的功能。但是，在实际的通信系统中，由于信道传输特性不 理想以及加性

5、噪声的影响，接收到的信息中不可避免地会发生错误， 影响通信系 统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力，当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码， 并且让系统从纠正后的码组中提取正确的信息码组。针对给定的矩阵0 1 1Q= 1 0 11 1 0J 完成如下的工作：1完成对任意信息序列的编码2根据生成矩阵，形成监督矩阵；3根据得到的监督矩阵，得到伴随式，并根据它进行译码；4验证工作的正确性。2设计原理2.1线性分组码的编码2.1.1生成矩阵线性分组码（n, k）中许用码字（组）为2k个。定义线性分组码的加法为模二加法，乘法为二进制乘法。即

6、 1+1=0、1+0=1、0+1= 1、0+0=0; 1X1=1、1X）=0、0X）=0、0X1=0。且码字：=c “7, “也c o）与码字 & -的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质（n, k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为n、信息码元为k位、监督码元为r= n-k位的分组码，常 记作（n, k）码，如果满足2r- 1 >n则有可能构造出纠正一位或一位以上错误 的线性码。下面我们通过（7, 3）分组码的例子来说明如何具体构造这种线性码。设分 组码（n, k）中，k

7、= 3,为能纠正一位误码，要求r>3现取r= 4,贝U n= k + r =7。该例子中，信息组为（C6C5C4），码字为（CSC5C4C3C2C1C0）.当已知信息组时，按 以下规则得到四个校验元，即C3=C6+C4C2=C6+C5+C4（2-1 ）C1=C6+C5Co=C5+C4这组方程称为校验方程。一373（7, 3）线性分组码有23 （8）个许用码字或合法码字，另有 27-23个禁用 码字。发送方发送的是许用码字，若接收方收到的是禁用码字，则说明传输中发 生了错误。为了深化对线性分组码的理论分析， 可将其与线性空间联系起来。由于每个 码字都是一个二进制的n重，及二进制n维线性空间

8、Vn中的一个矢量，因此码 字又称为码矢。线性分组码的一个重要参数是码率 r=k/n,它说明在一个码字中信息位所占的比重，r越大，说明信息位所占比重越大，码的传输信息的有效性越高。由于(n,k)线性分组，线性分组码的2k个码字组成了 n维线性空间Vn的一个kK维子空间。因此这2k个码字完全可由k个线性无关的矢量所组成。设此k个矢量为C1,C2,ck,有生成矩阵形式为C1C2G=(2-2)Ck(n,k)码字中的任一码字q,均可由这组基底的线性组合生成，即c=mi G=m-i mn-2 mn-k G式中，mi =mn-i mn-2m-k 是k个信息元组成的信息组。表2-1(7，3)线性分组码信息组码

9、字0000000000001001110101001001110110111010100100110101101001111011010011111110100对于表2-1给出的(7, 3)线性分组码，可将写成矩阵形式C6 C5 C4 C3 C2 Cl Co=C 6 C5 C4 故（7，3）码的生成矩阵为100可以看到，从（7,3）码的8个码字中，挑选出k=3个线性无关的码字（1001110） （010011D，（ 00111101作为码的一组基底，用 C=m G计算得码字。一个系统码的生成矩阵G，其左边k行k列应是一个k阶单位方阵Ik，因此 生成矩阵G表示为(2-3)G=lkP式中，P是一个

10、kx （n-k）阶矩阵。2.1.2校验矩阵表2-1所示的（7, 3）线性分组码的四个校验元由式（2-1）所示的线性方 程组决定的。把（2-1）移相，有c6+c4+c3=0(2-4)c6+c5+c4+c2=0 c6+c1+c5=0 c5+c4+c0=01110 1110 0 00、000上式的矩阵形式为C6c5c4c3c2c1c0丿这里的四行七列矩阵称为（7, 3）码的一致校验矩阵，用H表示，即H=11101111101100001000010001J kCi,(i=1,2,2 ),都必须满足由H矩阵各(2-5)由H矩阵得到(n,k)线性分组码的每一码字行所确定的线性方程组，即 G Ht=0.(

11、7，3)码的生成矩阵G中每一行及其线 性组合都是(n,k)码的码字，所以有G Ht =0。由G和H构成的行生成的空 间互为零空间，即G和H彼此正交。H=Pt Ir其右边r行r列组成一个单位方阵。2.2伴随式与译码2.2.1码的距离及纠检错能力1.码的距离两个码字之间，对应位取之不同的个数，称为汉明距离，用 d表示。一个吗 的最小距离dmin定义为dmin=mind(ci,c),i工j,Ci,C (n,k),两个码字之间的距离表 示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码 字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。2.线性码的纠检错能力对于任一个

12、(n,k)线性分组码，若要在码字内(1)检测出e个错误，则要 求码的最小距离d> e+1;(2)纠正t个错误，则要求码的最小距离d> 2t+1;(3)纠正 t个错误同时检测e(>t)个错误，则要求d>t+e+1；222伴随式与译码假设接收端收到的码字为B，那么它和原来发送端发送的码字 A之间就有可能 存在着误差。即在码组 a= a6 a5 a4 a3 02 a1 a中的任意一位就有可能出错。这 样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意 思。为了描述数据在传输信道中出现错误的情况，引入了错误图样E,在错误图样中，0代表对应位没有传错，1代表传输

13、错误。实际上错误图样 E就是收序列 与发送序列的差。所以在译码中用接收到的码字 B模尔加错误图样E就可以得到发送端的正确码字A。因此译码的过程就是要找到错误图样 E定义：校正子SS = B * H T = ( A + E ) * HT+ E * H因为A是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为 0。 显然，S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子 S,也 就可以找到E。而与发送的码字无关。若 E=0,则S=0；因此根据S是否为0可 进行码字的检错。如果接收码字B中只有一位码元发生错误，又设错误在第i位。即Ei-i=1,其他的Ei均为0。在后面的译码程序中，建

14、立了一个校正子S与错误图样E对应的表。 也就是收到一个B序列，就可以通过计算得到一个校正子，而每一个校正子都 对应着一个错误图样E，再通过B模尔加上E，就可以得到正确的码字 A。因为在不同的错误序列B中，同一位码元错误时对应的 E是一样的，所以可 以利用0000000这个正确的码字让它每位依次错误， 来求得它的八个校正子。而 这时的矩阵B就是错误图样E。这样就算得了 8个校正子S。而这时的错误序列B，就是错误图样E,所以有： E与S都已经得到，这时就可以建立一个表来将它们一一对应起来。3设计过程3.1编码过程监督矩阵H与生成矩阵G的关系：(3-1 )(3-1)(3-2)(3-2)由H与G的分块

15、表示的矩阵形式H =P I n-kG=lk Qp=Qt(3-3 )(3-3)(3-4)(3-5)(3-6)则可以根据G=l k Q求出生成矩阵斤00G=110丿(3-7)则有G- H=0或 H - G=0已知给出的(6, 3)码的Q矩阵0 1 11 0 11 1 0 丿Q=由P = Q和H =P I n-k可求出监督矩阵H为1110 0H=0 1 0 1 01 0 0 0 1 丿有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵，即MATLA函数为:(3-8)C=rem(l*G,2);其中C为编码后的结果，I为信息矩阵，G为生成矩阵。 则编码的所有情况为： 编码序列:信息位|

16、监督位C=0 00 0 1110 10 100 110 110 0 010 11110 11 10 11 00 0(3-9)3.2仿真程序% H监督矩阵% G生成矩阵% C编码矩阵% I输入信息序列% R信道输出码% A纠错输出码序列% E错码矩阵%S校验子矩阵% M校验子的行的十进制序列%信道编码程序clear allclose allH=0 1 1 1 0 0;1 0 1 0 1 0;1 1 0 0 0 1;G=ge n2par(H);%监督矩阵H%求H阵的生成矩阵GI=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(l*G,2)

17、;disp(所得的编码结果为：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;B=input('请输入接收码组B:');a,b=size(B);%求码字C%显示输出码字C%监督矩阵H%返回数组B的维数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);%求校验子 Si=1;for i=

18、1:1:aM(i,1)=S(i,1).*4+S(i,2)*2+S(i,3);%求校验子所表示的十进制整数endfor i=1:1:aswitch(M(i,1)case 0A(i,:)=B(i,:)+E(1,:);case 1A(i,:)=B(i,:)+E(2,:);case 2A(i,:)=B(i,:)+E(3,:);case 3A(i,:)=B(i,:)+E(4,:);case 4A(i,:)=B(i,:)+E(5,:);case 5A(i,:)=B(i,:)+E(6,:);case 6A(i,:)=B(i,:)+E(7,:);case 7A(i,:)=B(i,:)+E(8,:);enden

19、dfor i=1:1:aswitch（M（i,1）case 0disp （没有出现错误！'case 1disp （注意：第1位出现一个错误！请纠正！'case 2disp（注意：第2位出现一个错误！请纠正！'case 3disp（注意：第3位出现一个错误！请纠正！'case 4disp（注意：第4位出现一个错误！请纠正！'case 5disp（注意：第5位出现一个错误！请纠正！'case 6disp（注意：第6位出现一个错误！请纠正！'case 7disp（注意：第6位和第3位出现两个错误！请纠正！）;endendA=rem（A,2）;%

20、求出正确的编码disp（检纠错后的码组A='）;disp（A）;%显示正确的编码j=1；while j<=3%提取信息位I（：,j）=A（:,j）;j=j+1;enddisp（'译出的信息序列匸'）;disp(l);3.3仿真结果图%显示原信息码1 输出编码结果及输入正确接收码的译码结果，根据仿真程序得出仿真结果如下 图所示：» 加得雨編网结卑为：C=0Q0000110 1010 11010 0010 11110 111100ioiioio001I诸输入接收码齟氏D 0 1 1 i 0 1没有出现错渓？ 检纠错后的码组姑0G1110译出的信息序列U001

21、»图3-1输出编码结果和正确输入时显示图2 输入一位错误时的结果显示图»所得的漏姥结果为心000000001110010101011011100011101101110110111000请输入接收码姐附0 Q 0 1 0 0 注意：策&位出现一于错误！诸纠正！ 检纠错后的码组职001100译出的信扈序列左001图3-2有一位错误输入时的显示图3 输入两位特定位错误时的结果显示00000000111010101011011100011101101110110111000谙输入接收码组艮i a o 1 o 注意：策&位和第3位出现两个措误？诸纠正？检纠墙后的码组

22、期0000 0 0译出的信息序列"000»图3-3有两位特定位错误输入时的显示图3.4结果分析1 输出编码结果及输入正确接收码的译码结果分析由图3-1输出编码结果和正确输入时显示图所示的结果可以看出编码的结果 的八种情况和在推导过程中运算的结果是一致的，可以见得程序的编码过程是正确的。对于译码过程而言，当界面显示“请输入接收码组B:” ，然后从提示符后输入：0 0 0 1 0 0,由于输入的接收码组与编码后的码字一致，它提取了每个 码组的前四位，即信息位，由结果看出译码过程是正确的，并没有出现错译的情 况，可见程序的译码片段是正确的。2 输入一位错误时的结果分析对于纠错过程

23、而言，当界面显示“请输入接收码组 B:” 。然后从提示符后输 入：1 1 1 1 1 0，由图3-2有一位错误输入时的显示图所知， 接收码组的第五位 发生了错误，经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。 可见程序的纠错功能也是可以实现的， 以上结果进一步证实了，系统译码程序的 正确性。3 输入两位特定位错误时的结果分析由图3-3有两位特定位错误输入时的显示图知，当输入 B=1 0 0 1 0 0时，校正 子是111,错误图样是100100,所以结果显示与理论相符。通过对线性分组码中的线性分组码的编码编程实现，了解到线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r个 校验位，组成长度为n=k+r的码字，用（n，k）表示。信息码元与校验位之间为线 性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实 现起来是十分简单的对于码组长度为n、信息码元为k位、监督码元为r = n- k位的分组码，如 果满足2r - 1>n,则有可能构造出纠正一位或一位以上错误的线性码。就像本 设计的（6，3）分组码的（n，k）中，n=6， k = 3，r >3能纠正一位误码，检测 到两位