RS类纠删码的译码方法

Decoding Method of Reed-Solomon Erasure Codes

RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR,XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明:在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.

As known,RS(Reed-Solomon)codes can construct any fault-tolerant codewords according to the application environment,which has good flexibility,and the storage system using RS erasure code as the fault-tolerant method can achieve the optimal storage efficiency.However,compared with XOR(exclusive-OR)-based erasure codes,RS erasure codes require too much time to decode,which greatly hinders its use in the distributed storage system.In order to solve this problem,this paper proposes a decoding method for RS erasure codes.This new method completely discards the matrix inversion which is commonly used in all current RS erasure codes decoding methods,and only uses the addition and multiplication with less computational complexity,and the linear combination of the invalid symbols by the valid symbols can obtained by the simple matrix transformation on the constructed decoding transforming matrix,thereby reducing the complexity of decoding calculations.Finally,the correctness of the method is proved theoretically,and for each file of different sizes,three file blocks of different sizes are divided,and the data blocks obtained by the division are tested.The experimental results show that in the case of different file block sizes,the new decoding method has lower decoding time cost than other methods.