信息论与编码第6

《信息论与编码第6》由会员分享，可在线阅读，更多相关《信息论与编码第6（107页珍藏版）》请在金锄头文库上搜索。

1、第6章线性分组码 第第6章线性分组码章线性分组码 6.1线性分组码的基本原理线性分组码的基本原理 6.2线性分组码矩阵表述线性分组码矩阵表述 6.3线性分组码的编码及译码线性分组码的编码及译码 6.4汉明码及其他纠错码汉明码及其他纠错码 念九赫欠秤筛侩阳比汐倚豆涎殃施谚尿俯狞谱蛛埠憾魏苹解惭愧诗擎碗讫信息论与编码第6信息论与编码第6第6章线性分组码 6.1线性分组码的基本原理线性分组码的基本原理 6.1.1基本概念基本概念在通信系统中，为了能在接收端发现和纠正信息传输中产生的错误，发送端需要对所传输的数字信息序列进行编码。首先，把信息序列按一定长度分成若干信息码组，每组由相继的k位信息数字组成

2、；然后，编码器按照预定的线性运算规则(可由线性方程组来规定)把信息码组变换成n(nk)重码字，如图61所示。 腆萄氰喀页鼎刘子驼鼓彤恕脸疗款野辅婆墓穗约羊韭氰矗庄瞥拐蜂材烬耍信息论与编码第6信息论与编码第6第6章线性分组码 图61线性分组码编码器烬蚜劫蚕疑滤硷嫂冗涣砚洽选鸽房脉软哪姆酪中划屉毫昌芜汤皋款目抗加信息论与编码第6信息论与编码第6第6章线性分组码 n-k个附加码元是由信息码元的线性运算产生的,此码叫做（n,k）线性分组码。如果一个(n，k)线性分组码的数域为GF(p)，即每一个码元可能有p种取值，则信源可发出pk种不同的消息组。为使接收端对码字惟一可译,即当从n位长的码字中译出k位的

3、消息时，消息组与码字之间应有一一对应的关系，因此编码器至少要存储pk个码字才能实现消息到码字的变换(当k比较大时，这种编码器就显得有些不切实际)。为了压缩编码器的存储容量，通常对编码器附加一个线性约束条件，使得线性码的校检位与信息位之间呈线性关系。对于二进制码，(n，k)线性分组码(以后简称为(n，k)码)共有2k个码字，它们构成k维子空间的主要特征是：在加法运算下满足封闭性；在2k个码字中只有k个是线性独立的。 终严脊颇圭靠克互悟坛齐富闰邹桐点疯栋骤表滥利煮壶潘埔弄妆菊铀呼莎信息论与编码第6信息论与编码第6第6章线性分组码 (n，k)码除具有封闭性外，还满足加法交换律和加法结合律。因为(n，

4、k)码的pk个码字集合构成可交换的加法群，所以线性码又称为群码。对(n,k)码通过预定的线性运算，可将长为k位的信息码组变换成n(nk)重的码字。由pk个信息码组编成的码字集合称为(n,k)码许用码字,由pn-pk个除了许用码字之外的码字集合称为禁用码字。 冗窜画楚痒喜痉藉圈痘内珐淆信易乓秃交污膳咀僳茧蝎拱训兔绳盲医姐蹈信息论与编码第6信息论与编码第6第6章线性分组码 码组是所有码字的集合。一个n重的码字C可以用矢量C=cn-1cn-2c1c0来表示，所以码字又称为码矢。对(n，k)线性码，用Rkn表示码字中信息位所占的比重，叫做编码效率或编码速率，简称码率。它说明了信道利用效率，所以也叫做传

5、信率。R越小，冗余度就越大,即在一个码字中添加给每个信息符号的冗余符号越多。一个码组的冗余符合越多，检错和纠错的能力越强，但也降低了传输信息的实际速率。R越大，码的效率也就越高或传信率越高。R是衡量码性能的一个重要参数。 亢联鹰贮黎赠照淆夺躲涂夏闪襄卫草潦攻戒副夫消玲缠候递湃摩搂略悍辅信息论与编码第6信息论与编码第6第6章线性分组码 如上所述，信道编码就是给已知信息组按预定规则添加监督码元，以构成码字。在k个信息元之后附加r(rnk)个监督码元，使每个监督元是其中某些信息元的和。例如，信息分组长度k3，在每一信息组后加上4个监督元，构成(7，3)线性分组码。设该码的码字为c6c5c4c3c2c

6、1c0，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元可按下面方程组计算： （6） 毯梦煎伤慢尿棚争获迈溉矗圆腔亨扎输喊纷纫贯氛赞跑笛呵暇壹锻片德冯信息论与编码第6信息论与编码第6第6章线性分组码 式(61)为一线性方程组，它确定了由信息元得到监督元的规则，所以称为监督方程或校验方程。由于所有码字都按同一规则确定，因此式(61)称为一致监督方程或一致校验方程，所得到的监督元称为一致监督元或一致校验元，这种编码方法称为一致监督编码或一致校验编码。因为一致监督方程是线性的，亦即监督元和信息元之间是线性运算关系，所以由线性监督方程

7、所确定的分组码是线性分组码。利用式(61),每给出一个3位的信息组，就可编出一个码字，如表61所示。 舱胳氰吴郭恃乖春戍垫姥仿尹揍跋矿门昧龄材沃讹陕槽炯麓杆吭狂众危舒信息论与编码第6信息论与编码第6第6章线性分组码 表61（，）分组码编码表 齐梆茶样予逐嚼滔阅惧北胜谤重嗡孺由获酱曝乱教糜弗堤伺声膛谍勋隙渡信息论与编码第6信息论与编码第6第6章线性分组码 6.1.26.1.2码的重量和码的距离码的重量和码的距离在信道编码中，定义码字中非零码元的数目为码字的汉明（Hamming)重量，简称码重。例如“010”码字的码重为1，“011”码字的码重为2。把两个码字之间对应码位上具有不同二元码元的位数定

8、义为两码字的汉明距离，简称码距。在一种编码中，任意两个许用码字间距离的最小值，即码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以dmin表示；在非零码字中，重量最小者称为该码的最小汉明重量。 刀睁拆朵嘘盒巡莆枉辆蔚锄王搪刻隙觉脊墙谆键球食霹亮倔像束叠栋奠嚼信息论与编码第6信息论与编码第6第6章线性分组码 通常，用d(C1，C2)表示两个n重C1、C2之间的汉明距离，则汉明距离有以下三个性质：(1)对称性：d(C1，C2)d(C2，C1)；(2)非负性：d(C1，C2)0；(3)满足距离三角不等式：d(C1，C2)d(C1，C3)d(C3，C2)。 驻儿蛹由寨半啥挥鹃裕出料古地殿

9、断筛臆必箔蛮哲殷货誊新泳供寝滔都极信息论与编码第6信息论与编码第6第6章线性分组码 最小距离dmin与码率R是码的两个最主要的参数， dmin表示了码的纠错能力。以后用（n，k，dmin）表示最小距离为dmin，码率为Rkn的线性分组码。纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。在3位二元码字中，如8种码字都作为许用码字时，任两组码间的最小距离为1，称这种编码的最小码距为1，记作dmin1。已知(n，k，d)线性分组码的最小距离dminnk1。若系统码的最小距离dminnk1，则称此码为极大最小距离可分码，简称MDS码。 孜的据描屉漂诸擅撤游绊

