神奇的数据恢复算法 _数据恢复算法

文章插图

今天码哥给大家带来一种数据备份与修复的技术——里德所罗门编码。
里德所罗门编码可是应用场景很多，例如我们耳熟能详的RAID（磁盘阵列），又例如在UDP传输中降低丢包导致的数据缺失的情况等等。
什么是里德所罗门编码这里，先要介绍一种纠错方法——极大距离可分法（MDS）。这是一种很常见的纠错方法，它将原始数据分成等长的N份，并根据这N份数据生成M个冗余的校验数据。此时，M+N块数据中任意M块数据损失，也可以通过剩余N块数据经过计算来恢复原始数据。
里德所罗门纠错算法就是经典的MDS算法。
里德所罗门编码的理论基础

范德蒙矩阵

文章插图

有限域算法
- 伽罗华域

这里我们那先不过多解释，大家先对矩阵型形式混个脸熟，至于伽罗华域我们后面会说到。
里德所罗门编码的原理在开始前，我们不得不引入一个数学问题——插值问题。
在一些工程实践中，某些变量间是存在函数关系的，但通常不能用公式表示，只能用实验观测得到y=f(x)，即一系列xi在函数上的值。有些公式非常复杂，计算其完整公式并不划算，因此我们希望用另一个函数p(x)来尝试逼近f(x) 。
此时，假设在二维空间中有n个点，(x1, y1), (x2, y2), …, (xn, yn)，希望得到一个多项式的解：