Bounds and Constructions of Locally Repairable Codes: Parity-Check Matrix Approach

DOI10.1109/TIT.2020.3021707zbMATH Open1457.94233arXiv1601.05595OpenAlexW3083398082MaRDI QIDQ5138908FDOQ5138908

Authors: Jie Hao, Kenneth W. Shum, Bin Chen, Fangwei Fu, Shutaong Xia, Yi-Xian Yang 

Publication date: 4 December 2020

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

Abstract: A $q$-ary $(n,k,r)$ locally repairable code (LRC) is an $[n,k,d]$ linear code over $mathbb{F}_q$ such that every code symbol can be recovered by accessing at most $r$ other code symbols. The well-known Singleton-like bound says that $dlen-k-lceilk/rceil+2$ and an LRC is said to be optimal if it attains this bound. In this paper, we study the bounds and constructions of LRCs from the view of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed. Several useful structural properties on $q$-ary optimal LRCs are obtained. We derive an upper bound on the minimum distance of $q$-ary optimal $(n,k,r)$-LRCs in terms of the field size $q$. Then, we focus on constructions of optimal LRCs over binary field. It is proved that there are only 5 classes of possible parameters with which optimal binary $(n,k,r)$-LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these 5 classes of possible optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes.

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

zbMATH Keywords

boundsparity-check matricesconstructionsSingleton-like boundlocally repairable code (LRC)

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65)

Cited In (14)

• Codes for Distributed Storage
• Infinite families of optimal linear codes and their applications to distributed storage systems
• Perfect LRCs and \(k\)-optimal LRCs
• A characterization of optimal locally repairable codes
• Optimal Locally Repairable Codes and Connections to Matroid Theory
• New upper bounds and constructions of multi-erasure locally recoverable codes
• Optimal ternary locally repairable codes
• Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
• A characterization of optimal constacyclic locally repairable codes
• On finding the largest minimum distance of locally recoverable codes: a graph theory approach
• Improved Bounds and Singleton-Optimal Constructions of Locally Repairable Codes With Minimum Distance 5 and 6
• On locality of binary distance-optimal codes
• Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
• Locally Repairable Regenerating Codes: Node Unavailability and the Insufficiency of Stationary Local Repair

This page was built for publication: Bounds and Constructions of Locally Repairable Codes: Parity-Check Matrix Approach

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