10、瓤伴才幼庄娠衫眺脓单施桐甸傲励李潮宇控仟蝇信息论与编码第6信息论与编码第6第6章线性分组码 6.1.36.1.3码的检错及纠错能力码的检错及纠错能力下面讨论码的检错、纠错能力与最小码距的数量关系。在一般情况下，对于分组码有以下结论：(1)若一个码组内能检测e个错码，则要求最小码距为 dmine1 (62) 或者说，若一种编码的最小距离为dmin，则它最多能检出dmin-1个错码。式（62）可以通过图62（a)来说明。图中C表示某码组，当误码不超过e个时，该码组的位置将不超出以C为圆心、e为半径的圆(实际上是多维的球)。只要其他任何许用码组都不落入此圆内，则C码组发生e个误码时就不可能与其他许用

11、码组相混。这就证明了其他许用码组必须位于以C为圆心，以e1为半径的圆上或圆外，所以，该码的最小码距dmin为e1。 星努方杀天近兑泅苫吭伐挽瓮刘砒氓兑豢啤氢潭岗毛澳雇战汤砧叔俱益砷信息论与编码第6信息论与编码第6第6章线性分组码 图62码距与检错、纠错能力的关系 冀熊构捷酸样循驾搂失装硷且曙审邀鞘徊荒迭到趣谩沼厘轨仓袭贮蹭刃绊信息论与编码第6信息论与编码第6第6章线性分组码 (2) 若一个码组内能纠正t个错码，则要求最小码距为 dmin2t1 (63) 或者说，若一种编码的最小码距为dmin，则它最多能纠正（dmin1）/2个错码。式（63）可以用图62(b)来说明。图中C1和C2分别表示任意

12、两个许用码字，当各自错码不超过t个时，发生错码后两个许用码字的位置移动将分别不会超出以C1和C2为圆心、t为半径的圆。只要这两个圆不相交，则当错码小于t个时，可以根据它们落在哪个圆内而正确判断为C1或C2码字，即可以纠正错误。而以C1和C2为圆心的两个圆不相交的最近圆心距2t1就是纠正t个错误的最小码距了。 洋九旬建这锗萍阶乾瘤嗓樱十缚既沮茧汾试撕堪颐色漆赏赐唱讽拙豌眨窝信息论与编码第6信息论与编码第6第6章线性分组码 (3)若在一个码组内能纠正t个错码，同时也能检测e(et)个错码，则要求最小码距为 dminet1 (et) (-4) 这里所说的能纠正t个错码，同时能检测e个错码的含义是：当

13、错码不超过t个时，码组能自动予以纠正；而当错码超过t个时，则不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。可以用图62(c)来说明式(64)。图中C1和C2分别为两个许用码字，在最不利情况下，C1发生e个错码而C2发生t个错码，为了保证这时两码字不发生相混，则要求以C1为圆心、e为半径的圆必须与以C2为圆心、t为半径的圆不发生交叠，即要求最小码距dminet1。同时，还可以看到当错码超过t个时，两圆也有可能相交，因而码组不再有纠错的能力，但仍可检测e个错码。 娇筷冲榨涟磐队吭埔损霍糯饶煽悬铰缆本碗泅脓摈沏适毡登仅甘媳朵弛固信息论与编码第6信息论与编码第6第6章线性分组码

14、(4)若一个码组内能纠正t个错误和P个删除，则要求最小码距为 (65) 这里所说的删除是指已知错误产生的位置，但不知错误值的大小。 寻察抹虚贞嫉亿肾坛寇养拔地闹沈轩阎称绅镇灸抡叁潜殴尊官甚底述品掸信息论与编码第6信息论与编码第6第6章线性分组码 【例61】已知GF(2)中一个码组的全部码字为 如果将此码用于检错,能检出几位错码?如果将此码用于纠错,能纠出几位错码?如果将此码同时用于检错和纠错,能检出几位错码?纠出几位错码? 000 000,001 110 ,010 101,011 011,100 011,101 101,110 110 致炕姆后貉禾绿耶傲蹦银谭粘害筏棘骨歉冉杉撰摄奖拎桃源歌罚莎

15、娇壮痰信息论与编码第6信息论与编码第6第6章线性分组码 解解由8个码字可得码组的最小汉明距离dmin=3。若检测e个错码，则要求最小码距：dmine1，则e2，此码最多可以检出2位错码；若纠正t个错码，则要求最小码距：dmin2t1，则t1，此码最多可以纠出1位错码；若既能纠正t个错码，同时又能检测e(et)个错码，则要求最小码距：dminet1(et)，则e=2，t=0，此码只能检错，不能纠错。 腑弗役陪体跨弧澡沃巨氮酝钢人挚缄廊贸峙楔撞奈臼蛙贺魄靴倡哥呀皑湍信息论与编码第6信息论与编码第6第6章线性分组码 6.1.4线性分组码的性质线性分组码的性质一个线性分组码具有下述性质：(1)两个属于

16、该码组码字的和仍是一个属于该码组的码字。(2)全零码字总是码组中的一个码字。(3)一个线性码组中两个码字之间的最小距离等于任何非零码字的最小重量。如果两个码字的和是另外一个码字，该两个码字的差也将仍然是一个合法码字。例如，若C1、C2和C3是码字，且C1+ C2 = C3，那么有C3 -C1=C2。所以，对一个线性分组码，全零码字必为一个合法码字。 蕾襟你忻魏束巧撮邀该熙彰侥执菩馋颅查瘩丛洗勺刊碾骚楼夷纫墅女拓懈信息论与编码第6信息论与编码第6第6章线性分组码 【例62】已知GF(2)中码组C=0000,1010,0101,1111是一个分组长度n=4的线性分组码。观察码字之间所有十种可能的和

17、： 0000+0000=0000,0000+1010=1010,0000+0101=0101,0000+1111=1111,1010+1010=0000,1010+0101=1111,1010+1111=0101,0101+0101=0000,0101+1111=1010,1111+1111=0000 它们都在C中，全零码字也在C中。该码组的最小距离为dmin=2。为了验证这个线性码的最小距离，可计算所有码字对（共6对）之间的距离: 显然这个码组的最小距离为2。 哥锰靠数艳窃孤妆也莆雹抱挠串箭胁科寇圣谰劳傅效壕琢辉笨覆糖逐寡黍信息论与编码第6信息论与编码第6第6章线性分组码 设S为一个长度为n

18、且分量在GF(p)上的向量集合。S中所有向量的线性组合构成的集合称为S的线性扩张，记为S。因此线性扩张是由S生成的GF(pn)的一个子空间。给定GF(pn)的任意子集S，可以得到一个由S生成的线性码C=S，它恰好包含下列码字：全零码字;S中所有的字;S中两个或两个以上的字的所有线性组合。 雅雕桌撵畏沧许荷弘耳毯定烦愿持初欣咳匀杰淹想管觉狄巧句吨恭赎凉坛信息论与编码第6信息论与编码第6第6章线性分组码 【例63】设GF(2)中S=1100,0100,0011，S的所有可能线性组合为:1100+0100=1000，1100+0011=1111，0100+0011=0111，1100+0100+00

19、11=1011。因此，C=S=0000，1100，0100，0011，1000，1111，0111，1011。可得该码组的最小距离dmin=1。 当挝琉娘乱炊寐颜癣粗综浓俄否卧肛巫骚殷陆扮诛萨丑躬智动赶舍价兽橱信息论与编码第6信息论与编码第6第6章线性分组码 6.2线性分组码矩阵表述线性分组码矩阵表述 6.2.16.2.1生成矩阵生成矩阵在（n，k）线性分组码中，n表示码长，k表示信息位的维数，也就是子空间的维数，将n个码字位和k个信息位之间的关系写成矩阵形式,即 C CUGUG (66) 佳闽惕铁祈哦蒜路途绒请临警涟起擅师莫卤段俐伊叁轩抚勇鄙家丑耪加裤信息论与编码第6信息论与编码第6第6章线

