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

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 $d\le n-k-\lceil k/r\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.

18 pages

References in corpus (5)

• A family of optimal locally recoverable codes
• Binary Cyclic Codes that are Locally Repairable
• Constructions and Properties of Linear Locally Repairable Codes
• Optimal Locally Repairable Codes via Rank-Metric Codes
• Achieving Arbitrary Locality and Availability in Binary Codes

Cited by in corpus (3)

• Irregular Recovery and Unequal Locality for Locally Recoverable Codes with Availability
• Bounds and Constructions for Linear Locally Repairable Codes over Binary Fields
• New Constructions of Optimal Cyclic (r,δ) Locally Repairable Codes from Their Zeros