首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

1

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

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

J LOWE YOV

这是什么意思?

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

I HRVE YPU

I LOVF WOU

张二妮把三条消息连起来看, 她发现,第一个位置字符 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 785

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

张大胖说:“真聪明!”

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

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

张二妮收到的消息:46785

两个数据发生了变化,一个减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位。

关于作者:刘欣,码农翻身公众号作者,畅销书《码农翻身》作者,近 20 年软件行业从业经验,前 IBM 架构师,领导过多个企业应用架构设计和开发工作;洞察技术本质,用故事讲解技术是拿手好戏。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20191018A03VF700?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券