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

《线性分组码编码的分析与实现.pdf》由会员分享，可在线阅读，更多相关《线性分组码编码的分析与实现.pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、。2 设计原理错误!未定义书签。2.线性分组码的编码.错误!未定义书签。21.1 生成矩阵.错误!未定义书签。2.2 校验矩阵错误!未定义书签。2.伴随式与译码错误!未定义书签。2.1 码的距离及纠检错能力.4 22.2 伴随式与译码.错误!未定义书签。3 设计过程错误!未定义书签。3.1 编码过程.错误!未定义书签。3 仿真程序.错误!未定义书签。3.4 结果分析.错误!未定义书签。总 结.错误!未定义书签。致谢.错误!未定义书签。参考文献错误!未定义书签。-0 1 1 1 0 1 1 1 0 课程描述 线性分组码具有编译码简单,封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效

4、方法，是目前较为流行的差错控制编码技术。对线性分组码的讨论都在有限域GF(2)上进行，域中元素为0,1,域中元素计算为模二加法和模二乘法。分组码是一组固定长度的码组，可表示为(n,k），通常它用于前向纠错。在分组码中,监督位被加到信息位之后，形成新的码。在编码时,个信息位被编为n 位码组长度，而 n-k 个监督位的作用就是实现检错与纠错。对于长度为 n 的二进制线性分组码，它有种可能的码组，从 2n种码组中，可以选择=2k个码组(k)组成一种码。这样,一个 k 比特信息的线性分组码可以映射到一个长度为 n 码组上，该码组是从 M=2个码组构成的码集中选出来的,这样剩下的码组就可以对这个分组码进

5、行检错或纠错。要设计一个(6,3)线性分组码的编译码程序,最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。同时，还要让它具有对接收到的整个码组中提取信息码组的功能。但是，在实际的通信系统中,由于信道传输特性不理想以及加性噪声的影响,接收到的信息中不可避免地会发生错误,影响通信系统的传输可靠性，因而，本设计还要让该程序具有纠正错误的能力,当接收到的码组中有一位码，发生错误时可以检测到这一位错码，并且可以纠正这一位错码，并且让系统从纠正后的码组中提取正确的信息码组。针对给定的矩阵 Q=完成如下的工作：1 完成对任意信息序列的编码 2 根据生成矩阵，形成监督矩阵;3 根据得到的监督矩阵

6、,得到伴随式,并根据它进行译码;4 验证工作的正确性。-2 设计原理 2.1 线性分组码的编码 2.1.1 生成矩阵 线性分组码(n，k)中许用码字(组）为 2个。定义线性分组码的加法为模二加法,乘法为二进制乘法。即+1=0、+0=1、0+1、0+0=；11=1、0=0、00=0、01=0。且码字与码字的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质（,k)的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为 n、信息码元为 k 位、监督码元为 rnk 位的分组码,常记作（，k)码，如果满足r-1n，则有可能构造出纠

7、正一位或一位以上错误的线性码。下面我们通过（7，3）分组码的例子来说明如何具体构造这种线性码。设分组码（，)中,k=3，为能纠正一位误码,要求 r3。现取 r4,则 n=k+r=7。该例子中，信息组为(65c4),码字为(c6c54c3c2c1c0).当已知信息组时，按以下规则得到四个校验元，即 3=c+c 2c6+c+c (-1)c1=cc5 c54 这组方程称为校验方程。（7，3)线性分组码有 23(8)个许用码字或合法码字,另有 27-23个禁用码字。发送方发送的是许用码字,若接收方收到的是禁用码字,则说明传输中发生了错误。为了深化对线性分组码的理论分析，可将其与线性空间联系起来。由于每

8、个码字都是一个二进制的n 重,及二进制维线性空间Vn 中的一个矢量，因此码字-c1 c2 ck 又称为码矢。线性分组码的一个重要参数是码率 r=/n，它说明在一个码字中信息位所占的比重,越大,说明信息位所占比重越大,码的传输信息的有效性越高。由于(,）线性分组,线性分组码的 2k个码字组成了 n 维线性空间 V的一个 K维子空间。因此这 2k个码字完全可由 k 个线性无关的矢量所组成。设此个矢量为1,c,ck，有生成矩阵形式为 G=（2-2)(n，k）码字中的任一码字 ci，均可由这组基底的线性组合生成,即 ci=m Gm-1 2 -k 式中，mi 1 m-2-k 是 k 个信息元组成的信息组

9、。表 2-1 (7，3)线性分组码 信息组 码字 00 000000 001 001101 010 0100111 1 0111010 10 10011 101 110011 0 101001 111 1000 -对于表给出的(7,3）线性分组码,可将写成矩阵形式 6 c5 c4 c3 c c1 c=c 5 4101110011100100111001 故（7，3）码的生成矩阵为 G=101110011100100111001 可以看到,从(7，3)码的个码字中，挑选出 k个线性无关的码字（01110）（00011)，（0011101)作为码的一组基底,用 c=mG 计算得码字。一个系统码的生

