BASIC Codes: Low-Complexity Regenerating Codes for Distributed Storage Systems

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results.National Basic Research Program of China [2012CB315904, 2013CB336700]; Natural Fund of Guangdong Province [S2013020012822]; Shenzhen Basic Research Project [SZJCYJ20150331100723974, SZJCYJ20140417144423192]; University Grants Committee, Hong Kong [AoE/E-02/08, 14209115, CUHK14209515]SCI(E)ARTICLEhouhanxu@163.com; wkshum@inc.cuhk.edu.hk; minghua@ie.cuhk.edu.hk; lih64@pkusz.edu.cn63053-30696