Locally recoverable code: Difference between revisions

Revision as of 03:09, 28 November 2024

Revision as of 03:11, 28 November 2024

Line 64:

==Definition==

Let <math>C</math> be a <math>[n, k, d]_{q}</math> [[linear code]]. For <math>i \in \{1, \ldots, n\}</math>, let us denote by <math>r_{i}</math> the minimum number of other [[Coordinate system|coordinates]] we have to look at to recover an erasure in [[Coordinate system|coordinate]] <math>i</math>. The number <math>r_{i}r_i</math> is said to be the ''locality of the <math>i</math>-th [[Coordinate system|coordinate]]'' of the code. The ''locality'' of the code is defined as <divmath styledisplay="text-align: center;"><mathblock>r = \textrm{max}\{r_{i}|r_i \mid i \in \{1, \ldots, n\}\}.</math></div>

An <math>[n, k, d, r]_{q}</math> ''locally recoverable code'' (LRC) is an <math>[n, k, d]_{q}_q</math> [[linear code]] <math>C \in \mathbb F_q^n</math> with locality <math>r</math>.

Let <math>C</math> be an <math>[n, k, d]_{q}_q</math>-locally recoverable code. Then an erased component can be recovered linearly,<ref>{{Citation

|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |contribution=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |title=2012 IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 |arxiv=1206.3804 }}</ref> i.e. for every <math>i \in \{1, \ldots, n\}</math>, the space of [[linear equation]]s of the code contains [[Element (mathematics)|elements]] of the form <math> x_{i}x_i = f(x_{i_{1}i_1}, \ldots, x_{i_{r}i_r})</math>, where <math>i_{j}i_j \neq i</math>.

==Optimal locally recoverable codes==