简单总结《改变未来的九大算法》(二)——纠错码

作者:杨润炜
日期:2022/1/15 23:38

问题:数据在网络传输可能会出错,如:数值缺失、数据变化(硬件故障、射线等,导致二进制数值变化)、数据被恶意更改等
历史上解决的方法有以下几种:

重复传输,直到认为正确

多次传数据,按数据分组,取频率最高的作为此次传输的数据。
如下图,假设在不稳定的网络环境中传输数据,将“ABC”这个数据重复传了10次,接收端分别收到“ABC”6次,“ABD”1次,“AEC”2次,“BAC”1次,这时接收端会将频率最大的“ABC”作为此次通信的数据。
重复传输直到正确

冗余编码纠错

重复传输比较浪费带宽,特别是在传大文件的时候,而且概率这种事情不是很可靠,万一有问题,还真难复现。为了解决这个问题,引入了冗余编码。
发送前将原数据编码,接收端收到数据后解码,如果解码时发现数据不在编码列表里,就找到其临近的编码结果,这样就修复了传输受损的数据。
下面用现实生活中的文字传阅例子来说明一下。
冗余编码纠错
这个有点类似平时在阅读时,就算遇到错别字也往往能“自动修复”,不会影响信息大意。
实际在计算机中使用的是一种叫汉明码的冗余码,它通过将4bit冗余为7bit的编码方式,能纠错单bit错误,检测双bit错误。(后面找时间扒一下汉明码吧)

数据校验,错了重试

校验和

简单版:将传输的数据累加起来,作为冗余位加入传输的数据中,接收端收到后也用累加的方式校验冗余位,不相等则要求重传。
升级版:因为累加只能识别单bit异常,如果两个bit同时出错,一个减了1,另一个加了1,最后结果还是相等的,所以需要用阶梯校验和。如要传输的数据是“456”,它将被换算为: (4 1) + (5 2) + (6*3) = 32 取最后一位作为冗余位,如果中间传输有两bit出错,则冗余位肯定不一样。

加密哈希函数

MD5、SHA-1都属于这类,它们的校验率更高,更能应对恶意篡改。

这里需要注意,冗余并不能百分百校验出异常的数据,要提高校验率就得提高冗余的位数,这需要权衡数据传输的成本和对速度的影响。

定位错误,精准修复

数据校验只能校验出异常的数据,但要得到正确的数据还是得重传。如果能定位到错误直接修复,就可以节省传输的成本。

二维奇偶校验

通过例子能直观地理解这个方法。
二维奇偶校验码
左边表示数据经过编码后的形式,可以看到每一行的右边、每一行的下边都有个当前累加的数值;
右边第一个表示的是收到数据后,用这个校验和算法计算出每一行、列的累加和,并与数据中的累加数值对比;
右边第二个说明校验的数值对不上,但可以根据行列定位到出错的位置,且能够根据传输过来的累加值反推出原始数据,以此纠正错误。
这种做法有两个问题,一个是需要更多的计算,另一个是出错多的话也没办法修复。

应用场景

在网络协议中,使用的也是校验和,但在校验失败后往往选择让发送端重传,因为数据是拆分小“包”,就算重传也影响比较小。
另一种是下载文件时往往会有checkSum,这种往往是通过加密哈希函数实现的,抗错性更好。

敬请期待下篇 图形识别

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/124.html
邮箱:glowrypauky@gmail.com
QQ: 892413924