前向纠错能力在很多产品 PPT 里捧的很高,但其实是一个炒冷饭的技术。类似海明码和硬盘 RAID 阵列都有类似的功能和概念。
最简单的前向纠错实现是 QUIC 用的异或(RAID也是用异或),N 个数据块异或出一个校验块,然后即可以容忍 1/(N+1) 的丢包率。
异或的计算原理在逻辑代数里,虽然非常简单,但那也是大学才学的玩意,本文不详述。
下面我们用中学数学解释一下能容忍任意 M/N 丢包率的算法,大约是初中生基本都能懂的程度。
先假设一对网络通讯的发送方和接收方约定如下二元一次方程组:
x + y = a
x + 2y = b
接收方收到:{a=3,b=4} 这组数据的时候,发送方想让他知道啥呢?
接收方解方程得到结果:{x=2, y=1},这才是发送方的原始数据。
这么折腾一圈似乎没啥意义啊,就浪费了一点 CPU 时间而已……
如果我们继续折腾,扩展一下这个方程组:
x + y = a
x + 2y = b
2x + y = c
接收方收到:{a=4,c=7} 时,它能解出:{x=3,y=1}。
接收方收到:{b=5,c=4} 时,它能解出:{x=1,y=2}。
接收方收到:{a=5,b=8} 时,它能解出:{x=2,y=3}。
我们看到:扩展方程组后,接收方只要收到 2/3 的数据,即能解出所有的原始数据。
调整方程组,就可以设计任意容忍 M/N 丢包率的算法了。
至于如何用代码设计和实现这个算法,因为涉及线性代数,本文不讲。
2019-03-28 深圳
技术很多都是新瓶装旧酒,关键在变通!