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\)).
Parents
- Linear \(q\)-ary code
- Locally correctable code (LCC)
- Locally decodable code (LDC) — Linear LCCs can be converted into LDCs with the same locality \(r\) [1; Sec. 2.4.1].
Children
- Hadamard code — Hadamard codes are two-query LDCs and LCCs [1,2].
- Generalized RM (GRM) code — GRM codes are LDCs and LCCs [1,2].
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 [3].
References
- [1]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [2]
- S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
- [3]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
Page edit log
- Victor V. Albert (2023-03-27) — most recent
Cite as:
“\(q\)-ary linear LCC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/q-ary_lcc