Reed-Solomon纠错码（RS码）（⾥德-所罗门码）
Reed-Solomon纠错码(RS码)
Reed-Solomon利⽤范特蒙矩阵或者柯西矩阵的特性来实现纠错码的功能。 把输⼊数据视为向量D=（D1,D2,…,Dn），编码后数据视为向量（D1,D2,…Dn,C1,C2,…,Cm），RS编码可以看做为如下图的矩阵运算。编码矩阵B必须具有任意⼦矩阵可逆的特性。 Reed-Solomon解码：
RS最多能容忍m个数据块被删除，m包括实际数据和冗余数据。数据恢复的过程如下：
(1)假设D1,D4,C2丢失，从编码矩阵中删掉丢失的数据块/编码块对应的⾏。
根据上图所⽰RS编码运算等式，可以得到如下B’以及等式。
（2）由于B’是可逆的，记B’的逆矩阵为（B’ ^ -1），则B’*(B’^-1）=I单位矩阵。两边左乘B’逆矩阵。
（3）得到如下原始数据D的计算公式
有限域：
假设每⼀个向量元素由8bit组成，那么矩阵相乘后的结果必然要超过8bit的范围，为了解决这个问题，提出有限域的概念。
1.域
⼀组元素的集合，以及在集合上的四则运算，构成⼀个域。其中加法和乘法必须满⾜交换、结合和分配的规律。加法和乘法具有封闭性，即加法和乘法结果仍然是域中的元素。
域中必须有加法单位元和乘法单位元，且每⼀个元素都有对应的加法逆元和乘法逆元。但不要求域中的0有乘法逆元。
2.有限域
有限域⼜称为伽罗华域，其仅含有限多个元素的域。GF（2^ w）表⽰含有2^ w个元素的有限域，那么在计算机中常⽤的有限域是GF(2^8) 3.单位元
Identity Element，也叫⼳元，通常使⽤e来表⽰单位元，单位元和其他元素结合时，并不会改变那些元素。
对于⼆元运算 * ，若a * e=a，e称为右单位元；若e * a=a,e称为左单位元，若a * e=e*a =a，则称e为单位元。
4.逆元
对于⼆元运算 *，若a * b=e，则a称为b的左逆元素，b称为a的右逆元素。若a * b=b * a=e，则称a为b的逆元，b为a的逆元。
5.本原多项式
域中不可约多项式是不能够进⾏因⼦分解的多项式，本原多项式是⼀种特殊的不可约多项式，当⼀个域上的本原多项式确定了，这个域上的运算也就确定了。
**RS-Code是纠删码的⼀种，**Erasure Code(EC)，即纠删码，是⼀种前向错误纠正技术。主要应⽤在⽹络传输中避免包的丢失，存储系统利⽤它来提⾼存储的可靠性。相⽐多副本复制⽽⾔，纠删码能够以更⼩的数据冗余度获得更⾼数据可靠性，但编码⽅式较复杂，需要⼤量计算。纠删码只能容忍数据丢失，⽆法容忍数据篡改。 EC是⼀种编码技术，它可以将n份原始数据，增加m份数据，并能通过n+m份中的任意n份数据，还原为原始数据。即如果有任意⼩于等于m份的数据失效，仍然能通过剩下的数据还原出来。
⽬前，纠删码技术在分布式存储系统中应⽤主要有三类，阵列纠删码（Array Code:RAID5\RAID6）、RS、LDPC（LowDensity Parity Check Code)低密度奇偶校验纠删码。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议