容错传输

假设我们需要传输 $k$ 个数，但是传输过程可能发生错误，我们就会通过这 $k$ 个数计算出 $n$ 个 $n\geq k$ 个数字进行容错传输。由于信息量变大了，容错率也就变高了。

一种典型的容错传输算法叫做 “里德·所罗门” 算法，该算法通过传输 $n$ 个点值来传输一个 $k-1$ 次多项式。

Reed-Solomon algorithm

里德所罗门算法的传输分为两步，第一步是编码，第二步是解码。即编码算法先将需要传输的 $k-1$ 次多项式的 $n$ 个约定好的位置的点值打包，通过有损信道传输，解码算法接收后，找到对应的 $k-1$ 次多项式或者报告传输失败 (错误太多导致传输失败)。

如何做到呢？

Encoding

整个编码和解码的过程统一在模 $p$ 的剩余系下操作。假设多项式为：

$$
\sum_{i=0}^{k-1}F_ix^i
$$

编码和解码算法首先约定好一个大小为 $n$ 的有序集 ${a_0,a_1,\cdots,a_{n-1}}$，这个集合用于确定多项式的点值。

$$
\forall i\in[0,n),\ b_i=\sum_{j=0}^{k-1}F_jb_i^j
$$

然后，将 ${b_0,b_1,\cdots,b_{n-1}}$ 通过有损信道传输给解码算法。即可。

Decoding (Berlekamp-Welch algorithm)

该算法的精髓在于，创造性地提出了一个 Error-Locate 多项式：

$$
E(x)=\sum_{i=0}^{\deg(E)-1}(x-p_i)=\sum_{i=0}^{\deg(E)-1}e_ix^i
$$

其中 $p_i\in[0,n)$ 为每一个发生错误的位。

该多项式满足：

$$
\forall i\in[0,n),\ b_iE(a_i)=F(a_i)E(a_i)
$$

假设我们知道，共有 $e$ 个位置在传输过程中发生了错误，那么我们就可以规定，$E(x)$ 的次数为 $e$ ，即 $e_e\neq 0$，更进一步，我们可以直接规定 $e_e=1$，因为将 $E$ 进行缩放仍然满足上面的等式。

如果规定了这些，并且我们知道足够多的 $(a_i,b_i)$ ，一个合法的 $E$ 一定可以被唯一确定。另外，上面等式的右边我们也需要确定，即：

$$
b_iE(a_i)=Q(a_i)
$$

我们需要求出 $e_i$ 和 $q_i$。 $E$ 是一个 $e$ 次的多项式， $Q$ 是一个 $e+k-1$ 次的多项式，多项式的每个系数都是一个未知数，因此总共有 $k+2e+1$ 个未知数，我们有 $n+1$ 个方程 (包括 $e_e=1$)。只需要保证 $k+2e+1\leq n+1$ 即可

我们需要求解下面的方程：

$$
\begin{bmatrix}
b_0a_0^0 & b_0a_0^1 & \cdots & b_0a_0^e & -a_0^0 & -a_0^1 & \cdots & -a_0^{e+k-1} \\
b_1a_1^0 & b_1a_1^1 & \cdots & b_1a_1^e & -a_1^0 & -a_1^1 & \cdots & -a_1^{e+k-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
b_{n-1}a_{n-1}^0 & b_{n-1}a_{n-1}^1 & \cdots & b_{n-1}a_{n-1}^e & -a_{n-1}^0 & -a_{n-1}^1 & \cdots & -a_{n-1}^{e+k-1} \\
0 & 0 & \cdots & 1 & 0 & 0 & \cdots & 0
\end{bmatrix}
\cdot
\begin{bmatrix}
E_0 \\
E_1 \\
\vdots \\
E_e \\
Q_0 \\
Q_1 \\
\vdots \\
Q_{e+k-1}
\end{bmatrix}=
\begin{bmatrix}
0 \\
0 \\
\vdots \\
0 \\
1
\end{bmatrix}
$$

使用高斯消元即可。

求解出得到的就是多项式 $E$ 和 $Q$ 。 $\frac{Q}{E}$ 即为 $F$。如果 $Q$ 不能被 $E$ 整除，则算法发现了过多的不可修正错误。

一些细节

• 如果想要解出上面的方程，就必须保证 $k+2e+1\leq n+1$，即 $e\leq \frac{n-k}{2}$。
• 在真实传输过程中，我们并不知道 $e$ , 因此需要尝试每一个可能的 $e$ ，看能否求解。

代码

请见 https://github.com/totorato/Reed-Solomon