Leafee98's Blog

Reed Solomon

· 341 words · 1 minutes to read

Reed-Solomon 直译大概是“里德-所罗门”,它利用多项式插值拟合的思想,将数据分为 n = t + k 份,那么任意最多 k 份数据丢失,依然能够还原出原始数据。

首先多项式拟合的思想是,对于任意 t 个点,存在唯一的插值 t 项(最高次幂为 t-1)多项式,使得函数图像经过所有这 t 个点。更多特点可以看维基百科

那么我们将数据分为 t 份存储,将存储媒介随意标号,比如 1 号磁盘、2 号磁盘……,将这些标号作为横坐标,每个磁盘中存的数据作为纵坐标,可以得到坐标系中的 t 个点。对这 t 个点进行插值,得到一个唯一的函数图像,然后再取 k 个不同的点,将纵坐标存储为冗余数据。

假设这 n 块磁盘有不多于 k 份丢失,那么可以从剩下的至少 t 份数据插值得到与原来相同的唯一函数,只需要取原磁盘标号处的纵坐标,就可以还原出原磁盘中的 t 份数据。

参考 🔗


Categories