Research On Fast Encoding And Decoding Algorithm Of Blaum-Roth Array Code

With the popularization of the Internet and the advent of the big data era,high requirements have been put forward for the storage reliability and availability of massive-scale data.Distributed storage systems have emerged as the times require and add redundancy to the original data to ensure fault tolerance.There are two main redundancy strategies in the industry:replication and erasure correction codes.Due to high storage overhead,the replication strategy is not suitable for large-scale distributed storage systems.Compared with the replication strategy,the erasure correction codes strategy has lower storage overhead under the same fault tolerance capability,Therefore,it is widely adopted by modern distributed storage systems.MDS array codes are special type of erasure correction codes,which have simple encoding and decoding process and achieve the best balance between storage overhead and fault tolerance.The increasing scale of storage systems has led to research on MDS codes that can correct any number of erasures,such as Reed-Solomon codes.Reed-Solomon codes are defined on finite field and require time-consuming multiplication and division over finite field during the encoding and decoding process.Compared to Reed-Solomon codes,Blaum-Roth codes are defined on quotient ring rather than finite field,owing to multiplication operations can be converted into cyclic shift operations,Blaum-Roth codes have more efficient encoding and decoding algorithms.Blaum-Roth codes use Vandermonde matrix as the check matrix and encoding process can be regarded as special case that all check columns fail,So we only need to focus on the research of fast decoding algorithms.Two existing all-erasure decoding algorithms for Blaum-Roth codes are syndrome-based decoding algorithm and interpolation-based decoding algorithm.We optimize these two decoding algorithms and present a decoding algorithm based on LU decomposition of Vandermonde matrix.We have achieved the following results:(1)Firstly,the unnecessary computation in syndrome-based decoding algorithm has been reduced through rigorous proof? secondly,we proposes a merging algorithm to simplify the factorial multiplications with only two non-zero terms that appear in both syndrome-based decoding algorithm and interpolation-based decoding algorithm? thirdly,we use more efficient algorithm to replace polynomial divisions that appear in both syndrome-based decoding algorithm and interpolation-based algorithm? finally,fast decoding algorithm based on LU decomposition of Vandermonde matrix is used to decode Blaum-Roth codes.(2)Drawing on the surrogate model of cloud storage,we build an extended HDFS distributed file storage system platform and evaluate the performance of five algorithms in the system,including syndrome-based decoding algorithm,interpolation-based decoding algorithm,modified syndrome-based decoding algorithm,modified interpolation-based decoding algorithm and decoding algorithm based on LU decomposition of Vandermonde matrix.From the aspects of encoding speed and decoding speed,the performance of the two optimized decoding algorithms is better than the original decoding algorithm,and decoding algorithm based on LU decomposition of Vandermonde matrix has best performance.