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

吉林建筑大学电气与计算机学院信息理论与编码课程设计报告设计题目：线性分组码编码的分析与实现专业班级：电子信息工程121学生姓名：学号：指导教师：设计时间：2016.1.11－2016.1.22教师评语：成绩评阅教师日期1第1章概述1.1设计的作用、目的《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求线性分组码具有编译码简单，封闭性好等特点，采用差错控制编码技术是提高数字通信可靠性的有效方法，是目前较为流行的差错控制编码技术。通过设计一组（7,3）线性分组码，来完成对任意序列的编码，根据生成矩阵形成监督矩阵，得到伴随式下，并根据其进行译码，同时验证工作的正确性，最基本的是要具备对输入的信息码进行编码，让它具有抗干扰的能力。1.理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2.掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3.深刻理解信道编码思想与目的，理解线性分组码的基本原理与编码过程。4.能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容已知一个（7,3）线性分组码的校验元与信息元有如下限定关系。设码字为(c6,c5,c4,c3,c2,c1,c0)。2161052104203ccccccccccccc求出标准校验矩阵、Q矩阵、标准生成矩阵，完成对任意信息序列（23个许用码字）的编码。当接收码字分别为(0000000),(0000001),(0000010),(0000100),(0001000),(0010000),(0100000),(1000000),(0100100)时，写出其伴随式S，以表格形式写出伴随式与错误图样E的对应关系，纠错并正确译码，当有两位错码时，假定为c5位和c2位发生错误。2第2章线性分组码编码的分析与实现2.1设计原理1.线性分组码的生成矩阵和校验矩阵（1）线性分组码的性质线性分组码的任意两个码组的和还是许用的码组。码的最小距离等于非零码的最小码重。对于长度为n的二进制线性分组码，它有2n可能的码组，从2n种码组中，可以选择M=2k个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=2k个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。对于码组长度为n、信息码元为k位、监督码元为r＝n－k位的分组码，常记作（n，k）码，如果满足2r－1≥n，则有可能构造出纠正一位或一位以上错误的线性码。（2）生成矩阵和校验矩阵线性分组码码空间C是由k个线性无关的基底1kg，…1g0g，张成的k维n重子空间，码空间的所有元素(即码字)都可以写成k个基底的线性组合，即111001kkCmgmgmg这种线性组合特性正是线性分组码名称的来历。显然，研究线性分组的关键是研究基底、子空间和映射规则，可把子空间和映射关系如图2.1所示：图2.1码空间与映射用ig表示第i个基底并写成n1矩阵形式，01)2()1(,,,,iininiiggggg，再将k个基底排列成k行n列的G矩阵，得：k维n重码空间Ck维k重信组空间mn维n重空间nVn-k维n重对偶空间DGH3(1)(1)(1)1(1)01101(1)11100(1)0100,,,knkkknngggGggggggggg由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k，当信息元确定后，码字仅由G矩阵决定，因此称这nk矩阵G为该kn线性分组码的生成矩阵。基底不是唯一的，生成矩阵也就不是唯一的。事实上，将k个基底线性组合后产生另一组k个矢量，只要满足线性无关的条件，依然可以作为基底张成一个码空间。不同的基地有可能生成同一个码集，但因编码涉及码集和映射两个因素，码集一样而映射方法不同也不能说是同样的码。基底的线性组合等效于生成矩阵G的行运算，可以产生一组新的基底。利用这点可使生成矩阵具有如下的“系统形式”：0001)1(01011)1(10)1(1)1()1)(1(1000010001pppppppppPIGknknkkknkk这里P是knk矩阵；kI是kk单位矩阵，从而保证了矩阵的秩是K。与任何一个kn,分组线性码的码空间C相对应，一定存在一个对偶空间D。事实上，码空间基底数k只是n维n重空间全部n个基底的一部分，若能找出另外kn个基底，也就找到了对偶空间D。既然用k个基底能产生一个kn,分组线性码，那么也就能用kn个基底产生包含kn2个码字的knn,分组线性码，称knn,码是kn,码的对偶码。将D空间的kn个基底排列起来可构成一个nkn矩阵，将这个矩阵称为码空间C的校验矩阵H，而它正是knn,对偶码的生成矩阵，它的每一行是对偶码的一个码字。C和D的对偶是互相的，G是C的生成矩阵又是D的校验矩阵，而H是D的生成矩阵，又是C的校验矩阵。由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。因此，kn,线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交4于校验矩阵H的任意一个行矢量，即0TCH。由于生成矩阵的每个行矢量都是一个码字，因此必有0TGH。对于生成矩阵符合“系统形式”G的系统码，其校验矩阵也是规则的，必为：knIQH上式中的负号在二进制码情况下可以省略，因为模二减法和模二加法是等同的。（3）信息码元及对应码字的关系（n，k）码字中的任一码字ic，均可以由这组基底的线性组合生成，即12iinnnkcmGmmmG式中12innnkmmmm的是k个信息元组的信息组，因此其信息码元及对应码字的关系如表一所示：表2.1信息码元及对应码字关系信息组码字000000000000100111010100100111011011101010010011101011010011110110100111111101002.线性分组码的伴随式与译码（1）码的距离及检错能力两个码字之间，对应位取之不同的个数，称为汉明距离，用d表示。一个码的最小距离mind定义为(,)minmin,,,(,)cicjijddjjccnk,两个码字之间的距离表示了它们之间差别的大小。距离越大，两个码字的差别越大，则传送时从一个码字错成另一码字的可能性越小。码的最小距离愈大，其抗干扰能力愈强。任何最小距离mind的线性分组码，其检错能力为1mind纠错能力t为521mindINTt最小距离mind表明码集中各码字差异的程度，差异越大越容易区分，抗干扰能力自然越强，因此成了衡量分组码性能最重要的指标之一。估算最小距离是纠错码设计的必要步骤，最原始的方法是逐一计算两两码字间距离，找到其中最小者。含k2个码字的码集需计算2122kk个距离后才能找出mind，费时太多，实用中还有一些更好更快的方法。线性分组码的最小距离等于码集中时非零码字的最小重量，即iCwdminmin0iiCCC及式中，符号iwc表示ic重量（1的个数）。这里利用了群的封闭性，由于分组码是群码，任意两码字之和仍是码字，即CCCCikj。因此任意两码字间的汉明距离其实必是另一码字的重量，表示为成下面公式形式。ikjikjkiCwCCdCwCCwCCdmin,min,,。于是可将最小距离问题转化为寻找最轻码字问题，含k2个码字的码集仅需计算k2次。码的检错能力取决于码的最小距离，但还需说明的另一点是码的总体检错能力不仅仅与mind有关。检错能力t只是说明距离t的差错一定能纠，并非说距离大于t的差错一定不能纠。事实上，如果有2k个码子，就存在2212kk个距离，这并非相等的。比如最小距离min3d，检错力1t，是由码21CC的距离决定，只要2C朝1C方向偏差大于1就会出现译码差错；然而若2C朝3C方向偏差3，译码时仍可正确地判断为2C而非3C。可见，总体的、平均的纠错能力不但与最小距离有关，而且与其余码距离或者说与码子的重量分布特性有关，把码距（码重）的分布特性称为距离（重量）谱，其中最小的重量就是mind。正如信息论各符号等概时熵最大一样，从概念上可以想象到:当所有码距相等时是（重量谱为线谱）码的性能应该最好；或者退一步说，当各码距相当不大时（重量谱为窄谱）6性能应该叫好。事实证明确实如此，在同样的mind条件下，窄谱的码一般比宽谱的码更优。纠错重量谱的研究具有理论与现实意义，不仅仅是计算各种译码差错概率的主要依据，也是研究码的结构、改善码集内部关系从而发现新的好码的重要工具。但目前除了少数几类码如汉明码、极长码等的重量分布已知外，还有很多码的重量分布并不知道，距离分布与性能之间确切的定量关系对于大部分码而言尚在进一步研究当中，特别当n和k较大时，要得出码重分布是非常困难的。重量谱可以如下多项式来表示，称为重量算子，即234012341nnnniiAxAAxAxAxAxAxAx式中的含义：在码长n的码集里，包括重量为0的码子0A个（线性码一定包含一个重量为0的全0码），码重为1的码字1A个，，重量为n的码字nA个。（2）伴随式与译码码字1210,,,,nCcccc在传输过程中受到各种干扰，接收端收码1210,,,,nRrrrr已不一定等于发码C，两者间的差异就是差错，差错是多样化的，我们定义差错的式样为差错图样E,即110111100,,,,,,nnnEeeeRCrcrcrc对于二进制码，模2减等同模2加，因此有mod2ERCRCE及利用码字与校验矩阵的正交性TCH，可检验收码R是否错误,即000TTTTTTRHCEHCHEHEHEH定义TRH运算结果为伴随式S,即110,,,TTnkSsssRHEH可见，虽然R本身与发码有关，但乘以TH后的伴随式TTRHSEH仅与差错图E有关，只反映信道对码字造成怎样的干扰而与发什么码C无关了。可以先利7用收码R和已知的H算出的伴随式S；再利用S算出差错图样E。这种思路下的编译码过程如图所示。在此过程中，TRH和RE的计算都是确定性的，而从S计算E却带有随机性。这是因为伴随式S是一个重失量，二进制时只有种肯那个的组合，而差错图样E是n重失量，因此S与E不存在一一对应关系。假设接收端收到的码字为R，那么它和原来发送端发送的码字C之间就有可能存在着误差。即在码组0123456aaaaaaaR中的任意一位就有可能出错。这样我们在接收端接收到一个码组是就有可能判断错发送端原来应该要表达的意思。为了描述数据在传输信道中出现错误的情况，引入了错误图样E，在错误图样中，0代表对应位没有传错，1代表传输错误。实际上错误图样E就是收序列与发送序列的差。所以在译码中用接收到的码字R模尔加错误图样E就可以得到发送端的正确码字R。因此译码的过程就是要找到错误图样E。定义：校正子STTTTHEHEHCHECHRS因为A是编得的正确码字。根据前面所叙述，它和监督矩阵的转置相乘为0。显然，S仅与错误图样有关，它们之间是一一对应的关系。找到了校正子S，也就可以找到E。而与发送的码字无关。若0