Binary Linear Locally Repairable Codes

DOI10.1109/TIT.2016.2605119MaRDI QIDQ2976506zbMATH OpenOpenAlexFDO

Authors Pengfei Huang, Eitan Yaakobi, Hironori Uchikawa, Paul Siegel

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.06960

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this work, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$, dimension $k$, locality $r$, availability $t$, and field size $q$. Then, we study binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared to other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and $4$-cycle free regular low-density parity-check (LDPC) codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.

Cited in

(19)

• On the locality of quasi-cyclic codes over finite fields
• Application of optimal \(p\)-ary linear codes to alphabet-optimal locally repairable codes
• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Locality of optimal binary codes
• On binary locally repairable codes with distance four
• The minimum locality of linear codes
• Perfect LRCs and k-optimal LRCs
• Optimal binary linear locally repairable codes with disjoint repair groups
• Batch codes from Hamming and Reed-Muller codes
• Codes for Distributed Storage
• Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
• Theory behind quantum error correcting codes: an overview
• On locality of binary distance-optimal codes
• Optimal ternary locally repairable codes
• Easy repair via codes with simplex locality
• A new class of self-orthogonal linear codes and their applications
• The augmented codes of a family of linear codes with locality 2
• A family of self-orthogonal divisible codes with locality 2
• Two families of optimal quantum locally recoverable codes

This page was built for publication: Binary Linear Locally Repairable Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976506)