海明码例举.ppt

海明码详解;海明码步骤： 一、确定校验码的位数k 二、确定校验码的位置 三、数据的位置 四、求出校验位的值 ;数据的位数m=6，公式来计算满足条件的k的最小值 2的k次方-1=m+k 即：2的k次方-1=6+k 解此不等式得：满足不等式的最小k=4，也就是D=101101这个数字的海明码应该有6+4=10位，其中原数据6位，校验码4位。 ;设这4为校验码分别为P1、P2、P3、P4 数据从左到右为D1、D2、……、D6 编码后的数据共有6+4=10位，设为M1、M2、……M10 校验码Pi（这里i=1,2,3,4）在编码中的位置为2的（i-1）次方，值是这样的1,2,4,8,16……即：P1在M1位置，P2在M2位置，P3在M4位置，P4在M8位置，这里一共有10位,所以排不到M16，见下图中“甲”行红色字体 ;;这个很简单，除了校验码的位置其余的就是数据的位置，填充进去就可以了，见图中“甲”行的蓝色字体，于是可以先把数据信息填进去，见“丙”行，下面就是最关键的部分，求出校验位的值 ;这里会用到一个公式，先回顾一下二进制的表达，对于一个4位二进制数，可以表达16个值，0000B~1111B，“B”代表二进制，“D”代表十进制，假定这4位二进制数，从左到右分别为S4、S3、S2、S1，请向左歪90°看下图：1D=0001B，所以M1在S1那一行，4D=0100B，所以M4在S3那一行，5D=0101B，这就不能用一个格子来表达了，所以需要S3和S1共同表达，即4+1=5，看图中黄色的部分，是不是M5？M后边的数字都可以拆为由2的n次方的数相加来表达，在举一个例子M7：4+2+1=7即：7D=0111B，看图中橙色的部分，都是M7吧! 这个公式在验证纠错的时候还会用得到，只要记住这个公式的推导就可以解决所有问题了。;;接下来就是代入求值的过程了，注意“⊕”这个符号，这是异或符号。按照图1中的指示，把相应的值代入到图2 的公式里，可以得到如下内容 S1=M1⊕M3⊕M5⊕M7⊕M9 =P1⊕D1⊕D2⊕D4⊕D5 S2=M2⊕M3⊕M6⊕M7⊕M10=P2⊕D1⊕D3⊕D4⊕D6 S3=M4⊕M5⊕M6⊕M7 =P3⊕D2⊕D3⊕D4 S4=M8⊕M9⊕M10 =P4⊕D5⊕D6 ;如果海明码没有错误信息，S1、S2、S3、S4都为0，等式右边的值也得为0，由于是异或，所以Pi（i=1,2,3…）的值跟后边的式子必须一样才能使整个式子的值为零，即：Pi=后边的式子的值,即： P1 =D1⊕ D2⊕ D4⊕ D5 P2 =D1⊕ D3⊕ D4⊕ D6 P3 =D2⊕ D3⊕ D4 P4 =D5⊕ D6 ;仔细想一下异或的含义，以S4= P4⊕D5⊕D6为例,S4=0,就是说P4⊕D5⊕D6=0，那么P4和（D5⊕D6）必须一样（即P4= D5⊕D6），那么异或的结果才能为零！（不要以算术加减法来理解，要用逻辑数学的思维！） 那么可以算出Pi的值了吧？ P1 =D1⊕D2⊕D4⊕D5 = 1⊕ 0⊕1⊕0=0 P2 =D1⊕D3⊕D4⊕D6 = 1⊕ 1⊕1⊕1=0 P3 =D2⊕D3⊕D4 = 0⊕1⊕1=0 P4 =D5⊕D6 =0⊕1=1 把Pi的值填写到图1中，看“丙”行，就可以得到haimming（海明）编码！ ;;现在我们得到了D=101101的正确海明码就是 那么出错的时候是怎么验证出来的呢？比如第5位错了，第5位现在的值是0，如果错了，它只能是1，二进制就这两种值即：我们得到了这样的一组编码，现在要找出错误的位置（假定你不知道哪里错） ;;现在又要用到公式了，请看图 ;把图4中的值，带入到图2 的公式里 S1=0⊕1⊕1⊕1⊕0 =1 S2=0⊕1⊕1⊕1⊕1 =0 S3=0⊕1⊕1⊕1 =1 S4=1⊕0⊕1 =0 按照S4S3S2S1排列得到的二进制数为：0101，对应的值十进制为5，找到错误位置！纠错！把1改为0！