20、性分组码 式中: G为该线性分组码（n，k）码的生成矩阵，即 （67） 可见G建立了消息与码矢间的一一对应关系，它起着编码器的变换作用。因此C的每一位数字都是消息数字的线性组合。应该指出，一个子空间的基底矢量的选择不是惟一的，所以生成矩阵G的选择也不是惟一的。 繁欺访险淡官诈琢轿招趾椒妄白少厄犬渡敛勿焕个峰驱颖革囚熙铱映敬栽信息论与编码第6信息论与编码第6第6章线性分组码 【例64】已知(7，3)线性分组码，设该码的码字为C=c6c5c4c3c2c1c0，其中c6、c5、c4为信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或“1”，即ciGF(2)。监督元可按式(61)方程组计算

21、。求生成矩阵。解解因为信息位分别为u2、u1、u0，则码元为: c6=u2c5=u1c4=u0c3=u2+u0c2=u2+u1+u0c1=u2+u1 c0=u1+u0 帜诅照瞻酞港踩病浚怂靠讳抗谦恢莽肋侦挽簿攻次虱焉后锌奶递澈窟纂爷信息论与编码第6信息论与编码第6第6章线性分组码 又因为 C=c6 c5 c4 c3 c2 c1 co，U=u2 u1 u0 ，由C=UG，所以 这种形式不同的生成矩阵仅表示消息与码字之间不同的一一对应关系，但2k个消息的集合却对应着同一个（n，k）码的码字空间。 券钙霉鹤帜噶鸽补廉讶伟迄募烫榔狡氟友陨帧榷经轨两腑癸兹可呛硬旗吨信息论与编码第6信息论与编码第6第6章

22、线性分组码 【例65】已知GF(2)中码生成矩阵分别为： 求：G G1和G G2 2分别对应的码字空间？ 鳖豆杂浸凤幸猩算移汉断犁扑暂盆蚂搽橙杀苦戏砂沈莎票蒋契涝狼烫茹律信息论与编码第6信息论与编码第6第6章线性分组码 表表62用不同的生成矩阵得到的线性码用不同的生成矩阵得到的线性码 竣垄竞册爸明腋瘁需裁两拱恳胺瞒博洗馅蕾屑摧谍牢税虎绅嫂拽尉深侯俯信息论与编码第6信息论与编码第6第6章线性分组码 6.2.26.2.2监督矩阵监督矩阵在线性分组码（n，k）中，因为监督元和信息元间是线性关系，若设CT、0T及HT分别为C、0、H的转置矩阵，所以每个码字中r（rnk）个监督元和信息元之间的关系为 H

23、CHCT0 0T 或 CHCHT0 0 （68） H称为(n,k)线性码的一致监督矩阵，即 式中： C Ccn1 cn2 . cl c0。 钠递滦坏株闺逗汪疡账淮箩搞雪铸奔沥垄渐岁腿玉殉韵歧着予薪账黎食狐信息论与编码第6信息论与编码第6第6章线性分组码 【例66】已知(7，3)线性分组码，设该码的码字为C=c6c5c4c3c2c1c0,其中c6c5c4为信息元; c3c2c1c0为监督元，每个码元ciGF(2)。监督元可按式(61)方程组计算。求监督矩阵。解解因为 c6=u2c5=u1 c4=u0 望粳襄脐动恬假眩狭糯棕肋拱臭渗涤恩大嘘田赋轰丙卓扰纸圣赚陪榆蔬抖信息论与编码第6信息论与编码第6

24、第6章线性分组码 则由监督方程得 c3u2u0c6c4c2u2u1u0c6c5c4c1u2u1c6c5 c0u1u0c5c4 因为 北似命涪赦半踞群锋环诸蝇正将缨酚保梭鹤衍氟庶北务耻瘤亏捍恢卵嫂底信息论与编码第6信息论与编码第6第6章线性分组码 6.2.36.2.3等价码及系统码等价码及系统码如果一个线性P元码可由另一个通过下面一种或两种运算得到，则称它们为等价码。该运算为：(1)用非零常量去乘它的分量；(2)对码的位置做置换。 奶卫租鬃虞并鄂茶雇备珊董舷氢纯砖穴伦寥衣娠板曳逼免话豺辗价菩督米信息论与编码第6信息论与编码第6第6章线性分组码 定理定理6 61 1两个kn矩阵,若一个可以由另一个

25、通过一系列下述变换得到，则它们生成的GF(p)上的(n，k)线性码等价：（1）对行置换； (2)对行乘以一个非零常量； (3)把一行乘以一个常量然后加到另一行上；（4）对列置换；（5）对任意列乘以一个非零常量。 竖珐料届揉褥荷河虏溉鳖柄档红衣防绞出铲筑疚婆寒罪荆秉厂蓬苑值挂指信息论与编码第6信息论与编码第6第6章线性分组码 前三种运算（只是行变换）保留了生成矩阵的行的线性独立性，变换只是改变了基。最后两种运算（列变换）把矩阵变成能生成等价码的一个矩阵。由例65中G2生成的码，因其前k位与消息完全相同，则称这种码为系统码。系统码的编码器仅需存储k(n-k)个数字(非系统码要存储kn个数字)，译码

26、时仅需对前k个信息位纠错即可恢复消息。由于系统码的编码和译码都比较简单，而且性能也与非系统码一样，因此系统码得到了十分广泛的应用。 禄马铰眯勾苍狠听鼓骂级够庸组足物啪渣瞬毗庞汪剥苹劈嘴铂崭北冤苦奈信息论与编码第6信息论与编码第6第6章线性分组码 系统码的生成矩阵可用分块矩阵表示为 G GI IkP P (610) 式中：Ikkk阶单位方阵；Pk(n-k)阶阵。由此G生成的码称为系统码，否则称为非系统码。 显然,在系统码的码组 C(cn1，cn2，c0)中，前k位(cnl，cnk)(u1，uk)是信息位，后nk位(cnk，c)称为码字的校验位。 炼苞体互烟婚昧乎题唬西吻苦昭核闰肮麻鬃旗束摆寻吴浴

27、苦肯桃纶匹嘘吓信息论与编码第6信息论与编码第6第6章线性分组码 对上节所讲的一致监督矩阵H各行实行初等变换，并将后r列化为单位子阵，则 H HQ QI Ir (611) 把变换所得的后面r列是一单位子阵的监督矩阵H称为监督矩阵H的标准形式。H阵的一般形式可通过行的线性变换化成标准形式。利用标准形式的H阵进行编、译码很方便，所以H阵的标准形式是一种常用形式。显然，H阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的和为0，因而,H的标准形式还说明了相应的监督元是由哪些信息元决定的。H阵的r行代表了r个监督方程，也表示由H所确定的码的码字有r个监督元，那么为了得到确定的码，r个监督方

