为了爱情,我发明了一个算法

2019-10-23 13:07发布

1、

张大胖和张二妮异地恋,见一面很不方面,两人只能通过电脑联系,可是由于计算机之间的通信(无线通信,光纤,双绞线等)存在信道干扰, 他们发送的消息经常出问题。 


这一天,张二妮收到了一条张大胖发了的奇怪消息: 


J LOWE YOV   


这是什么意思? 


张大胖看到张二妮迟迟没有回复,又发了两遍,这次张二妮那边收到的消息是: 


I HRVE YPU


张二妮把三条消息连起来看, 她发现,第一个位置字符 I 出现的频率最高,第二个字符L出现的频率高,第三个是O,第四个是V ...... 她终于猜出来了张大胖的心思:I LOVE YOU


2、


两人周末见了面,聊起上次那让人抓狂的消息, 张二妮不满地说:“你发一堆乱七八糟的数据让我猜,想让人家当数学家啊!” 


张大胖不好意地挠挠头:“这网络太差了,几个单词都出错 !不过我也明白了一个道理,通过重复发送能消除不确定性。” 


张二妮说:“这怎么行?!你学计算机的,想个办法啊!” 


张大胖说:“这样吧,我们搞一个错误检测的办法,以后每次我给你发送一个消息的时候,都附加上一个校验和(checksum),比如我想给你发4个数字 4 5 7 9 。”


张二妮马上打断他:“啊?难道你以后只想给我发数字了吗?” 


“不是不是,我就是举个例子而已,其实计算机的所有东西都是二进制数字表示的,这个校验和是这么计算的,我把他们加起来4+5+7+9 = 25,保留个位就是5, 我把它放到消息的最后一并发给你:4 5 7 9 5。”  


张二妮说:“奥,我明白了,我收到消息以后,把前面的几个数也累加起来计算校验和,然后和5比较,如果相等,数据就是对的,如果不相等,就是错的,我就不用去搭理它了,对吧?” 


张大胖发送的消息:4 5 7 9 5


张二妮收到的消息:4 5 7 8 5  


由于数据从9变成了8 ,张二妮再次计算校验和,就是4(只保留个位),和原来的不相等,表示出错。 


张大胖说:“真聪明!” 


可是张二妮眼珠一转,马上问道:“如果发生了这样的情况呢?” 


张大胖发送的消息:4 5 7 9 5


张二妮收到的消息:4 6 7 8 5  


两个数据发生了变化,一个减1, 另外一个加1, 校验和还是5!错误检测不出来了! 


张大胖叹了口气:“唉,看来这个求和算法太简单了,我得找到一个算法,得产生足够的混乱性和随机性才行。”


3、


又是一个周末,两人见了面,互诉相思之苦以后,张大胖说:“我已经找到办法了,用除法。” 


“什么除法?” 


“就是把要发送的消息转换成一个巨大的二进制数,然后用咱们俩协商好的二进制数字去除,并从中得到余数。把这个余数当成校验和,与消息一并发送。你收到以后也用同样的除法除一下,验证校验和就行了。” 


张二妮问道:“我对二进制加法略知一二,这除法怎么弄啊?!” 


张大胖说:“很简单,和10进制除法是一样的,只不过出现借位的时候,借1不当作十,当作2就可以了。” 

这样,checksum就是那个余数 100 ,发出去的消息就是  1001100 100。 


张二妮用同样的除法一计算,核对一下余数是不是相等,就知道数据有没有错误了。 


这时候张大胖突然想到了一个问题,用计算机来实现借位除法可不容易啊,必须得简化,反正就是为了得到一个余数吗,搞那么复杂干嘛,使用异或运算! 


1 xor 0 = 1 


1 xor 1 = 0 


0 xor 1 = 1 


0 xor 0 = 0 


简单来说,就是“同性”相斥(结果为0),“异性”相吸(结果为1) 


把这个异或运算用到除法中来,是这个效果: 

张二妮都看傻眼了,她说:“刚才的除法我就做不了,你现在又弄什么XOR,太复杂了,我可算不出来。”  


张大胖说:“别担心,我写个程序,会自动实现这个算法,到时候你直接用就行了。” 


(码农翻身老刘注:这种办法就是大名鼎鼎的CRC的基本原理了,不过CRC做了额外的操作,对被除数的低位补了若干个0(除数长度-1), 然后再做除法,得到的余数作为checksum发送, 而接收方用同样的除数做除法,如果发现余数为0,则数据正确。感兴趣的同学可以自己手工计算一下。CRC背后数学原理就有待大家去进一步研究了。)


4、


CRC算法运转得还不错,过了两周,张二妮提出了新的问题:“你这个算法只能发现错误,出了错误还得重传,你能不能想个办法,自动地就纠正错误?” 


张大胖:“这个..... 你让我想想吧。”


张大胖怎么才能纠正错误?我们拭目以待。


后记: 

校验和是数据传输中重要的检测错误的手段,是一个非常基础的算法,既有相对简单的累加,如TCP:

也有复杂的CRC,例如以太网的数据帧,校验和有32位。

————————————————

版权声明:本文为CSDN博主「码农翻身」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/coderising/article/details/102634073


赞赏支持

登录 后发表评论
0条评论
还没有人评论过~