Revisiting the Reed-Muller Locally Correctable Codes
2019
Local codes are a special kind of error-correcting codes. Locally correctable codes (LCCs) are one type of local codes. LCCs can efficiently recover any coordinate of its corrupted encoding by probing only a few but not all fraction of the corrupted word. A q-ary LCC which encodes length k messages to length N codewords with relative distance Δ has three parameters: r, δ and ϵ. r is called query complexity recording the number of queries. δ is called tolerance fraction measuring the relative distance between encoding codewords and its corrupted codes which can be locally decoded. ϵ is called error probability showing the coordinate of its corrupted encoding fail to be recovered with probability at most ϵ. One fundamental problem in LCCs is to determine the trade-off among rate, distance and query complexity. But for a specific LCC, focus is on query complexity, tolerance fraction and error probability. Reed-Muller codes (RM codes) are the most presentative LCCs. In order to understand the "local" more clearly, we revisit local correctors for RM codes and analyze them in detail: 1)The decoding procedures; 2)The role of Reed-Solomon codes (RS codes) in decoding RM LCCs; 3)Other local correctors for RM codes. How parameters including r, δ and ϵ change in RM LCCs have been analyzed in different correctors. We believe this paper can help us understand local codes better and grasp the main soul of this research direction.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
0
Citations
NaN
KQI