28、程(或H阵的r行)必须是线性独立的，这就要求H阵的秩为r。若要把H阵化成标准形式，只需检查单位子阵的秩，就能方便地确定H阵本身的秩。 讶蔚酉诈滴筋援频苑裙铲靡砒济毖磅囤稳涝星臣碰吊瓤崩抵兑锦斩他氛臂信息论与编码第6信息论与编码第6第6章线性分组码 在前面我们讨论了线性分组码的生成矩阵和监督矩阵，它们二者之间有无联系呢？回答是肯定的。(n，k)线性码的G和H之间有非常密切的关系。由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HCT0T，则有：因此，线性码的生成矩阵G和监督矩阵H的行矢量彼此正交。那么，由生成矩阵的行矢量张成的k维子空间和由监督矩阵行矢量张成的nk维子空间互为零空间。由式(

29、610)、(611)及式(612)得： HGT0T 或 GHT0 (612) GHGHTI Ikp pQ QI IrTQ QTp p0 0 （613） 盟始警忻链烽恐哭件姐臼蛙惑貌茵敢瑚菱咕阵砰蝶秸穆眩沙咐氦踏跋僳秘信息论与编码第6信息论与编码第6第6章线性分组码 所以 由此可得： G GI IkP PI IkQ QT 或 H HQ QI Irp pTI Ir因而线性系统码的监督矩阵H和生成矩阵G之间可以相互直接转换。例如，已知(7，4)线性系统码的监督矩阵为 P PQ QT 或P PTQ Q （614） （615） 宗耐滇馈碧坟奸诲粳斤涪槛逝植妓孵挥肘保赴溶惰掇旺位凑晦葵截戌谭藤信息论与编码

30、第6信息论与编码第6第6章线性分组码 可直接写出它的生成矩阵为 汉艰县肆员棺矣微盛粒捷熔丁舅固旅哉捏近栋情尸理挫嘘翅相痕殊汝苟瓷信息论与编码第6信息论与编码第6第6章线性分组码 6.2.4对偶码及缩短码对偶码及缩短码对一个(n，k)线性码CI，由于HGT0T，如果以G作监督矩阵，以H作生成矩阵，可构造另一个码CJ，码CJ是一个(n,nk)线性码，则称码CJ为原码CI的对偶码。显然，由于对偶码是原码的生成矩阵和监督矩阵互换后所构成的码，所以对偶码的码字与原码的码字彼此正交，而它们的码字集合分别构成的两个子空间是互为零化空间。例如，(7，4)线性码的对偶码是(7，3)码，那么(7，3)码的监督矩阵

31、H（7，3）是(7，4)码的生成矩阵G（7，4），即 舔式濒酸一猎淄妨栽墒鹃聘霍篙灸悦识勒峨硒雌蜒逛砂暮逾轻铲磺隘胜轿信息论与编码第6信息论与编码第6第6章线性分组码 而（7，3)码的生成矩阵G（7，3)是(7，4)码的监督矩阵H（7，4），即 H（7，3）G（7，4）H H(7，4) G G（7，3） 晶予齿帆吴近榨子亥旦枚吸短虹羡骇擦侗序柴抽怎僵案浪盂愿赚鉴擒可蒋信息论与编码第6信息论与编码第6第6章线性分组码 为了将由原码的监督矩阵和生成矩阵交换后所得对偶码的生成矩阵和监督矩阵化成标准形式，需在交换后对矩阵的行作初等变换，此变换过程可简单地将单位子阵由前移到后，或由后移到前，无需作繁琐的

32、运算。由前面的讨论可知，若已知消息U，可从G求出监督元，也可从H求得同样的监督元。因此线性分组码的性质完全由G或H决定。对于一个具体的矩阵来说，它既可以作为生成矩阵将消息变换成码字，也可作为一致校验矩阵将消息变换成另一种码字，这样所得的两种码称为对偶码，前者如果是(n，k)码，那么后者一定是(n，n-k)码。 凉载宇湍坠颁简权垄娇誊额兢阴菏罗灵篓非矩萄邵购惺佳纺场领川桂震从信息论与编码第6信息论与编码第6第6章线性分组码 G（7，3）和H(7，4)这两个矩阵利用初等交换可以互相转化，根据矩阵代数理论可知它们是等价的。G(7,3)是(7,3)码生成矩阵的标准形式，H(7,4)是(7，4)码一致校

33、验矩阵的标准形式，两者可以编出互为对偶码的(7，3)码和(7，4)码，如表63和表64所示。在(7，3)码的码字集合中，如果将最左面一位为0的消息和对应的码字挑选出来，并把最左面的0删去，则它们构成(6，2)线性分组码，如表65所示。这种码叫缩短码。 新灰烙婴疏却籽签干氰邯粕捷转费神阔恤缀遍犬炭康姓卯妊毫恒橡疯齐噎信息论与编码第6信息论与编码第6第6章线性分组码 表63G（7，3）编出的（7，3）码 磋萧题带李惮径杯讶龋蝇铅熏抄春割回杠励鸯扁词府秸笑窄凤哈跺必赛协信息论与编码第6信息论与编码第6第6章线性分组码 表6-4 H H（7，4）编出的（7，4）码 冉殃叭条庆撞鞍砚嫌溅建伤降箩痈法育仰

34、辉排荆颇靴筑恿效设弦势领症翱信息论与编码第6信息论与编码第6第6章线性分组码 表65缩短的(6，2)码 撒激靳栏柞叹墓冉固杏连莲芳辊存晾岸矽往戍赵斥参扒袭莆竿游麓绚诵蹈信息论与编码第6信息论与编码第6第6章线性分组码 求缩短码的生成矩阵和一致监督矩阵是很方便的，如(6，2)码的生成矩阵就是将(7，3)码的生成矩阵的最上面一行和最左面一列删去，将(7，3)码的一致校验矩阵的最左面一列删去就是(6，2)码的一致监督矩阵，即 拿唤眠平旭酋辩层伙雏氟涤交卵耻故李丰枫原品肆育龄懂婉辣舱硅执伐副信息论与编码第6信息论与编码第6第6章线性分组码 6.3线性分组码的编码及译码线性分组码的编码及译码 6.3.1

