On a Class of Optimal Locally Recoverable Codes with Availability
Authors:
- 25 June 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2021-2026
Abstract
An [n, k, d, r] Locally Recoverable Code (LRC) is a linear code of dimension k, length n, minimum distance d, and locality r, where the locality is the minimum number of coordinates of a codeword one has to access when recovering a single erasure. In this paper we construct a new family of optimal locally recoverable codes with availability t, i.e. any node has t distinct recovery sets. Our codes, for some sets of parameters, achieve the generalized Singleton bound for Locally Recoverable Codes, i.e. $d \leq n - k - \left\lceil {\frac{k}{r}} \right\rceil + 2$, while still allowing availability of nodes. From an information theoretical perspective, this is possible because the inequalities for the distance that take into account availability simply return the Singleton bound in certain regimes of parameters n, k, r, d, t, even with t ≥ 2. This allows the existence of codes with availability t ≥ 2 that still match the Singleton bound for LRCs mentioned earlier. Our construction relies on a new combinatorial structure, arising from the theory of finite fields, that allows to produce orthogonal partitions by leveraging the arithmetic of polynomial rings.
Keywords
This publication has 25 references indexed in Scilit:
- New Constructions of Optimal Locally Recoverable Codes via Good PolynomialsIEEE Transactions on Information Theory, 2017
- On the Combinatorics of Locally Repairable Codes via Matroid TheoryIEEE Transactions on Information Theory, 2016
- Optimal Locally Repairable Codes and Connections to Matroid TheoryIEEE Transactions on Information Theory, 2016
- Locally recoverable codes on algebraic curves2015
- A Family of Optimal Locally Recoverable CodesIEEE Transactions on Information Theory, 2014
- Locally Repairable CodesIEEE Transactions on Information Theory, 2014
- Optimal Locally Repairable Linear CodesIEEE Journal on Selected Areas in Communications, 2014
- Optimal locally repairable codes via rank-metric codes2013
- Optimal linear codes with a local-error-correction property2012
- Hints for computer system design1983