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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

58 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number7452376
Pages (from-to)3053-3069
Journal / PublicationIEEE Transactions on Information Theory
Volume62
Issue number6
Online published13 Apr 2016
Publication statusPublished - Jun 2016
Externally publishedYes

Abstract

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.

Research Area(s)

  • Binary parity-check code, distributed storage systems, low complexity, Regenerating codes

Citation Format(s)

BASIC Codes : Low-Complexity Regenerating Codes for Distributed Storage Systems. / Hou, Hanxu; Shum, Kenneth W.; Chen, Minghua et al.

In: IEEE Transactions on Information Theory, Vol. 62, No. 6, 7452376, 06.2016, p. 3053-3069.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review