A Class of Binary Locally Repairable Codes

作者：Shahabinejad Mostafa^*; Khabbazian Majid; Ardakani Masoud

来源：IEEE Transactions on Communications, 2016, 64(8): 3182-3193.

DOI：10.1109/TCOMM.2016.2581163

• Erasure coding
• distributed storage systems
• coding complexity
• binary locally repairable codes

An (n, k) erasure code that can recover any coded symbol by at most r other coded symbols is called a locally repairable code (LRC) with locality r. LRCs have been recently implemented in distributed storage systems. Coding complexity reduction can be significantly decreased by using binary LRCs (BLRCs) as they eliminate costly multiplication calculation. In this paper, motivated by the recently erasure codes with d = 4 used in practice, we propose BLRCs when (r + 1) vertical bar n and d = 4. We prove that our proposed binary codes are optimal for r is an element of {1, 3}, meaning that neither their locality nor their minimum distance can be improved by non-binary codes. For r >= 4, our proposed binary codes offer near-optimal code rate, with a rate gap of O(log r/n) compared with optimal non-binary codes. While keeping the bulk of code structure binary, we eliminate this rate gap by using fields with sizes as small as r + 2 for only two redundant symbols. These non-binary codes still eliminate the need for costly multiplications in many operations including a single failure repair (a dominant repair scenario). Using the construction of spanning BLRC with d = 4 as a backbone, we also construct LRCs with minimum distance d >= 6. Furthermore, we obtain a closed-form equation for the mean-time to data-loss of arbitrary erasure codes.

• 出版日期2016-8