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）是一种数学运算，用于计算两个整数相除后的余数。

• 符号表示：，读作“a 模 n”。

• 含义：求整数 除以正整数 后的余数，结果在到之间。

公式：
其中，是商， 是余数。

例如模5运算中，所有结果都在{0,1,2,3,4}范围内。

1. 减法：由于 ，所以 ；因此，

2. 除法：由于，所以 ；因此，

将时钟当做模为12的运算，数字在钟面上循环，12点位置对应0值，顺时针为加法，逆时针为减法。

模运算的运算法则与普通运算一致：

当模数 是素数时，模运算的集合 不仅是一个环，还能构成一个有限域（Galois域），记作 。
域的关键特性是：

• 每个非零元素都有乘法逆元：即对任意 ，存在 使得 。

• 运算封闭且可逆：加减乘除（除零外）均合法，适合复杂计算。

多项式插值

给定平面上的n个点，存在唯一的一个次数不超过(n-1)的多项式经过所有这些点。

例如，(1,3), (2,1), (3,2) 可以确定唯一一个二次多项式

该唯一性可通过反证法证明：

假设存在两个不同的二次多项式和都经过这三个点，则差值多项式：

• 是次数≤2的多项式

• 在x=1,2,3处都有

• 但非零二次多项式最多有2个根，矛盾！

由这些点计算多项式的方式如下：

1. 基多项式构造：

   • 对每个点 ，构造基多项式 ，使其满足：

     • （在当前点取值为1）。

     • （在其他点 取值为0）。

   • 具体构造方法：

     • 分子：将 对所有 的项连乘，形成 （排除 ）。

     • 分母：将分子中的 替换为 后的计算结果，确保标准化（即 ）。

     • 表达式：。

2. 合成多项式：

   • 将每个基多项式 乘以对应的 ，并将所有结果相加：

   • 由于每个 在 处为1、其他点处为0，合成的 必通过所有给定点 。

最终结果：通过上述步骤构造的 是次数不超过 的唯一多项式，精确穿过所有 个数据点。

基多项式构造：

• 对点(1,3)：

• 对点(2,1)：

• 对点(3,2)：

合成多项式：

纠删过程

运用模运算与拉格朗日插值法，可以解决本文开头提出的数据丢失场景。

设原始数据为[2,4,3,1]，在模5系统中操作：

1. 构造3次多项式满足：

   f(0)=2, f(1)=4, f(2)=3, f(3)=1

2. 通过插值法解得：

   f(x) = 2x³ + 2 mod 5

3. 计算冗余数据：

   f(4)=0, f(5)=2

假设传输过程中丢失了第1和第6个数据，接收端获得：

[?, 4, 3, 1, 0, ?]

通过已知的4个点(1,4), (2,3), (3,1), (4,0)重构唯一的原多项式，再计算：

f(0)=2 → 恢复第一个丢失数据

需要用模运算的原因是：

1. 数值可控：所有运算结果在0-4之间

2. 除法可行：素数模保证每个非零元都有逆元

3. 避免溢出：有限域运算适合计算机处理