A Fast Algorithm of Syndrome Computations for Binary Optimal Locally Repairable Array Codes

Locally repairable array codes (LRACs) constitute an important class of array codes due to their applications in storage systems. In this paper, we first provide an effective generic decoding method for the erased errors. Numerous studies have shown that the syndrome computations account for the main computational overhead of the decoding procedure, especially when the code rate is large. Based on this observation, we present a fast algorithm of syndrome computations for binary optimal LRACs with disjoint local repair groups and certain specific amounts of redundancies, leveraging the vector Reed-Muller (RM)-type transform. In this case, as the code length increases, the number of XORs per data bit required in our algorithm approaches 3, matching that of Reed-Solomon (RS) codes with 4 to 7 redundancies. However, our studied LRACs significantly reduce the number of nodes required for repairing a failed node compared to these RS codes. Moreover, relative to optimal LRACs with 4 redundancies, our algorithm introduces only one additional XOR but tolerates more failures. Furthermore, we generalize our proposed algorithm to support any number of redundancies. We also derive an upper bound on its computational complexity, i.e., the number of XORs per data bit required in the generalized algorithm is at most ⌊log<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i>−1)⌋+1, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> represents the minimum distance of our studied LRACs.