Design And Implementation Of Fast Algorithms For Reed-Solomon Code

With the rapid increase of global data volume,people have increasingly favored the use of coding technologies in storage systems that have lower storage overhead than backup strategies under the same fault tolerance.Reed Solomon(RS)code,as a classical error-control code,originated from the field of communication coding.In recent years,RS codes are used in a variety of storage systems,such as RAID,Azure,GFS,CEPH,etc.,due to their optimal storage efficiency.Although RS codes are widely used in various applications,they are currently fac-ing new challenges.In digital communication systems,RS codes have the advantage of zero reception overhead compared to some well-known communication codes such as LDPC codes,LT codes,and Raptor codes.However,their code rate is limited by the size of finite field,which makes it unable to be applied to the scene without fixed code rate,such as multicasting.In data storage systems,a large number of erasure codes with localized repairability and low repair bandwidth based on RS codes(such as lo-cally repairable codes,regenerating codes,etc.)have been developed in recent years.But unfortunately,the high coding complexity of RS codes deeply limits their appli-cation prospects in low-latency storage systems.This paper proposes two fast coding algorithms for the shortcomings of RS codes in the above applications.In addition,from the viewpoint of linear transformation,which is the essence of RS code encoding and decoding,this paper proposes a high-performance in-place transform algorithm.The main innovations and contributions of this paper are enumerated as follows:1.Using the tower field over binary extended field,a low-complexity coding algo-rithm of rateless RS code based on FFT is proposed.In order to further optimize the computational efficiency of the algorithm,an output scheduling algorithm of FFT is also given.The rateless RS code can reduce the complexity of encod-ing and decoding to(9(lg k)per information packet when the loss probability of erasure channel is given,where k denotes the number of information packets.2.This paper explores the relationship between the parity-check matrix of RS code(Vandermonde matrix)and Reed-Muller matrix,and then proposes a fast com-putation for RS code syndrome.Based on this fast computation,fast encoding algorithms for RS codes with between 4 and 7 parity symbols are proposed.The-oretical analysis shows that the algorithms only require 3 XORs operations per data bit.3.Since RS codes are constructed on finite fields,the research of algebraic opera-tions on finite fields is of great significance for accelerating the encoding/decod-ing process of RS codes.Based on the method of SSE instruction set in SIMD technology for accelerating the look-up table of field multiplication,this paper presents an optimization method using the AVX instruction set.Furthermore,the execution efficiency of the original method is greatly improved by utilizing the technique of descending field on F216.4.The encoding/decoding process of RS code is essentially a linear transformation.From the perspective of linear transformation,this paper proposes an in-place linear transform algorithm that can be used to save storage space.This algo-rithm is based on the pipeline-friendly Gaussian elimination method,so it has a higher execution efficiency than the existing algorithm(LS algorithm).With the rapid development of big data and increasingly sophisticated mobile devices,the in-place linear transformation algorithm can provide a technical foundation for largescale matrix-vector multiplication to reduce the dependence on large mem-ory data devices.