​纠删码理论基础

纠删码数据容错原理

• 纠删码是一种前向纠删码。过程分为编码和解码。编码过程是将文件分割为固定大小的文件块，针对这些被分割的文件块编码为k个块(k个块中包括了k1个数据块和k2个校验块)。解码过程是将编码后的多个子块作为输入，经过解码可以恢复任何一个块的数据(不管是数据块还是校验块)。

• 采用纠删码技术来做数据容错，当磁盘出现故障，失效数据可以通过纠删码的校验链的构建机制来恢复数据，而不是纠正数据自身的错误,一般(k+r,k)纠删码存储开校门为r/k,相对副本纠删码具有低存储开销，但是纠删码涉及到的编解码，计算开销相对较大。
• (k+r,r)纠删码中，其中k份原始数据分块通过一定编码规则计算得到k+r个编码块，其中任意的r份数据块出错时候，均可以通过相应的重构善法来恢复原始k份数据块，纠错能力的上限r<=d-1(d是纠删码的最小列距)。

• 常用的编码编码有RS编码(里得所罗门编码)和LDPC编码(低密度奇偶校验编码)、RAID编码(阵列编码)这三种。

常用纠删码编码方式

• 范德蒙德RS编码：犯德蒙德RS编码中，范德蒙德生成矩阵和数据列向量在Galois域GW中执行乘法运算得到校验数据。如果数据分块d1发生失效，解码过程为利用存活数据所对应的剩余生成矩阵的逆矩阵与存活数据对应的列向量在Galois域GW中进行乘法uyunsuan得出失效数据。数据编码算法成立的必要条件是生成矩阵任意k个行向量在域GW上是线性无关。Galois域的加法等同于异或运算，而对于乘法和除法，则通过查询域GW上对数表和反对数表来实现。范德蒙德RS编码时间复杂度为O(kr),解码时间复杂度(O r的三次方)
• 柯西RS编码：柯西矩阵的RS编码在范德蒙德RS编码基础上做了优化。改进1，冗余矩阵采用柯西矩阵，解码过程中的求逆矩阵的计算复杂度有O(r三次方)降低到O(r的二次方);改进2,将有限域中的每个数表示成一个二维矩阵，使得有限域上的乘法运算转换为异或运算，提高运算效率的同事减低复杂度。
• LDPC编码：LDPC编码是对于一组给定的数据信息，通过在其末尾添加校验信息进行数据检错。若采用奇校验，则添加校验信息的原则是保证原始数据信息和校验信息的数量为奇数;若采用偶校验，保证原始数据信息和校验信息的数量为偶数。