|
==Locally recoverable codes with availability==
A code <math>C</math> has all-symbol locality <math>r</math> and availability <math>t</math> if every code symbol can be recovered from <math>t</math> disjoint repair sets of other symbols, each [[Set (mathematics)|set]] of [[Cardinality|size]] at most <math>r</math> symbols. Such codes are called <math>(r,t)_a</math>-LRC.<ref>{{Citation
'''Definition'''<ref>{{Citation
|first1=P. |last1=Huang |first2=E. |last2=Yaakobi |first3=H.|last3=Uchikawa |first4=P.H.|last4=Siegel |title="Linear locally repairable codes with availability" |chaptercontribution=Linear locally repairable codes with availability |pages=1871–1875 |___location=Hong Kong, China |publishertitle=2015 IEEE International Symposium on Information Theory |date=2015 |doi=10.1109/ISIT.2015.7282780|isbn=978-1-4673-7704-1 }}</ref> A code <math>C</math> has all-symbol locality <math>r</math> and availability <math>t</math> if every code symbol can be recovered from <math>t</math> disjoint repair [[Disjoint sets|sets]] of other symbols, each [[Set (mathematics)|set]] of [[Cardinality|size]] at most <math>r</math> symbols. Such codes are called <math>(r,t)_a</math>-LRC.
'''Theorem'''<ref>{{Citation |first1=I. |last1=Tamo |first2=A. |last2=Barg |title="Bounds on locally recoverable codes with multiple recovering sets" |chapter=Bounds on locally recoverable codes with multiple recovering sets |pages=691–695 |___location=Honolulu, HI, USA |publisher=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> 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]]
< divmath styledisplay=" text-align: center;block" ><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>▼▲<div style="text-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.
'''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]]
< divmath styledisplay=" text-align: center;block" ><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2 .</math> </div>.▼
▲<div style="text-align: center;"><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2</math></div>.
== References ==
| 