# 距离放大： Reed-Solomon编码的本质

在[如何判断两个大文件内容是否相等](https://hackmd.io/@Kurt-Pan/SJ6Y0DZLq)，[如何快速验证矩阵乘法的正确性](https://hackmd.io/@Kurt-Pan/HJ-RKq78c)两篇文章中我们都使用了Reed-Solomon编码作为关键性的构造方法，且在可靠性证明时使用了一个多项式的关键引理，[Schwartz-Zippel 引理](https://hackmd.io/@Kurt-Pan/Bkq-tZGL5)。

那么为什么对于一个长向量Reed-Solomon编码之后对多项式在随机点处的求值就可以作为原始向量的哈希指纹了呢，是什么原因使得这个特殊的$\mathbb{F}_p$元素就可以完全作为整个$\mathbb{F}_p^n$长度向量的代表了呢？

对于$n$维向量$a, b \in \mathbb{F}_{p}^{n}$，其Reed-Solomon编码是以向量各项作为多项式系数的多项式 $p_{a}$ 和 $p_{b}$ 。注意编码后的多项式成为了分布在整个有限域$\mathbb{F}_{p}$上的长度为$p$的向量。因为$p \gg n$，即编码后向量的长度要远远大于编码前向量的长度。编码过程本身是一个**距离放大**的过程，如果原始向量$a, b$哪怕在一个项上有所不同，那么编码后的两个向量在至少$1-n / p$ 个坐标上都会不同，即几乎每一项都会不同。这种雪崩现象也是可以将Reed-Solomon编码作为哈希函数的原因。

因为有一点不同的两个向量编码后的向量几乎每一项都不同，故可以随机选择$r \in \mathbb{F}_{p}$，使用$p_{a}(r)$ and $p_{b}(r)$这两个$\mathbb{F}_{p}$元素（即编码后向量中的其中随机一项）来代表整个原始向量，并和相对应项来进行比较。故检查两个向量$a$ 和 $b$ 是否相等的问题就可以归约到检查相对应的编码后的两个随机项是否相等的问题了。

### 例子

左边是对长度为3的向量$a=(2,1,1)$的Reed-Solomon编码，所选用的有限域为$\mathbb{F}_{11}$，编码后的结果为$p_a(x)=2+x+x^2$，上图列出了在整个有限域上的求职。右边对$b=(2,1,0)$的编码类似。可以看到虽然$a,b$只有一个项不同，但是编码后几乎所有项都已经不同了。

总结一下，通过Reed-Solomon编码，可以将检验两个大对象是否相等的问题，归约为检查对该对象距离放大编码后的两个随机项是否相等的问题。后者可以在线性时间内完成，大大减少了通信量或计算时间。

同样运用距离放大的思想，自然地引出下一篇的主题，**低阶扩展（LDE）** 和**多线性扩展（MLE）**。