Decoding variants of Reed-Muller codes over finite grids

DOI10.1145/3417754zbMATH Open1501.94097arXiv1908.07215OpenAlexW3099651412MaRDI QIDQ5862287FDOQ5862287

Authors: Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh 

Publication date: 7 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid. We show that their algorithm can be adapted to solve the unique decoding problem for the general family of Downset codes. Here, a downset code is specified by a family D of monomials closed under taking factors: the corresponding code is the space of evaluations of all polynomials that can be written as linear combinations of monomials from D.

Full work available at URL: https://arxiv.org/abs/1908.07215

Recommendations

• Decoding Reed-Muller codes over product sets
• Decoding Reed-Muller codes over product sets
• scientific article; zbMATH DE number 1594297
• On a recursive decoding algorithm for some subsets of first order Reed- Muller codes
• Efficiently decoding Reed-Muller codes from random errors

zbMATH Keywords

weighted distanceminimum distanceReed-Muller codeReed-Solomon codeweighted functiondownsetdownset codeunique decoding

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65) Decoding (94B35)

Cited In (2)

• Maximally Recoverable Codes for Grid-like Topologies
• Decreasing norm-trace codes

This page was built for publication: Decoding variants of Reed-Muller codes over finite grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5862287)