ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2022, Vol. 59 ›› Issue (3): 582-596.doi: 10.7544/issn1000-1239.20210575

Special Issue: 2022存储系统与智能处理专题

Previous Articles     Next Articles

Decoding Method of Reed-Solomon Erasure Codes

Tang Dan1,2, Cai Hongliang1, Geng Wei1   

  1. 1(School of Software Engineering, Chengdu University of Information Technology, Chengdu 610225);2(The Software Engineering Technology Research Support Center of Informatization Application of Sichuan, Chengdu 610225)
  • Online:2022-03-07
  • Supported by: 
    This work was supported by the Sichuan Provincial Key Research and Development Program (2020YFG0150).

Abstract: 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.

Key words: RS code, erasure codes, decoding, data reconstruction, recovery cost

CLC Number: