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].
Member of code lists
Primary Hierarchy
Parents
Optimal LRC
Children
For \(r \mid k\), Tamo-Barg codes meet the LRC Singleton bound [4; Sec. 15.9.3].
The generalized Singleton bound becomes the Singleton bound for \(k=r\), so optimal LRCs with that constraint are MDS.
References
- [1]
- P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “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
- [4]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) 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