Content deleted Content added
m Open access bot: arxiv, doi updated in citation with #oabot. |
No edit summary |
||
Line 62:
==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 <math>i</math>. The number <math>r_{i}</math> is said to be the ''locality of the <math>i</math>-th coordinate'' of the code. The ''locality'' of the code is defined as <div style="text-align: center;"><math>r = \textrm{max}\{r_{i}|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}</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}</math>-locally recoverable code. Then an erased component can be recovered linearly,<ref>{{Citation
|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |title="Locally Repairable Codes" |chapter=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publisher=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|linear equations ]] of the code contains elements of the form <math> x_{i} = f(x_{i_{1}}, \ldots, x_{i_{r}})</math>, where <math>i_{j} \neq i</math>.
==Optimal Locally Recoverable Codes==
'''Theorem'''<ref>{{Citation
|first1=V. |last1=Cadambe |first2=A. |last2=Mazumdar |title="An upper bound on the size of locally recoverable codes" |chapter=An upper bound on the size of locally recoverable codes |pages=1–5 |___location=Calgary, AB, Canada |publisher=International Symposium on Network Coding |date=2013 |doi=10.1109/NetCod.2013.6570829|arxiv=1308.3200 |isbn=978-1-4799-0823-3 }}</ref> Let <math>n = (r+1)s</math> and let <math>C</math> be an <math>[n, k, d]_{q}</math>-locally recoverable code having <math>s</math> disjoint locality [[Disjoint sets|sets]] of size <math>r+1</math>. Then <div style="text-align: center;"><math>d \leq n - k - \left\lceil\frac{k}{r}\right\rceil + 2</math></div>
An <math>[n, k, d, r]_{q}</math>-LRC <math>C</math> is said to be optimal if the minimum distance of <math>C</math> satisfies <div style="text-align: center;"><math>d = n - k - \left\lceil\frac{k}{r}\right\rceil + 2</math></div>
| |||