4.4 纠一位错的汉明码(1)

1第四章抗干扰二元编码§4.4纠一位错的汉明码(一)§4.4纠一位错的汉明码(一)一、基本原理二、译码纠错三、构造纠错汉明码的设计要求四、纠一位错的汉明码举例五、错误接收的概率六、生成矩阵七、增余汉明码2第四章抗干扰二元编码§4.4纠一位错的汉明码(一)§4.4纠一位错的汉明码(一)前面介绍的一致监督检错码、简单重复纠错码以及正反码都属于线性分组码。信息元的线性组合生成监督元，从而构成相应的码字。汉明码则是从更一般的角度来研究线性分组码，它给出了线性分组码的一整套统一的编码原理与纠错方法。汉明码的主要工作是由RichardW.Hamming在1950年完成的。最广泛的一类纠错码。(汉明简介)它们有一个共同的特点，即通过若干由于其编码和译码容易实现，因此至今仍是应用3第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理kxxx21k位信息元以()系统码为例：n,kkxxx21rkkkxxx21长度为的码字rkn通常将信息位记为,21kxxxM监督位记为,21rkkkxxxR相应地，系统码则记为.21nxxxRMX4第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理1.生成监督元kxxx21kxxx21rkkkxxx21k位信息元长度为的码字以()系统码为例：n,krkn,12121111kkkxaxaxax,22221212kkkxaxaxax,2211kkrrrrkxaxaxax即.,,2,1riikx1jk,jjixa方法.}1,0{jia其中：,)2(mod.,,2,1riP1555第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理1.生成监督元,12121111kkkxaxaxax,22221212kkkxaxaxax,2211kkrrrrkxaxaxax.}1,0{jia其中：方法,212222111211krrrkkaaaaaaaaaP令krkkkxxxPxxx2121则.)2(mod6第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理注(1)为了表述简洁，下面提到的“加”通常都指“模2加”；1.生成监督元方法kkrrrkkrkkkxxxaaaaaaaaaxxx2121222211121121.)2(modkxxxP21问题(1)对矩阵P有何要求?(2)对k和r有何要求?(2)在此意义下，一般不需要使用“减法”。7第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理2.监督矩阵分析收到一个码字后，为了检测该码字是否有错，需要直接对码字给出一个判别准则。,,,2,1riikx1jk,jjixa由,,,2,1ri,0ikx1jkjjixa有krrrkkaaaaaaaaa212222111211100010001.0rkkkxxxx11P1568第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理2.监督矩阵分析krrrkkaaaaaaaaa212222111211100010001.0rkkkxxxx11rIP.0RM令,rIP][H则有.0][XH(判别准则)注意到矩阵的大小为。][Hnr9第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理2.监督矩阵定义对于某代数分组码集合V，若存在矩阵，满足：][H对所有的允许码字，有VX;0][XH对所有的禁用码字，有VX,0][XH则称矩阵为码字集合V的监督矩阵。][H特别地，如果矩阵的形式为][H,rIP][H则称为标准监督矩阵。][H10第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理2.监督矩阵意义(1)给出了码集合中码字的生成规则。监督矩阵是汉明码中一个重要的概念，其作用为：][H监督矩阵的每一行给出了码字中各个码元之间][H的一个约束关系，从而可以得到一个生成规则。由于监督矩阵一共有r行，因此可以产生r个][H生成规则。对于标准监督矩阵，由这r个生成规则就正好产生系统码的r个监督元。11第四章抗干扰二元编码§4.4纠一位错的汉明码(一)一、基本原理2.监督矩阵意义监督矩阵是汉明码中一个重要的概念，其作用为：(2)用于检错。][H若则码字一定有错；X~,0~][XH若则“认为”码字无错。X~,0~][XH(3)用于纠错*?!记再由s与的关系完成纠错。,~][XHs][H12第四章抗干扰二元编码§4.4纠一位错的汉明码(一)例给出逐位重复的三重码的监督矩阵。,11132xxx其中,12xx,13xx;11P或者,021xx,031xx.0321xxx101011该码为(3,1)码，即每个信息位对应到长度为3的码字：解1x(信息元).321xxx(码字)101011][H.2IP得到监督矩阵为13第四章抗干扰二元编码§4.4纠一位错的汉明码(一)例给出逐位重复的三重码的监督矩阵。解比如信息位1对应的码字为111，若收到的码字为011，若收到的码字为101，若收到的码字为110，101011][H.得到监督矩阵为111][H.00则有011][H.11则有101][H.01则有110][H.10则有(有错)(有错)(有错)(第一位错?)(第二位错?)(第三位错?)14第四章抗干扰二元编码§4.4纠一位错的汉明码(一)例给出正反码的监督矩阵。jx51i5ji,ix.5,4,3,2,1j其中将上式进一步改写为矩阵形式，即得：,05jx1i5ji.5,4,3,2,1jix54321xxxxx54321xxxxx109876xxxxx信息元码字正反码为(10,5)系统码，解即：15第四章抗干扰二元编码§4.4纠一位错的汉明码(一)例给出正反码的监督矩阵。由此即得监督矩阵为：100000111101000101110010011011000101110100001111101051xxx.0.10000011110100010111001001101100010111010000111110][H解16第四章抗干扰二元编码§4.4纠一位错的汉明码(一)例给出正反码的监督矩阵。解由此即得监督矩阵为.10000011110100010111001001101100010111010000111110][H比如对于码字，TX)0001100011(若收到的码字为，TX)0001100011(~0(认为无错)XH][;)00000(T若收到的码字为，TX)0001100011(~1XH~][;)11101(T(有错)XH~][;)00100(T(有错)则有则有有(第二位错?)(第八位错?)17第四章抗干扰二元编码§4.4纠一位错的汉明码(一)二、译码纠错译码纠错的一般准则找码字，使得汉明距离最小，对于收到的码字，从允许码字集合中寻XX~)~,(XXd从而将译为码字。XX~直接使用最小距离准则的缺点计算量较大距离，并进行比较。最小距离准则需要计算收到的码字与所有允许码字的汉明下面将介绍如何利用监督矩阵进行纠错译码。18第四章抗干扰二元编码§4.4纠一位错的汉明码(一)回顾二、译码纠错设收到的码字为,)~~~(~21TnxxxX令，XHs~][X~,0s若则码字一定有错。(1)监督矩阵是一个大小为的矩阵。][HnrnrjihH)(][(按列分块)记为.),,,(21nhhh其中，n为码长，k为信息元的长度。,knr(2)监督矩阵用来对码字进行监督(即检错)。][H若则“认为”码字无错；X~,0s则有下面进一步看看向量与码字中码元出错的关系。XHs~][19第四章抗干扰二元编码§4.4纠一位错的汉明码(一)1.错误图样二、译码纠错定义设发送的码字为记,21nxxx,)(21TnxxxX收到的码字为记,~~~21nxxx,)~~~(~21TnxxxX令,~iiixxe,,,2,1ni称为错误图样。TneeeE)(21错误图样反映了码字中各码元的错误情况：若则码字中第j个码元有错。,1je若则码字中第i个码元无错；,0ieP15820第四章抗干扰二元编码§4.4纠一位错的汉明码(一)推导,~iiiexx由,~iiixxe(1),,,2,1ni.~EXX故XHs~][.)(][EXH.),,,(2121nneeehhh即XHs~][.2211nnhehehe1.错误图样二、译码纠错向量与错误图样的关系XHs~][有由于，0][XH(2)EH][XHs~][因此有21第四章抗干扰二元编码§4.4纠一位错的汉明码(一)2.纠(一位)错二、译码纠错分析根据关系式有XHs~][,2211nnhehehe若码字中无错，.0~][XHs若码字中只有一位错，比如仅第j个码元出错，,0ie;1je.ji(矩阵的第j列)][H.~][jhXHs,0ie.,,2,1ni则则22第四章抗干扰二元编码§4.4纠一位错的汉明码(一)2.纠(一位)错二、译码纠错方法(1)对于收到的码字，计算X~.~][XHs(2)若则“认为”码字无错；,0sX~则“认为”码字的第j个码元有错。X~若即s正好等于矩阵的第j列，,jhs][H问题(1)如何发现甚至纠正更多位数的码元错？(2)对监督矩阵有何要求？23第四章抗干扰二元编码§4.4纠一位错的汉明码(一),3,6rn解由于监督矩阵是一个的大小为的矩阵，63故该汉明码是一个(6,3)码，设其码字为,)(654321TxxxxxxX.3rnk长度为6的码字。.001101100101100111][H例已知某汉明码的监督矩阵为(1)求序列的汉明码；111011(2)若收到的码字为，问该码字是否有错？111000因此有即每3位信息元对应到一个.0][XH则有补24第四章抗干扰二元编码§4.4纠一位错的汉明码(一)解因此，以为信息位，为监督位，321,,xxx654,,xxx即,06321xxxx,0421xxx.0532xxx则可由上述生成关系得到相应的系统码。,214xxx,325xxx.3216xxxx生成关系.001101100101100111][H例已知某汉明码的监督矩阵为(1)求序列的汉明码；111011(2)若收到的码字为，问该码字是否有错？设其码字为则有,)(654321TxxxxxxX.0][XH11100025第四章抗干扰二元编码§4.4纠一位错的汉明码(一)011111,010.100解先将其按每3位分段，再分别