[Jump to code hierarchy]

\(q\)-ary linear LCC

Description

A linear code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)).

Cousin

  • Multiplicity code— There exist multiplicity codes with rate arbitrarily close to one that are locally decodable and locally correctable from a constant error fraction [1].

Member of code lists

Primary Hierarchy

Classical Domain
Galois-field Kingdom
\(q\)-ary codeECC
Additive \(q\)-ary codeECC
Linear \(q\)-ary codeECC
Parents
Linear \(q\)-ary code
Locally correctable code (LCC)LRC Distributed-storage ECC
Locally decodable code (LDC)ECC
Linear LCCs can be converted into LDCs with the same locality \(r\) [2; Sec. 2.4.1].
\(q\)-ary linear LCC
Children
Hadamard code
Hadamard codes are two-query LDCs and LCCs [2,3].
Generalized RM (GRM) code
GRM codes are LDCs and LCCs [2,3].

References

[1]
S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
[2]
Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
[3]
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: q-ary_lcc

Cite as:
“\(q\)-ary linear LCC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/q-ary_lcc
BibTeX:
@incollection{eczoo_q-ary_lcc, title={\(q\)-ary linear LCC}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/q-ary_lcc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/q-ary_lcc

Cite as:

“\(q\)-ary linear LCC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/q-ary_lcc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/distributed_storage/q-ary_lcc.yml.