Locally recoverable code: Difference between revisions

Content deleted Content added
OAbot (talk | contribs)
m Open access bot: arxiv updated in citation with #oabot.
 
(4 intermediate revisions by 3 users not shown)
Line 46:
|doi= 10.1007/s10623-022-01046-y
|publisher=IEEE
|arxiv=2104.01434
}}</ref><ref>{{Citation
|first1=K.
Line 67 ⟶ 68:
It is well-known that LRC is a [[linear code|code]] that needs only a limited [[Set (mathematics)|set]] of other symbols to be accessed in order to restore every symbol in a codeword. This idea is very important for distributed and [[cloud storage]] systems since the most common error case is when one storage node fails (erasure). The main objective is to recover as much [[data]] as possible from the fewest additional storage nodes in order to restore the node. Hence, Locally Recoverable Codes are crucial for such systems.
 
The following [[definition]] of the LRC follows from the description above: an <math>[n, k, r]</math>-Locally Recoverable Code (LRC code) of length <math>n</math> is a [[linear code|code]] that produces an <math>n</math>-symbol codeword from <math>k</math> information symbols, and for any symbol of the codeword, there exist at most <math>r</math> other symbols such that the value of the symbol can be recovered from them. The locality [[parameter]] satisfies <math>1 \leq r \leq k</math> because the entire codeword can be found by accessing <math>k</math> symbols other than the erased symbol. Furthermore, Locally Recoverable Codes, having the minimum [[Hamming distance|distance]] <math>d</math>, can recover <math>d-1</math> erasures.
 
==Definition==
Line 156 ⟶ 157:
 
'''Theorem''' The minimum [[Hamming distance|distance]] of <math>[n,k,d]_q</math>-LRC having locality <math>r</math> and availability <math>t</math> satisfies the [[Upper and lower bounds|upper bound]]
<mathdiv displaystyle="blocktext-align: center;"><math>d \leq n - \sum_{i=0}^t \left\lfloor\frac{k-1}{r^i}\right\rfloor.</math></div>
If the code is [[Systematic code|systematic]] and locality and availability apply only to its information symbols, then the code has information locality <math>r</math> and availability <math>t</math>, and is called <math>(r,t)_i</math>-LRC.<ref>{{Citation |first1=I. |last1=Tamo |first2=A. |last2=Barg |contribution=Bounds on locally recoverable codes with multiple recovering sets |pages=691–695 |___location=Honolulu, HI, USA |title=2014 IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874921|arxiv=1402.0916 |isbn=978-1-4799-5186-4 }}</ref>
 
'''Theorem'''<ref>{{Citation
|first1=A. |last1=Wang |first2=Z. |last2=Zhang |title=Repair locality with multiple erasure tolerance |pages=6979–6987 |journal=IEEE Transactions on Information Theory |date=2014 |volume=60 |issue=11 |doi=10.1109/TIT.2014.2351404|arxiv=1306.4774 }}</ref> The minimum [[Hamming distance|distance]] <math>d</math> of an <math>[n,k,d]_q</math> linear <math>(r,t)_i</math>-LRC satisfies the [[Upper and lower bounds|upper bound]]
<mathdiv displaystyle="blocktext-align: center;"><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2.</math></div>
 
== References ==
Line 167 ⟶ 168:
{{reflist}}
 
[[Category:Cryptography]]
 
[[Category:Information theory]]
 
[[Category:Mathematics]] [[Category:Cryptography]] [[Category:Information theory]] [[Category:Error detection and correction]]