algorithm_组合数学（41）
海明校验码具有检测错误的能力，同时还具有找出错误所在位置的能力。海明码的编码原理：给出信息，组成信息位：，其余位置填充位置码，海明码由此组成。
给定信息. 构建海明码：
其中，pi的值由和bi的位置关系决定。
我们称pi是校验位，bi是信息位。
3=1+2 ——&b1
5=1+4 ——&b2
6=2+4 ——&b3
7=1+2+4 ——&b4
hunnu OJ 10627 海明编码
给出信息码，求出每一组的测试海明码
#include &stdio.h&
#include &string.h&
const int N=205;
char str[N];
int bit[N];
bool vis[N];
int main()
for(int i=0;i&8;i++){
vis[1&&i]=1;
int n,cas=1;
scanf(&%d&,&n);
while(n--){
scanf(&%s&,str);
memset(bit,0,sizeof(bit));
int len=strlen(str);
for(int i=0,dex=3;i&i++){
int pot=0;
while(dex&=(1&&pot)){
if(dex&(1&&pot)) {
bit[1&&pot]^=(str[i]-'0');
if(vis[dex]) dex++;
printf(&CASE:%d\n&,cas++);
for(int i=1;i&N;i++){
if(vis[i]) printf(&%d&,bit[i]);
else printf(&%c&,str[d++]);
if(d==len)
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：187285次
积分：7171
积分：7171
排名：第2889名
原创：549篇
转载：12篇
评论：24条
my friends:
(2)(6)(2)(4)(4)(7)(11)(6)(7)(9)(1)(7)(11)(8)(19)(18)(43)(54)(41)(30)(16)(57)(99)(58)(35)(11)用户名：茶乡浪子
文章数：465
评论数：3349
访问量：2027529
注册日期：
阅读量：1297
阅读量：3317
阅读量：428700
阅读量：1116648
51CTO推荐博文
& & 接上篇：http://winda./0&
& & 以下内容摘自笔者即将出版的最新著作《深入理解计算机网络》一书。本书将于12月底出版上市，敬请留意！！
& &&&本书原始目录：http://winda./8
4.实现校验和纠错
1）海明码的差错检测
表5-2& 各校验码校验的码位对照表
& & 从表中可以得出以下两个规律：
l1p12p24p38p416p5
G1=p1&b1&b2&b4&b5&&&
G2=p2&b1&b3&b4&b6&b7&b10&b11&&&
G3= p3&b2&b3&b4&b8&b9&b10&b11&&&
G4= p4&b5&b6&b7&b8&b9&b10&b11&&&
G5= p5&b12&b13&b14&b15&b16&b17&b18&b19&b20&b21&b11&b23&b24&b25&b26&&&
0G1G2G3G40101
111000111101（一共12位，带阴影的4位就是校验码），从中可以知道它有四个校验组：G1、G2、G3、G4，然而到达接收端经过校验后发现只有G4=1（也就是只有这组校验结果不等于0），通过前面介绍的校验规律可以很快地发现是G4校验组中的p4校位码（也就是整个码字中的第8位）错了（因为只有一组校验结果出现差错时，则肯定只是对应的校验位出了差错），也就是最终的码字变成了：111000001101。
& & 再假设G3、G4两个校验值都不为0，也就是都等于1。通过表5-2中比较G3、G4两个校验组（注意本示例中码字长度一共才12位，只需要比较前12位）中共同校验的码位可是以很快发现是b8，也就是第12位出现了差错，也就是最终的码字变成了：0。
& & 【经验之谈】在这里一定要注意，最终有多少个校验组出现差错也不是随意的，一定要结合实际传输的码字长度来考虑。如上例是一共12位，如果换成了是16位的码字，且当b9位出现差错时，则G1、G3、G4一定会同时出现错误，因为b9这个位是三个校验组同时校验的，只要它一出错，肯定会同时影响这三个校验组的值。同理，如果是b11位出现了差错，因为它同时受G1、G2、G3、G4四个校验组校验，所以这四个校验组结果都将出现错误。
& & 以上就是海明码的整差错检测和差错纠正原理了，确实比单纯的奇偶校验码复杂些，但只要理清了思路，也还是比较简单的。本文出自 “” 博客，谢绝转载！
了这篇文章
类别：┆阅读(0)┆评论(0)
15:38:31 16:59:02 14:14:35 17:25:32 16:47:26 19:50:53 10:03:46 11:10:08温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
把自信和笑容放在脸上,把苦难与伤痛藏在心中。人生注定是一条开始而未结束的路,在觉悟与探索中我们不断进步,在执着与反思后我们不停前行。
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(2741)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_082064',
blogTitle:'海明码原理',
blogAbstract:'　  海明码是奇偶校验的一种扩充。它采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正错误的目的。　　假设数据位有m位，如何设定校验位k的长度才能满足纠正一位错误的要求呢?我们这里做一个简单的推导。k位的校验码可以有2的k次方个值。显然，其中一个值表示数据是正确的，而剩下的2的k次方–1个值意味着数据中存在错误，如果能够满足：2的k次方–1\>m + k (m + k为编码后的总长度)，在理论上k个校验码就可以判断是哪一位出现问题。　　1.编码步骤',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:0,
publishTime:7,
permalink:'blog/static/',
commentCount:1,
mainCommentCount:1,
recommendCount:1,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'把自信和笑容放在脸上,把苦难与伤痛藏在心中。人生注定是一条开始而未结束的路,在觉悟与探索中我们不断进步,在执着与反思后我们不停前行。',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}查看: 6859|回复: 1
主题帖子积分
总督军务威武大将军&镇国公
王道论坛中级道友, 积分 446, 距离下一级还需 554 积分
王道论坛中级道友, 积分 446, 距离下一级还需 554 积分
考研年份2013
报考学校哈尔滨工业大学
本科学校云南民大
& && &1奇偶校验
引出码距& && &2分组奇偶校验（为了引出码距，举的一个不算好的例子）& && &3海明码（同时给出一种那个确定校验位位数的公式的记忆）
所谓的偶校验，就是，在一组数中加上一位（0或1），使加上后的这组数中1的个数为偶数个。
就是给你一串二进制数，你数下1有几个，有奇数个，你就在后面（别的地方当然也可以，随你）加上一个1，这样就有偶数个1了。
这个时候有个人发给你了一组数，你拿过来这个数，一查，这怎么有奇数个1啊，你知道，这孙子肯定给你的是错误的编码！
但如果，他把两位的数值掉换了（把两位的，0变成1，1变成0），这样还是有偶数个1，于是虽然是错误的，但你却校验不出来了的。这就是说，我改变两位，又得到了个“正确”的数。
改变几位，能得到“正确（无法检验出是错误的）”的数，这个几位就被叫做码距。就是你改变几位后能到到一个“正确的数“，就是几位的码距（当然肯定是要位数最小的了……）。这就是为什么奇偶校验的码距为2。当码距大于等于2的时候才有检错能力。 & && &2分组检验（下面这段就是想说明，一个数可以将其分成组，然后分别进行偶校验，别看细节，你明白我说这句话的意思，下面这段就没必要看了。）
我现在想校验2位，比如01，我分别给用2位校验这两个数，比如01ab，使第一位0和校验位a的1的个数为偶数个，使，1和b中1的个数也为偶数个。这样一个数发过来，我只要检验第一为+a的1的个数，就能知道这两位中是否有错误了。& && &2.3海明码
坑爹的来了！
假设有一个数（有效信息+校验位，假定为3位），我把他分成不同的组，然后，对每一组进行偶校验。
（强调下，海明码只检验1位错误，，即如果发生错误，我们假设只有一位发生错误。）
我们现在这样分组，把第一位放在第一组。这是如果第一位错了，那么第一组中1的个数肯定不是偶数个。这样，当我们检验数时，如果（仅）第一组错了，意味这，第一位是错的。
第二位放在第二组，这样如果（仅）第二组出现错误了，就说明第二位出现错误。
那么第三位出现错误了怎么办？我让我们使第一组出现错误，第二组也出现错误，那么1+2刚好=3，这样就表示第三组出现错误。
具体怎么做的呢？我们把1位和3位分成一组，2位和3位分成一组。使第一组有偶数个1，第二组也有偶数个1，这样，这样就达到了我们上面的目的（自己试试看吧！）。
我们现在考虑这三位中哪一位是信息位的问题。
首先共有两组，要使，组1和组2，每一组都有偶数个1，我们知道校验位，是为了是一组中的1的个数为偶数个。如果有1位校验位，无论是这三个的哪个你都没办法达到目的，所以必然有2位校验位，3两个都有，所以选1，2作为校验位。
我们现在假设信息为+校验位有4位，1+2没办法加出4，我们就再分出一组，当这组出现错误的时候，我们就认为4出现了错误。
我们再加一位信息位—第5位，同上，把他放在第一组和第四组，通过校验位（第一位和第四位）使这两组的1的个数达到偶数个，这样当5出现错误的时候，我们的第一组和第四组同时出现错误（奇数个1）。同理，即当我们看到1组和4组出现错误的时候（海明码始终考虑的是一位出现错误，切记！），就表明我们的5位出现了错误。
总结下，你给我一组数，我把他加上适当的校验位，然后分成几组，并把分成的第一组叫做1，第二组叫组2，第三组叫做4，第四组叫做8……每组分一个校验位。然后再把信息位分到相应的组（第7位，就放在124组，第9位我就放在18组）。这样当收到一段信息，我们只要检验哪几组的1不是偶数个，把个组的权（1248……）加起来，就得到了哪一位是错的了！
最后你通过地推公式，就能得到一个关于信息位和校验位的关系，就是，信息位+校验位《=2的校验位次方&&-1。坦白的讲，我没推过这个公式，我也不太清楚为什么……我是这样记的。首先你那k位的验证位，一定要能表示给数的所有位数（n+k位），那么k位就有2的k次方种表示，k位自己的一种不算数，减掉，就有了那个公式（这个说法其实是错误的，但就是方便记忆，考试不会考这个公式怎么来的。）。
剩下的就是看书了。书上说的公式效果跟我说的应该是一样的！& && &
莱布尼茨认识伏羲吗？
主题帖子积分
王道论坛初级道友, 积分 34, 距离下一级还需 166 积分
王道论坛初级道友, 积分 34, 距离下一级还需 166 积分
考研年份2015
报考学校武汉大学
本科学校武汉大学
|||王道论坛 上传我的文档
 下载
 收藏
趁阳光正好，趁微风不燥，趁现在的双手还能拥抱彼此，趁我们还能呼吸
 下载此文档
正在努力加载中...
单片机实现海明码纠错原理的研究
下载积分：350
内容提示：单片机实现海明码纠错原理的研究
文档格式：PDF|
浏览次数：1|
上传日期： 10:08:52|
文档星级：
全文阅读已结束，如果下载本文需要使用
 350 积分
下载此文档
该用户还上传了这些文档
单片机实现海明码纠错原理的研究
官方公共微信