35、6.3.1线性分组码的编码线性分组码的编码(n，k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(nk)的码字,即先求出信息元和码元之间的关系,再利用此关系构造编码电路。若由监督矩阵和生成矩阵求出的信息元和码元之间关系的结果是一致的，则编码电路也相同。因为生成矩阵和监督矩阵只是以不同方式来描述同一码的结构而已。 券玫泼淖喳窥宏陕谚均优倍污氯豌找把湾亩蛾砂账汐惶促旧撕欢倒六元汛信息论与编码第6信息论与编码第6第6章线性分组码 下面利用监督矩阵来构造(7，3)线性分组码的编码电路。设二元码字为 Cc6c5c4c3c2c1c0 码的监督矩阵为 膀澡摈掩茸间磷赁浸籍窖宴感

36、歉系乙藉瘤芬莱舞血种险须趋锈蚁北庞假雅信息论与编码第6信息论与编码第6第6章线性分组码 图63线性系统码编码电路 屉夸狄马仟控随限胎笼鳃誊寅英最爷帐堪阀阑诫解蓟霞眶谢讹翔茶巡伤秀信息论与编码第6信息论与编码第6第6章线性分组码 6.3.26.3.2标准阵列及译码标准阵列及译码设C是GF(p)上的一个(n，k)码，a是长为n的任意向量。则将集合 （616） 称为C的一个陪集(Coset)。当(a-b)C时，称a和b属于同一个陪集。 苟使聚罗僧暑龋钾地色藏砖受慈付审州篓捎臻蜡盛氟钉凉饱秀奢拐卿摩疗信息论与编码第6信息论与编码第6第6章线性分组码 定理定理61假设C是(p)上的一个(n，k)码，则(

37、1)任意长为n的向量b都属于C的某个陪集；(2)每个陪集恰好包含pk个向量；(3)两个陪集或者不相交或者完全重合(不可能部分相交)；(4)若a+C是C的一个陪集，且b(a+C)，则b+C=a+C。证明证明(1)b=b+0b+C。(2)注意到xa+x是Ca+C上的一一映射，因此a+C含有的元素个数与C相同，即等于pk。 拈饮品众蜀缩拯糟娄作坟补组咬盏郝透那巢鲁簧葵版坦审顾程各藤昼旷噬信息论与编码第6信息论与编码第6第6章线性分组码 (3)假设a+C与b+C相交，即它们至少有一个公共向量。设v(a+C)(b+C)。则必存在x,yC使 （617） （618） 其中,zC（因为两个码字的差也是一个码字

38、）。固有 （619） 类似地，可以证明(a+C)(b+C)。由此可得（b+C）=（a+C）。 攘夺滦然顷淑珐构簇捆蛛还必讼稿衅消具疲袭蝴壹贤哇句呻沦马馋审协柴信息论与编码第6信息论与编码第6第6章线性分组码 （4）因为b(a+C)，这表明对某个xC有b=a+x。对任意(b+y)(b+C)有b+y=(a+x)+y=a+(x+y)(a+C) （620）因此(b+C)(a+C)。另一方面，对任意(a+z)(a+C)，有a+z=(b-x)+z=b+(z-x)(b+C) （621）因此(a+C)(b+C),从而b+C=a+C。证毕一个陪集中具有最小重量的向量称为陪集首(CosetLeader)。如果有多

39、余一个向量具有最小重量，则从中随机选择一个定为陪集首。 趾侄椭栓匣小札弥咬敌尝毡迷绒亏江浴窖眯雨敝安咸萤哩板滓销诫捅郑蓑信息论与编码第6信息论与编码第6第6章线性分组码 【例67】设C为一个二元（3，2）码，其生成矩阵如下： 码字C=000,010,101,111。C的陪集为: 诌出墅猜仿醚版浚恃菇再盗鼓垛箱玄迎弓军镣斑栖澈遮棱乃信至溺撕夏铺信息论与编码第6信息论与编码第6第6章线性分组码 所有的8个向量都被这两个陪集覆盖了。如果a+C是C的一个陪集而且b(a+C)，则有b+C=a+C。因此，上面已经列出了所有陪集。为了方便演示，以下写出全部的可能情况： 由此可以看到所有陪集已经被覆盖了。 盼

40、审墓殊宠几毙胡琳花嘎废肤熔化受敞池搔疮表茎炽饥缅逊澄翰划腾胜励信息论与编码第6信息论与编码第6第6章线性分组码 因为两个陪集或不相交或重合，所以GF(qn)上的所有向量可以写为 一个(n,k)码组C的标准阵列(Standard Array)是一个GF(pn)上全部向量的pn-kpk阵列,它的第一行由码组C构成(0码字在最左边),其它行是陪集ai+C,都以相应次序排列,陪集首放在最左边。 t=qn-k-1 赤尔类寂镰迸篆劳秦翟缴炮絮枷鞠宁朗制评请朗销馏樊投宝玉寝翟狄匡丙信息论与编码第6信息论与编码第6第6章线性分组码 设二元(n，k)线性码用来纠错，发送码字取自于2k个码字集合Ci。码字经信道传

41、输后，接收码字R可以是2n个n重矢量中的任一个。任何译码方法，都是把2n个n重矢量划分为2k个互不相交的子集D1，D2，D2k，使得在每个子集中仅含一个码字。根据码字和子集间一一对应关系，若接收字Rx落在子集Dx中，就把Rx译为子集Dx含有的码字Cx。所以，当接收字R与实际发送码字在同一子集中时，译码就是正确的。 丧籽发愿奥掉少儿睡维率丛丫湖阀雷里寂愚咒缄灿蹄坝砍械馋牟帐舔枉兵信息论与编码第6信息论与编码第6第6章线性分组码 对给定的（n，k）线性码，将2n个n重划分为2k个子集的一种方法是构造所谓的“标准阵列”。其方法如下：先将2k个码字排成一行，作为“标准阵列”的第一行，并将全0码字C10

42、00放在最左面的位置上；然后在剩下的2n2k个n重中选取一个重量最轻的n重E2放在全0码字C1的下面，再将E2分别和码字C2，C3， 相加，放在对应码字下面构成阵列第二行，在第二次剩下的n重中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码字上，得到第三行；，继续这样做下去，直到全部n重用完为止，按上述方法所构造的标准阵列如表6-6所示： 照渺魂播筏朽恐协绘取钩南江了摘酌同劝勾关甸挨筹夏茸啤讥隋炳炉劫椽信息论与编码第6信息论与编码第6第6章线性分组码 表表66(n，k)线性码的标准阵列线性码的标准阵列 C C1（0）C C2C CiE E2E E2C C2E E2C CiE

43、E2E E3E E3C C2E E3C CiE E3C C2 C Ci踩展诌萤茫姨吠肯溅崖劈斥馏捶酮褂束总杂利宋暮范谱屈谢午屁椒穴胚脚信息论与编码第6信息论与编码第6第6章线性分组码 定理定理6-2 在标准阵列的同一行中没有相同的变量，而且2n个n重中任一个n重在阵列中必出现一次且仅出现一次。 证明证明 因为阵列中任一行都是由所选出某一n重变量分别与2k个码字相加构成的，而2k码字互不相同，它们与所选变量的和也不可能相同，所以在同一行中没有相同的变量。在构造标准阵列时，是用完全部n重为止，因而每个n重必出现一次。另外，假定某一n重X出现在第y行第i列，那么XEyCi，又假设X出现在第m行第j列

44、，则有XEmCj，yy)的第一个元素，而按阵列构造规则：后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规则相矛盾。因而任何n重不可能在阵列中出现两次。证毕证毕 峡懈娩请审衰马拇加设畸西觉竭汤愧惮民澜丑荆甚惭梢哇巍白错企迂岿辰信息论与编码第6信息论与编码第6第6章线性分组码 由上可知，(n，k)线性码的标准阵列有2k列(和码字数相等)，2n2k2nk行，且任何两列和两行都没有相同的元素，即列和行都不相交。标准阵列的每一行叫做码的一个陪集， 每个陪集有相同的错误图样。每个陪集的第一个元素叫做陪集首，每一列包含2nk个元素，最上面的是一个码字，其它元素是陪集首和该码字之和，例如第j列即

45、为： 若发送码字为Cj，信道干扰的错误图样是陪集首，则接收字R必在Dj中，此时接收字R正确译为发送码字Cj；若错误图样不是陪集首，则接收字不在Dj中，则译成其它码字，造成错误译码。因而当且仅当错误图样为陪集首时，译码才是正确的。所以，这2nk个陪集首称为可纠正的错误图样。 DjCj，E2Cj，E3十Cj， ， Cj (623) 逻钥驾息麻扛简茵喉炸瞧霸搬辉老蒙樟疗墙俯焰品夫拟挨阶阿苔拭架椒塞信息论与编码第6信息论与编码第6第6章线性分组码 由于陪集首是可纠的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首。已知重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量

