代码与代码之外

Code and Beyond

简明前向纠错码(FEC)

前向纠错能力在很多产品 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 深圳

技术很多都是新瓶装旧酒,关键在变通!