10、成矩阵 G,其左边行列应是一个 k 阶单位方阵 Ik，因此生成矩阵 G 表示为 G=Ik P (2-3）式中,是一个(n-k)阶矩阵。2.1.2 校验矩阵 表 2-1 所示的(7,3)线性分组码的四个校验元由式(-1)所示的线性方程组决定的。把（-1)移相,有 c6+4+c0 c6+cc2=0 c+1+c5=0 （2-4)5c4+c0=上式的矩阵形式为-10001101100011001011100011011000110110001100101110001101 0123456ccccccc =0000 这里的四行七列矩阵称为（7，）码的一致校验矩阵,用 H 表示，即 =(25)由矩阵得到(

11、n,)线性分组码的每一码字ci,(i=1，,2）,都必须满足由 H矩阵各行所确定的线性方程组,即 iH=0.（7，3）码的生成矩阵 G 中每一行及其线性组合都是（,k）码的码字，所以有T=0。由和 H 构成的行生成的空间互为零空间,即和 H 彼此正交。HPT r其右边 r 行 r 列组成一个单位方阵。.2 伴随式与译码 2.2 码的距离及纠检错能力 1.码的距离 两个码字之间，对应位取之不同的个数,称为汉明距离,用表示。一个吗的最小距离in定义为 din=mind(ci,cj),j,i,cj(，k),两个码字之间的距离表示了它们之间差别的大小。距离越大,两个码字的差别越大,则传送时从一个码字错

12、成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。2.线性码的纠检错能力 对于任一个(n,k)线性分组码,若要在码字内（1）检测出个错误,则要求码的最小距离 de+;(2)纠正 t 个错误，则要求码的最小距离 dt1;(3）纠-正个错误同时检测 e(t)个错误,则要求 dt+e1;2.2.伴随式与译码 假设接收端收到的码字为 B，那么它和原来发送端发送的码字 A 之间就有可能存在着误差。即在码组 A=a6 a5 a4 a3 a1 a0 中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况,引入了错误

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

14、其他的 Ei均为 0。在后面的译码程序中，建立了一个校正子 S 与错误图样 E 对应的表。也就是收到一个 B 序列，就可以通过计算得到一个校正子，而每一个校正子都对应着一个错误图样 E,再通过模尔加上 E，就可以得到正确的码字。因为在不同的错误序列 B 中,同一位码元错误时对应的是一样的,所以可以利用 0000000 这个正确的码字让它每位依次错误,来求得它的八个校正子。而这时的矩阵 B 就是错误图样 E。这样就算得了 8 个校正子 S。而这时的错误序列 B，就是错误图样,所以有：E 与 S 都已经得到，这时就可以建立一个表来将它们一一对应起来。-0 1 1 1 0 1 1 1 0 1 0 0

15、 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 设计过程 3.1 编码过程 监督矩阵 H 与生成矩阵 G 的关系：由 H 与 G 的分块表示的矩阵形式 =P I-(-1)G=Ik Q （3-）P=Q (3)则有 GHT0 (-4)或 GT=0 （35）已知给出的(，3）码的矩阵 Q (36）则可以根据=k Q求出生成矩阵 G (3-）由=Q 和 H=P I 可求出监督矩阵 H 为 (3-3)(3-2)(3-1)-0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1

16、 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 H=有了生成矩阵后则可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵,即 TLAB 函数为：C=em(*，2);(3-8)其中 C 为编码后的结果，I 为信息矩阵,G 为生成矩阵。则编码的所有情况为:编码序列：信息位|监督位 C=(3-9）.2 仿真程序%H 监督矩阵%G 生成矩阵%C 编码矩阵%I 输入信息序列%R 信道输出码 A 纠错输出码序列 E 错码矩阵%S 校验子矩阵%M 校验子的行的十进制序列%信道编码程序 ler all clse all =1 1 0;0 0 1 0;-0 1;监督矩

17、阵 G=genpr(H）;求 H 阵的生成矩阵 =0 ；0 0 1;0 1 0；1 1;1 0 0;1 1;1 1 0;1 1 1;=rem(I*，2);%求码字 C dip（所得的编码结果为:C=）;%显示输出码字 C disp(）;信道译码程序 lear all;clos l；H=0 1 1 1 0;1 0 0 1 0;1 1 0 0 0;%监督矩阵 H B=input(请输入接收码组:);a，bsiz（);%返回数组 B的维数 E0 0 0;0 0 0 0 1;0 0 1 0;0 0 0;0 0 1 0 0 0;0 0 0 0 0;1 0 0 0 0；1 0 0 1 0;S=rem(B*

18、,2);%求校验子 S i=1；fo i=1:1:a M(,1）=S(,1).*+S(,2).*+S(,3);%求校验子所表示的十进制整数 en for i=1:1:-switch（i,1)cs 0 A(i,：)B（i,：）+(1,:)；e A(i，:)=B(i,:)+E（2,：);case 2 A（i,:)=(i,:)+E（,：);ase 3 A(i,:)B(i，:)+E(4,:);ase A(，:)（i，:)+(,:);cse 5 A(i,:)=B（i,:)E（6,:)；case 6 A(i,:)=B(i,:)+(,:）;case 7 A（,:)=B(i,:)+E(8，:）;en d f

19、i=1:a switch(M(i,)case p（没有出现错误！）;cs 1 isp(注意：第 1 位出现一个错误！请纠正！);s 2 dis(注意:第 2 位出现一个错误！请纠正！);case -dis(注意:第位出现一个错误！请纠正!);ae isp（注意:第 4 位出现一个错误！请纠正!);ase disp(注意:第 5 位出现一个错误!请纠正！);cse 6 disp(注意:第 6 位出现一个错误!请纠正!);cse 7 isp(注意：第位和第 3 位出现两个错误!请纠正!);end end A=rem(A,2)；求出正确的编码 dsp(检纠错后的码组 A);ip();%显示正确的编码

20、 j=1；whie=提取信息位 (:,j）=A(：,j）;j=j+;end dsp（译出的信息序列 I=)；s(）;%显示原信息码 .3 仿真结果图 1输出编码结果及输入正确接收码的译码结果,根据仿真程序得出仿真结果如下图所示:-图 31 输出编码结果和正确输入时显示图 2.输入一位错误时的结果显示图 图-2 有一位错误输入时的显示图 3输入两位特定位错误时的结果显示-图 3-3 有两位特定位错误输入时的显示图 3.结果分析 1输出编码结果及输入正确接收码的译码结果分析 由图 3-1 输出编码结果和正确输入时显示图所示的结果可以看出编码的结果的八种情况和在推导过程中运算的结果是一致的,可以见得

21、程序的编码过程是正确的。对于译码过程而言,当界面显示“请输入接收码组 B：”,然后从提示符后输入:0 0 0 0，由于输入的接收码组与编码后的码字一致，它提取了每个码组的前四位，即信息位，由结果看出译码过程是正确的,并没有出现错译的情况,可见程序的译码片段是正确的。2输入一位错误时的结果分析 对于纠错过程而言,当界面显示“请输入接收码组 B:”。然后从提示符后输入:1 1 0，由图 3-2 有一位错误输入时的显示图所知，接收码组的第五位发生了错误,经程序纠检错误后改正了接收序列的错误，并且正确译出了信息位。可见程序的纠错功能也是可以实现的,以上结果进一步证实了,系统译码程序的正确性。3.输入两

22、位特定位错误时的结果分析-由图3 有两位特定位错误输入时的显示图知,当输入 B=1 0 0 1 0 0时,校正子是 111，错误图样是00100,所以结果显示与理论相符。-总 结 通过对线性分组码中的线性分组码的编码编程实现,了解到线性分组码的构成方式是把信息序列分成每 k 个码元一段,并由这 k 个码元按一定规则产生 r 个校验位,组成长度为 nkr 的码字，用(n，）表示。信息码元与校验位之间为线性关系。并且知道了线性分组码的编码过程信息码元与校验位之间的线性关系实现起来是十分简单的.对于码组长度为n、信息码元为 k 位、监督码元为 r=k 位的分组码，如果满足-1n，则有可能构造出纠正一

23、位或一位以上错误的线性码。就像本设计的（6,)分组码的（n，k)中，n6，k=3，3 能纠正一位误码,检测到两位误码。运用 MATLA语言进行编程,可以较明显的知道编码的过程和译码时出现的错误，码字的最小距离是 3 时，可以纠正一位错误，当输入特定的两位错误时,该码字还可以纠正这两位错误,这种情况在编程结果的命令窗口中可以明显看到。-参考文献 1曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，00.2王慧琴.数字图像处理.北京:北京邮电大学出版社，00.孙丽华编.信息论与纠错编码.电子工业出版社 200，4 苏金明 阮沈勇编.ALAB 实用教程（第二版）.电子工业出版社.08.2 5 梅志红 杨万铨编 MATAB 程序设计基础及其应用.清华大学出版社.2005 6 王华 李有军编 MATLAB 电子仿真与应用教程(第二版).国防工业出版社 200.