46、最轻的n重码字作陪集首。这样，当错误图样为陪集首(可纠的错误图样)时，接收码字与发送码字间的距离(等于陪集首)最小。因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码，所以，标准阵列译码法也是最佳译码法。 机见了蝴秋癸谚井焚拿饿丽赡偷自唾地址庞褐厦装象铬氨羚谭心徘渐蹋注信息论与编码第6信息论与编码第6第6章线性分组码 【例68】已知二元(4,2)线性分组码生成矩阵为 求:(1)系统的标准阵列。(2)若接收码字R=1010,错误图样E=0100,求对应的码字,并判断译码有无错误。(3)若接收码字R=1010,错误图样E=0110,求对应的码字,并判断译码有无错误。 耻谈鞋容贱请苑

47、电娥疙叠吁献谁傅诣奎朝尔臭齐灵省录蛔玉邪要戊露捞联信息论与编码第6信息论与编码第6第6章线性分组码 解解(1)由C=UG得系统的码组为0000,0111,1001,1110所构造的标准阵列如表67所示。 表表67（4，2）线性码的标准阵列）线性码的标准阵列 愁历饵谴尉沽偏龟辞役健盏滁棵民陋究祟切到搬承砸泡凄储阮唯映也谴迢信息论与编码第6信息论与编码第6第6章线性分组码 标准阵列中的第一行是4个码字，其中码字0排在左边，然后在剩下的12个码字中，挑选一个重量最小的码字(例如1000)作为第二行的陪集首。将1000与第一行中所有的码字相加，就得到第二行。接着，在剩下的8个矢量中选取0100为第三行

48、的陪集首，等等。在这个例子中，陪集首的重量皆为1，但对于其他的码，陪集首的的重量可能为2，3，4，。 旬椎廊汾辉容陨恢羚蓄退靡瀑张声碗妆赎啪腑孟艇番匪曰晤矿杜侍暑庙掷信息论与编码第6信息论与编码第6第6章线性分组码 (2)当接收字R1010时，在表67的第3行第4列中找到了它，于是就可以把R译成位于第4列的码字U1110。显然，位于第3行的陪集首0100是错误图样E，因此译码正确,表示信道第2位有错。由此可见，译码正确与否的关键在于信道错误向量是否是陪集首。因为将R译为与它最接近的码向量U，所以符合最大似然译码准则。(3)当接收字R1010时，在表67的第3行第4列中找到了它，于是就可以把R译

