汉明码校验原理解析-

文章编号:1007-757X(200701-0058-03汉明码校验原理解析甘家宝摘要:汉明码是一个在原有数据插入若干校验码来进行错误检查和纠正的编码技术,在通讯领域内应用广泛。许多有关网络与通信持术的教科书对汉明码的统码原理及其方法都作了介绍,但是几乎所有的解释都或多或少地存在一些令人费解的地方:1对公式2k-1≥m+k(其中m是信息长度,k是插入位数的推导解释得不多;2对检验和纠正错误的原理都未能给出浅显的解释。3本文通过2进制的两个应用实例,循序淅进导出了汉明码检验和纠错的原理,通俗易懂。关键词:二进制;汉明码;偶性测试中图分类号:TN919.3文献标识码:A1前言近年来,随着网络技术的普及应用,越来越多的人开始学习与网络通信技术相关的课程。笔者在教学课程中发现众多的教科书对于应用比较普遍的校验技术—汉明码校验技术的原理解释得不够详尽,致使许多初学者对此感到迷惑。甚至有网友在互联网上发出了“只知道这么做,不知道什么?”的无奈。本文通过“贵夫人住店”和“猜年龄”等二进制应用实例通用俗易懂地给出了汉明码校验原理解释,可以帮助读者更好地理解汉明码的实现方法及其检错、纠错原理,也可以供相关教师在教学时参考。2汉明码校验方法的具体实现利用汉明码对网络传输数据进行校验时,被传送的数据由两部分组成。一部分是原始信息,另一部分是监督位信息。具本实施步骤如下:2.1发送方编码1根据原始信息的码长确定需要多少个监督位由于监督位必须设在第1,2,4,8,16,32,.....这些2的整次幂的位置,所以当原始信息是2~4位时,需要3个监督位:1234567XX*X***其中X为监督位,*为信息位;XX*X***X*******当原始信息是13~26位时,需要5个监督位:232425262728293031.......................................*********.......................................一般地,如果原始信息位长度为m,设监督位长度为K,则应有:2k-1≥m+k2确定监督位的内容根据偶性测试(或奇性测试的原理对监督位填写适当的0或1,确保发送出去信息各位上的“1”的个数为偶数。为了实现这一目的,我们先将待发送的原始信息按照上面的规律填写到*号所在的位置;然后分别按照以下数列组的顺序对各监督对各监督位填写0或1就可以了:1,3,5,7,9,11,13,15,......2,3,6,7,10,11,14,15,......4,5,6,7,12,13,14,15,......8,9,10,11,12,13,14,15...........................作者简介:甘家宝,上海托普信息技术学院软件学院,上海2013002.2接收方解码接收方在收到发送方的一系列“01”串以后,首先对收到的字串进行偶性测试,检验传输过程是否正确,如果正确,则剔除监督位获取正确信息。1偶性测试由于发送时,发送方是在监督位填写了适当的“0”或“1”,确保了各次监督过程的偶性测试都可以得到偶数个1,所以在接收方只需将发送方的步骤再重复一遍即可。如果发现某次未能得到偶数个“1”,说明相应的错误发生了。值得注意的是,由于是采用偶性测试的办法。所以如果同时出现了偶数个错误,那么将不能正确地被检出。但是出现这种情况概率很小。2解码如果通过偶性测试确认收到的数据是正确的,则可以将第1,2,4,8,16,32......等位置上的信息剔除,从而得到原的信息。2.3举例1发送方编码步骤1、确定监督位长度对照公式:2k-1≥m+k原始信息长度为12,监督位长度为3显然太小。设长度为4,则12+4=16,而24-1=15,小于16,也不行。所以监督位长度应该为5,也就是说,完整的传输信息应该是17位。步骤2、占位步骤3、填写监督位内容(1根据第1,3,5,7,9,11,13,15,17号各位置上的“1”的个数应该为偶数的原则,由于第3,7,9,11,13,15,17号为“1”,共7个,为奇数,因此第1号位置应该填写“1”。7+1=8,为偶数。(2根据第2,3,6,7,10,11,14,15号各位置上的“1”,的个数应该为偶数的原则,由于第3,7,11,15号为“1”,共4个,为偶数,因此第2号位置应该填写“0”。4+0=4,为偶数。(3根据第4,5,6,7,12,13,14,15号各位置上的“1”的个数应该为偶数据原则,可以确定出第4号应该为“0”。(4根据第8,9,10,11,12,13,14,15号各位置上的“1”的个数应该为偶数的原则,可以确定出第8号应该为“1”至此,编码完成。2接收方校验、纠错步骤1、按原位置对号入座步骤2、检验第1,3,5,7,9,11,13,15,17号各位置上的“1”的个数是否为偶数。检验结果共8个,为偶数,在5位2进制数的右起第1位记0XXXX0步骤3、检验第2,3,6,7,10,11,14,15号各位置上的“1”的个数是否为偶数。检验结果共4个,为偶数,在5位2进制数的右起第2位记0XXX00步骤4、检验第4,5,6,7,12,13,14,15号各位置上的“1”的个数是否为偶数。检验结果查共3个,为奇数,在5位2进制数的右起第3位记1XX100步骤5、检验第8,9,10,11,12,13,14,15号各位置上的“1”的个数是否为偶数。检验结果共5个,为奇数,在5位2进制数的右起第4位记1X1100步骤6、检验第16、17号各位置上的“1”的个数是否为偶数。检验结果共4个,为偶数,在5位5进制数的右起第5位记001100最后将该二进制换数算成十进制数:(011002=(1210证实第12位确实有误,将0改为1即得正确信息。对于上面的编码和检验的过程,一般初学者都存在这样两个问题:1、为什么监督位必须设在第1,2,4,8,16,32,.....这些2的整数资幂的位置?2、为什么监督位的内容需要根据以下数列组(1对应位置上的内容来确定?不过,再仔细分析下面两则二进制应用实列以后,这两个问题也就迎刃而解了。3两则二进制应用实例实例1贵夫人住店一位贵夫人旅游,来到一家豪华宾馆准备住宿。可以在办完各项入住手续准备掏钱包付款时发现钱包丢了。于是和店主商定:每晚的房价先以金项链的一环抵押,待款到后再如数赎回。老板同意了这一方案。接下来夫人考虑了切割项链环和将来恢复所需要的费用问题:金匠是按照切割和恢复的次数来收费的。如果将项链割成一环一环的,很显然不合算。夫的解决方案是:将项链切割成如下数列{1,2,4,8,16,32,......}(2的子串。第1天给出1环串;第2天取回1环串,给出2环串;第3天给出1环串;第4天取回一环串和2环串,给出4环串;第5天给出1环串;第6天取回1环串,给出2环串;.....如些类推,可以实现每一个不同数字的组合。而且由于数列(2中的第一项比前面各项和小1,也就是说不存在第二种可以实现同样效果的数字组合方式。表4表5表6可见该切割方案确实是最为节省工钱的切割的方案。(下转第64页在最重好的安全性方面。SSLVPN能够提供ERP全程安全保证。首先,SSLVPN可以实现128位数据加密,保证数据在传输过程中不被窃取,确保ERP数据传输的安全性。其次,多种认证和授机方式的使用能够只让“正确”的用户访问ERP系统,从而确保ERP访问的安全性。再次,SSLVPN支持多层安全控制机制,能够保保证ERP后台服务器的安全性。在管理维护和操作性方面,SSLVPN方案可以做到基于应用的精细控制,基于用户和组赋予不同的应用访问权限,并对相关访问打操作进行审计。此外,SSLVPN还提高了ERP平台的灵活性,方便扩展应用和增强性能,尤其是在降低使用成本、最有效地保护用户投资这一敏感话题上,SSLVPN赢得了用户最终的好感。以ArrayNetworks公司的ArraySP系列产品为例,其不仅采用了SSL加速、连接多路复用、和HTTP压缩等减负技术,还使用了Webwall、AAA、Web资源映射、内容过滤和策略实施技术。当今Web成为标准平台已势不可挡,越来越多的企业开始将ERP系统移植到Web上。而SSLVPN通过特殊的加密通讯协议,被认为是实惠远程安全访问Web应用的最佳手段,能够让用户随时随地甚至在移动中连入企业内网,ERP将是基于SSLVPN的远程安全接入的直接爱益者。6结束语随着中国企业对网络信息技术日益重视,将有越来越多的企业会建立自己的企业内网和门户站来规范自身的管理扩展业务。Web技术凭借在应用部署以及维护上的优势,将会在其中占据绝大的份额。SSLVPN必将会在其中扮演极其重要不可或缺的角色。参考文献:[2]小四.了解SSLVPN,认识SSLVPN应用市场[J].IT世(收稿日期:2006-11-1(上接第60页这个实例还不能完全回答上面的二个问题,但是有一些辅助作用,它说明了2的整数次幂的位置的特殊意义。实例2猜年龄首先请观察下面的六张表格。在分析其规律之前,我们先做个小游戏:假设你的年龄是1到63之间的某个数,那么你无需告诉我这个数,只需告诉我这个数在哪几张表中有,哪几张表中没有,我就可以算出你的平龄。举例来说,假设你的年龄为38,那么表1表2表3表4表5表6无有有无无有将“有”用“1”,“无”用“0”替换表1表2表3表4表5表6011001再将这张表第二行中的各数顺序倒置:100110此数换算成十进制,就是38。读者也可以自行再验证几个数。那么该算法的原理何在呢?首先,我们观察一下各表的第一个数字,不难发现它们分别是2的1次方,2次方,......5次方。其次,我们对表1至表6中的数字进行分组:表1中每组1个数,各组间隔为2;表2中每组2个数,各组间隔为4;表3中每组4个数,各组间隔为8;...........................由此我们可以得出结论:表1中各数被2除所得余数化为2进制时,右起第1位总是1;表2中各数被4除所得余数化为2进制时,右起第2位总是1;表3中各数被8除所得余数化为2进制时,右起第3位总是1;.................................有了这个规律,我们就可以推算出准确的数字了。例如某人记下了55这个数字作为年龄,我们通过观察可以发现表1,2,3,5,6有这个数字,而其他表没有,因此该数应该为:(110