什么是里德-所罗门码？计算机如何恢复丢失的数据
What are Reed-Solomon Codes? How computers recover lost data
Reed-Solomon码
https://youtu.be/1pQJkt7-R4Q?si=WMn1S-zb8ovxXJ0K
数据丢失
想象我们需要通过网络传输4个整数。如果传输过程中可能丢失任意2个数据，如何保证接收方能还原原始信息？
答案是通过冗余编码：发送端将原始4个数据扩展为6个数据（添加2个冗余），即使丢失任意2个数据，接收方仍能通过剩余4个数据还原原始信息。
例如要传输数据[2, 4, 3, 1]，通过数学计算生成冗余数据[0, 2]，构成 [2, 4, 3, 1, 0, 2]。这样即使丢失了任意两个数据，例如2 ? 3 1 ? 2，也能够恢复原始数据。
这种纠删方法在生活中广泛存在：
光盘修复：CD表面划痕导致数据丢失，但仍能正常使用
二维码容错：即使30%面积污损仍可扫描
太空通信：深空探测器与地球的弱信号传输
模运算
在解释这种纠删原理前，需要先补充些数学知识。
模运算（Modular Arithmetic）是一种数学运算，用于计算两个整数相除后的余数。
符号表示：amodn，读作“a 模 n”。
含义：求整数 a 除以正整数 n 后的余数，结果在0到n−1之间。
公式：
a=q⋅n+r(0≤r<n)
其中，q是商，r=amodn 是余数。
例如模5运算中，所有结果都在{0,1,2,3,4}范围内。
运算类型 | 计算示例 |
|---|---|
加法 | 3+4≡2 |
减法 | 2−4≡3 |
乘法 | 3×4≡2 |
除法 | 3÷2≡4 |
解释下其中的减法和除法： |
减法：由于 4−4≡0,4+1≡0，所以 −4≡1；因此，2−4≡2+1≡3
除法：由于2⋅2−1≡1,2⋅3≡1，所以 2−1≡3；因此，3÷2≡3⋅2−1≡3⋅3≡4
将时钟当做模为12的运算，数字在钟面上循环，12点位置对应0值，顺时针为加法，逆时针为减法。
模运算的运算法则与普通运算一致：
加法规则 | 乘法规则 |
|---|---|
(a+b)+c≡a+(b+c)modp | (ab)c≡a(bc)modp |
a+b≡b+amodp | ab≡bamodp |
a(b+c)≡ab+acmodp | (a+b)c≡ac+bcmodp |
a+0≡a≡0+amodp | a⋅1≡a≡1⋅amodp |
a+(−a)≡0≡(−a)+amodp | aa−1≡1≡a−1amodp |
当模数 n 是素数时，模运算的集合 {0,1,2,...,n−1} 不仅是一个环，还能构成一个有限域（Galois域），记作 GF(n)。
域的关键特性是：
每个非零元素都有乘法逆元：即对任意 a=0，存在 b 使得 a⋅b≡1modn。
运算封闭且可逆：加减乘除（除零外）均合法，适合复杂计算。
多项式插值
给定平面上的n个点，存在唯一的一个次数不超过(n-1)的多项式经过所有这些点。
例如，(1,3), (2,1), (3,2) 可以确定唯一一个二次多项式
该唯一性可通过反证法证明：
假设存在两个不同的二次多项式f(x)和g(x)都经过这三个点，则差值多项式h(x)=f(x)−g(x)：
是次数≤2的多项式
在x=1,2,3处都有h(x)=0
但非零二次多项式最多有2个根，矛盾！
由这些点计算多项式的方式如下：
基多项式构造：
对每个点 (xi,yi)，构造基多项式 Li(x)，使其满足：
Li(xi)=1（在当前点取值为1）。
Li(xj)=0（在其他点 xj (j=i) 取值为0）。
具体构造方法：
分子：将 (x−xj) 对所有 j=i 的项连乘，形成 (x−x1)(x−x2)⋯（排除 x−xi）。
分母：将分子中的 x 替换为 xi 后的计算结果，确保标准化（即 Li(xi)=1）。
表达式：Li(x)=∏j=i(xi−xj)∏j=i(x−xj)。
合成多项式：
将每个基多项式 Li(x) 乘以对应的 yi，并将所有结果相加：f(x)=i=1∑nyi⋅Li(x)
由于每个 Li(x) 在 xi 处为1、其他点处为0，合成的 f(x) 必通过所有给定点 (xi,yi)。
最终结果：通过上述步骤构造的 f(x) 是次数不超过 n−1 的唯一多项式，精确穿过所有 n 个数据点。
基多项式构造：
对点(1,3)：L1(x)=(1−2)(1−3)(x−2)(x−3)=2x2−5x+6
对点(2,1)：L2(x)=(2−1)(2−3)(x−1)(x−3)=−1x2−4x+3
对点(3,2)：L3(x)=(3−1)(3−2)(x−1)(x−2)=2x2−3x+2
合成多项式：
纠删过程
运用模运算与拉格朗日插值法，可以解决本文开头提出的数据丢失场景。
设原始数据为[2,4,3,1]，在模5系统中操作：
构造3次多项式满足：
f(0)=2, f(1)=4, f(2)=3, f(3)=1通过插值法解得：
f(x) = 2x³ + 2 mod 5计算冗余数据：
f(4)=0, f(5)=2
假设传输过程中丢失了第1和第6个数据，接收端获得：
[?, 4, 3, 1, 0, ?]通过已知的4个点(1,4), (2,3), (3,1), (4,0)重构唯一的原多项式，再计算：
f(0)=2 → 恢复第一个丢失数据需要用模运算的原因是：
数值可控：所有运算结果在0-4之间
除法可行：素数模保证每个非零元都有逆元
避免溢出：有限域运算适合计算机处理