Description
An LRC whose parameters saturate a generalized Singleton bound.
A \((n,k,r)\) LRC with distance \(d\) is optimal if its parameters \(n\), \(k\), \(d\), and \(q\) are such that the generalized Singleton bound \begin{align} \label{eq:gen-singleton} d\leq n-k-\left \lceil\frac{k}{r}\right \rceil+2 \tag*{(1)}\end{align} becomes an equality. When \(k=r\), the generalized Singleton bound becomes the Singleton bound.
The generalized Singleton bound (1) does not account for \(q\)-ary alphabet size. A more general bound (including the nonlinear case) is given in Ref. [3].
Parent
Children
- Tamo-Barg code
- Maximum distance separable (MDS) code — The generalized Singleton bound becomes the Singleton bound for \(k=r\), so optimal LRCs with that constraint are MDS.
References
- [1]
- P. Gopalan et al., “On the Locality of Codeword Symbols”, (2011) arXiv:1106.3625
- [2]
- D. S. Papailiopoulos and A. G. Dimakis, “Locally Repairable Codes”, (2014) arXiv:1206.3804
- [3]
- V. R. Cadambe and A. Mazumdar, “Bounds on the Size of Locally Recoverable Codes”, IEEE Transactions on Information Theory 61, 5787 (2015) DOI
Page edit log
- Victor V. Albert (2023-12-01) — most recent
Cite as:
“Optimal LRC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/optimal_lrc