49、成位于第4列的码字U1110。显然，位于第3行的陪集首0100不是错误图样E=0110，因此译码不正确。由此可见，译码正确与否的关键在于信道错误向量是否是陪集首。因为将R译为与它最接近的码向量U，所以符合最大似然译码准则。 酗输涡爆培椒倘绞老妹扶开焙胆善蔬牌好了似很诲坯识吹例劫钓林诵菌铆信息论与编码第6信息论与编码第6第6章线性分组码 【例69】设二元(6，3）码的生成矩阵为 表68（6，3）线性码的标准阵列 班炭饵作效凑冗偏酋秩总靳沽泽伪苯动恬咐帛股饭秘魂白酝抓道介愁搏杠信息论与编码第6信息论与编码第6第6章线性分组码 求：(1)若接收码字R=111011,错误图样E=010000,求对应的

50、码字,并判断译码有无错误。(2)若接收码字R=100111,错误图样E=001100,求对应的码字,并判断译码有无错误。解解（1）若接收字R111011，查表68可知它所在子集的估值101011，错误图样E010000和陪集首相同，因此译码正确。表克肘庸鸯氛莽赁碑冶赫吉懊氖悍倡褂膏凤薪宿沙易鸦忌霄梗疚募磷匪百信息论与编码第6信息论与编码第6第6章线性分组码 （2）由于R100111，与此R对应的100110，但它的错误图样为E001100，它不在陪集首，属于错误译码。 当n很大时，用标准阵列译码要存储2n个n重码字是不实际的。如当C为码长是100的二元码时，则C的标准阵列由2100个阵元组成，

51、译码器必须存储它们，译码时还必须从中搜索接收码字R，这在工程实践上是很难实现的。然而利用伴随式译码可以使标准阵列译码过程得到简化。 台禁验麓贾泌斋股欧达虏掖舵鄂糠炊桑藐刽琳种青盆破病产桨狄腑汐侵楔信息论与编码第6信息论与编码第6第6章线性分组码 6.3.3 伴随式及错误检测用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收字R R后，可用监督矩阵H H来检验R R是否满足监督方程，即HRHRT T0 0T是否成立。若关系式成立，则认为R R是一个码字，否则判为码字在传输中发生了错误。因此，HRHRT的值是否为0 0是检验码字出错与否的依据。 把S SRHRHT或S STHRHRT，称为接收字

52、R R的伴随式(或监督子，或校验子)。 设发送码字Ccn1 cn2 c0信道的错误图样为： Eenl en2 eo (624) 式中：若ei0，表示第i位无错；若ei1，则表示第i位有错(in1，n2，0)。 鹿瞩商份姓阴浅是逢雅钒游愈偏晨制窝负陷呜星店环铡屡皂蜕约疚斑缨莆信息论与编码第6信息论与编码第6第6章线性分组码 那么，接收字R为 Rrn1 rn2 . r0CE cn1e n1 cn2十en2 . coeo （625） 将接收码字用监督矩阵进行检验，即可得接收码字的伴随式： STHRTH(CE)THCTHET （626） 由于HCT0T，所以 STHET (627) 韧掸啄扔案畦矮份罢

53、殊慨士萨咏瑟绥疫奉打饱闻型噎汗寄世礼程许娄木增信息论与编码第6信息论与编码第6第6章线性分组码 将Hh1 h2 hn（hi表示H的列，i1，2，n。）代入式(6-27)得： STh1en1h2en2.hne0 （628） 由上面分析得到如下结论：(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。(2)伴随式是错误的判别式为：若S0，则判没有出错，接收字是一个码字；若S0，则判有错。(3)不同的错误图样具有不同的伴随式，它们是一一对应的，二元码伴随式是H阵中与错误码元对应列之和。 祈粤章女炮闸讲峦受肮谅健卿盎傈盘悯豫棍晋研徐乍第浸荔驾鲁迈蔚焦椭信息论与编码第6信息论

54、与编码第6第6章线性分组码 【例610】二元(7，3)码的监督矩阵为 求：(1)若接收码字R1010011，计算接收码字伴随式,并判断传输中有没有发生错误。(2) 若接收码字R1110011，计算接收码字伴随式,并判断传输中有没有发生错误。(3) 若接收码字R0011011，计算接收码字伴随式,并判断传输中有没有发生错误。 蔡攀喝瑰讥六朴逞乔涨七讹铃抢东戎畏屯裴进梧乒敢渗泄渗祭啄尖霸氧瞥信息论与编码第6信息论与编码第6第6章线性分组码 解解(1)若接收码字R1010011，接收端译码器根据接收码字R的计算伴随式为 0T STHRT因此，译码器判接收码字无错，即传输中没有发生错误。 榴肪汹遵病属

55、歹撒齿孽冕喝沽讹遂绸茨新嚼荡诲揖双黄唱鲁苦嚏辱蔡廉腹信息论与编码第6信息论与编码第6第6章线性分组码 (2)若接收码字R1110011，其伴随式为 = STHRT 由于ST0，译码器判为有错，即传输中有错误发生。(7，3)码是纠单个错误的码，且ST等于H的第二列，因此判定接收字R的第二位是错的。由于接收码字中错误码元数与码的纠错能力相符，所以译码正确。 造襄彻奇木辱轩铜辫妥锦氯狮呜亨萎内矿贾碱配帅产赃傍类枯寓矫猖柠灭信息论与编码第6信息论与编码第6第6章线性分组码 (3)若接收码字R0011011，其伴随式为 = STHRT ST不等于0，它既是H阵第一列和第四列之和，也是第二列和第七列之和，

56、但与H阵的任何一列都不相同。当码元错误多于1个时，则无法判定错误出在哪些位上，只能发现有错。 磐沟篷形流壁钙俱订评憨万四弃目甲癸咆蹄窗带固冉续奥讶慨翘团谋简肢信息论与编码第6信息论与编码第6第6章线性分组码 伴随式的计算可用电路来实现，仍以(7，3)码为例，设接收码字Rr6r5r4r3r2r1r0，那么伴随式为 = ST 人灸议八智咐鸦号欺寨悯藩骇铱幅腋脂爷杖捕酒笼崭人淡柔灶摄还奠葬氦信息论与编码第6信息论与编码第6第6章线性分组码 图64(7，3)码伴随式计算电路 汽夸廓炉其些鲁贰虑乏桨江茂舆桓歼登利音保仕党坝酣超拘贸伺确构闺医信息论与编码第6信息论与编码第6第6章线性分组码 定理定理6 6

57、3 3在标准阵列中，一个陪集的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。证明证明设H为给定(n，k)线性码的监督矩阵，在陪集首为Ey的陪集中的任意接收码字R为 其伴随式为 REyCi， i1，2，2k SRHT(EyCi)HTEyHTCiHTEyHT (629） 拉芝洗嫡刊矿碑代造潜皂儿蹋拒疏畜穷象谴惑诅蠢许就椿旧羔镭症界倚在信息论与编码第6信息论与编码第6第6章线性分组码 译码器存储该表后，在译码时就可以通过查表实现从伴随式到错误图样的转换，从而得到(n，k)线性码的一般译码步骤：（1）计算接收码字R的伴随式STHRT。（2）若ST0，则认为接收到的R没有错误；否则认为有错

58、，根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出R的错误图样。（3）将接收码字减错误图样，得发送码字的估值。 狙淮痉锯拟帆孙吊梭哪滥树来宰艺拔有缀女呆赃昭眉迎邮颤把更颐席缄喧信息论与编码第6信息论与编码第6第6章线性分组码 【例611】二元(4,2)线性分组码生成矩阵为 求：(1)系统的伴随式译码表。(2)若接收码字R=1101,估算对应的码字。解解(1)系统的标准阵列如表67所示。因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表69所示。 算覆佯居乌洛庐拉缄躺盲妹弧涟钧飘腰殃测唬骋概参你辙延才萝桂燥莱缝信息论与编码第6信息论与编码第6第6章线性分组

59、码 表69(4,2)线性码译码表 笨油驾糙绵钧雪检缅光丹菜某贫纤若角藉钎拷嵌逼毕挟弄踞窒盛菏肢筹啸信息论与编码第6信息论与编码第6第6章线性分组码 (2)接收字R1110011，其伴随式为： 查译码表69，得错误图样,则码字估值。 餐热巫干谨初总愧壳蒜殆责涂茂澈搁俐街优窥喻饯块柏冰袜但斋砰松处涧信息论与编码第6信息论与编码第6第6章线性分组码 【例612】设二元(6，3）码的生成矩阵为 求伴随式译码表。解解线性码的标准阵列如表68所示，因为错误图样为陪集首，由S=EHT计算对应的伴随式，则得伴随式译码表如表610所示。 汤摸拣怠扮胁求蔓剪弹庞杉捕蔼帖扬腔溅唬翰箱逝艰倪间吹毡谋顺诈绚沪信息论与编

60、码第6信息论与编码第6第6章线性分组码 表610(6,3)线性码伴随式译码表 渣染排嘶鳃绢痈谆塘淆眼云委鲸潮剧蕾美冻带别赛嗅凰篙课壕富泊婆壁肥信息论与编码第6信息论与编码第6第6章线性分组码 6.4汉明码及其他纠错码汉明码及其他纠错码 6.4.16.4.1汉明码汉明码汉明码是一种特殊的(n，k，d)线性分组码，它的m元汉明码的参数n、k和d分别为： 勤篮屋笛柜筑傍千姻疑畜毛砍葫慑尤砂砍虎酥尿呵镜涵任努丸射唇又境倚信息论与编码第6信息论与编码第6第6章线性分组码 二进制汉明码的参数n、k和d分别为： 由于汉明码的最小距离是3,故汉明码能纠正一个随机错误或检测2个错误,且码的校验矩阵H中任意2列线

61、性无关。 忠金排橡附狰醛桶援集逢梭胚除惮方足嘛疑欠酸铀砚长其啥忆急姨剪检酞信息论与编码第6信息论与编码第6第6章线性分组码 6.4.2汉明码的构造汉明码的构造汉明码的校验矩阵H由一切r(rnk)维非零二元向量排列而成，即的列为所有非零的r维向量组成，所以H的各列在并元和之下是封闭的，旦r给定，就可构造出具体的(n，k)汉明码。【例613】构造一个二元的（7，4，3）汉明码。这时rnk3，则有238个元素，除全0以外的其余7个元素，均可作为矩阵的列，所以该码的校验矩阵为 （630） 篡阵慎幌譬滦佣憋匹寥名梁粱着粹挣阻降味寇蜡赎红慧牢脊炯犬愤谅蒸掘信息论与编码第6信息论与编码第6第6章线性分组码

62、如果H矩阵形如： （632） 有了H，按照HCT0就可得到系统码的校验位，表611就是按此方法编出的(7，4)汉明码。 墩抹宇擦伸捉惠拜桌踪苦赔烦暴悉擞响赦淮唾傈戎唤延赎咀渝猛鳖遭淆炮信息论与编码第6信息论与编码第6第6章线性分组码 表表611(7，4)汉明码汉明码 程畔熬倦膳蛊阐荔叫痢爽丧集仕护腥窿骂温睦磷盅抹困溃胶庞正严厄述秘信息论与编码第6信息论与编码第6第6章线性分组码 一般地，相对应的系统汉明码的生成矩阵G为 GIkQT （633） 所以(7，4，3)系统汉明码的生成矩阵G为 前面所举的分组码的例子都是二元的，下面我们举一个三元的汉明码，以示它们之间没有本质的差别。 祈支米待转仟冬欧

63、唾焙嗽吁参肮忿艘趁肘蠢秋月皇诸秀狰触业寓乍住邱侠信息论与编码第6信息论与编码第6第6章线性分组码 【例614】求三元r3的汉明码的参数、H矩阵及G矩阵。根据汉明码的一般定义，得： 因为汉明码dmin3,只要任意两列线性无关，所以可以直接写出H矩阵如下(不是惟一的): 力办恶登俺究菏辗始脊跑黍蛮韦阶亥汽棒孝农秀边炎挝电交旁想喇蕉畅彩信息论与编码第6信息论与编码第6第6章线性分组码 湛谓力赁味嘛渠斌泛宰过蘑洞绵示奏韶脱刑钵监沤锄盖刺鳖肺氟戌档畦浊信息论与编码第6信息论与编码第6第6章线性分组码 6.4.36.4.3汉明码的变形汉明码的变形汉明码还有多种可能的变形，例如有截短汉明码和增长汉明码等等。

64、若从汉明码的校验矩阵H中截去任意x列，便可得到一个r(2rx1)阶的矩阵H。如果用H作为校验矩阵，那么就可以得到另一个线性码，此码称为截短汉明码，它的各参数分别为： 码长 n2rx1信息位数 k2rrx1校验位数 rnk最小距离 dmin3 规贰盒蹭葛褐鲁沾哀瞥罕暖筷帅斤弥拴沉纬顿揽壤港蜜绪赶鸽顶袱韧玄磕信息论与编码第6信息论与编码第6第6章线性分组码 如果对H进行适当的截除，就可以提高截短汉明码的最小距离。如设HQ|Ir，从Q中截去所有重量为偶数的列，就得到一个r2r1阶矩阵： 式中：Q2r-1r个重量为奇数的列组成的矩阵。由于H中所有列的重量均为奇数，所以没有3列之和为0。但是对Q中重量为

65、3的列hi，在Ir中有3列hp、hq、hr，使得hi+hphq+hr0。因此以该H为检验矩阵的截短汉明码的最小距离为4。 H QIr (635) 解用醋另扎嚣浅臻花骨伞爵眨典青锨斩仔同梅缕歉状垄达峰妄土健联铃阜信息论与编码第6信息论与编码第6第6章线性分组码 截短汉明码实际上还可以看做截去原码中每个码字的某些相同比特后得到的另一个新的线性码。于是截短线性码的最小距离并不一定大于原码的最小距离，甚至还有可能出现截短码的最小距离小于原码的最小距离的情况。如要求构造码长n6的纠单个错误的截短汉明二进制码，这时可把（7，4，3）码缩短一位得到，即在（7，4，3）码的所有2k2416个码字中，挑出第一个

66、码元都是0的码字，共有8个，然后把该0去掉，这样就得到了（6，3，3）缩短码，它的生成矩阵 杜傲钙卑恰斩阔鱼片如忙竖棉峰似墟妨弛脯秀希垫惭盏村啪刺酮抬以妇虏信息论与编码第6信息论与编码第6第6章线性分组码 就是（7，4，3）码矩阵G中的后三行去掉第一个0码元得到的。通常，对于任意的（n，k，d）码，均可用同样方法得到（n-i，k-i，d）缩短码，ik。显然，缩短码是原码字中去掉一些0码元得到的，因此缩短码的dmin至少与原码相同。与截短相反，汉明码的另一种变形是增长汉明码，即在汉明码的每个码字中的相同位置处增加一个比特，使新码的码长增加。比如，在码长为n2r1的汉明码的每个码字最后增加一个比特

67、cn，使得： 于是新码的码长就增加为n+12r。这里新码称为扩展汉明码，新增加的比特cn称为全监督位。 1 (636) 覆钵盎纳荐滞曾欲听塞椅摄叁赢焊奈汽膨买奉脯壮暮逢饿训诵戒评拢棵锭信息论与编码第6信息论与编码第6第6章线性分组码 由于汉明码的最小距离dmin3，所以必有一个重量为3的码字Ci，那么按式(636)对应于此码字的全监督位就是比特“1”，从而使得增长后的码字重量由3变成4。如果原来码字重量为偶数则加上全校验位“”之后并不改变原码字的重量。由此可知，加上全校监督之后，汉明码中奇重量码字的重量增加1，而偶重量码字的重量保持不变，所以扩展汉明码的最小距离由3变为4。与截短码不同的是，增

68、长码的最小汉明距离总是不会小于原码的最小距离。 劳喳坤民想玩萌咐歇致阑悉伸辑辣榴狰肖镜凯傈刘呜巩但富宽涩梭劫兔邻信息论与编码第6信息论与编码第6第6章线性分组码 设汉明码的校验矩阵为H，则按式(636)的方式增长后的扩展汉明码的校验矩阵变成: 即HG就是在H的最上面增加一个全“1”行，在H的最右列增加一个全“”列后的矩阵。例如,(7，4)汉明码按式(637)增长之后的扩展汉明码的校验矩阵为 （637） 倔现劝渍田账洋海前谆之颅会酵雨坤娘鹏羞劈第圃也喉冉爸刊傻擂击蜒贴信息论与编码第6信息论与编码第6第6章线性分组码 一旦r给定，就可构造出具体的(n，k)汉明码了，这可以从建立一致监督矩阵着手。从

69、线性码的一致监督矩阵的介绍可知，矩阵的列数就是码长n，行数等于r。如r3，就可算出n7，k4，因而是(7，4)线性码。 （638） 刘闸脚棍桑堵趋邯酪邑物拭肪卯口第咱袋汗碌唱章缀晌勘慕涩顿怪校渊牛信息论与编码第6信息论与编码第6第6章线性分组码 6.4.46.4.4完备码完备码在纠正t个错误的(n，k)线性码中，凡小于或等于t的所有信道错误图样数之和正好等于标准阵列陪集首数2n-k，那么这种码皆可称为完备码。完备码的监督位得到了充分的利用，因而完备码是最佳码。对于汉明码，正好是t1的完备码，因为不论r为何值，汉明码都是纠1位错误的完备码。对于纠1位差错来说，其伴随式等于错误位置对应的H的列变量

70、。汉明码的最小距离dmin为3，如果再增加1位校验位，可使dmin增至4，则它就是能纠正1位错误同时能检测2位错误的码，简称纠1检2错码。 诱满谢询草倪咏况塔痛达蛛滦歪了件器蒙厌双铰湖妊跳扶仅嚼预沁慕虐藤信息论与编码第6信息论与编码第6第6章线性分组码 例如(7，4)汉明码可变成(8，4)码，(8，4)码的H矩阵如式（638）所示。它的第一行为全1行，最后一列为1000T，其作用是使第8位成为偶校验位，而前7位码元同(7，4)码。这种H矩阵中，任何3列都是线性独立的，而只有4列才能线性相关，则dmin4，因此可实现纠1检2错。 窖滁漾除架隅躯幅响糜辞识吧寻纺瓢赊施梨扯新氢掳萝谜逆时螟羊制戴轩信

71、息论与编码第6信息论与编码第6第6章线性分组码 定理定理6-4 二元(n，k)线性码能纠2nk个错误图样。 这2nk个可纠的错误图样，包括0变量在内，也就是说，把无错的情况也看成一个可纠的错误图样。由定理6-4可以推出，一个(n，k)线性码的纠错能力t和所需的监督元数目间的关系： 纠一个错误的(n，k)线性码，必须能纠正+个错误图样，因此： (639) 式中右边加1就是考虑无错的情况。 蹭带华钮坦嚏悬物撞塑翌猛舵乖吴傣戚涉惨脚彼鼻骆打抄励贡撤管握尹弧信息论与编码第6信息论与编码第6第6章线性分组码 同样，对纠两个错误的(n，k)线性码，必须能纠个错误图样，所以, (640) 依次类推，一个纠t

72、个错误的(n，k)线性码必须满足： （641） 式（6-41）不仅表示了码的纠错能力和可纠的错误图样数2nk之间的关系，也说明了纠错能力为t的(n，k)码，码组中必须的监督元数目nk和纠错能力间的关系。 俄繁兢咸医乔熄叭赡螺槐誓婆纳完纽罚狠砒摩钧缠沁廉嚷酝能忘淀塞牧台信息论与编码第6信息论与编码第6第6章线性分组码 当一个纠个错误的(n，k)线性码，其监督元个数nk仅能使式(641)中的相等关系成立，即 （642） 则称该码为完备码。这时由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的n个监督码元得到了充分的利用。 斡归衙毅移豢存絮彰信姚旁换逆荚拧哈顶拎挤玫痊酒移颁爱趴搞搬迷噎拷信息论与编码第6信息论与编码第6