List decoding of the first-order binary Reed-Muller codes
- 1 September 2007
- journal article
- Published by Pleiades Publishing Ltd in Problems of Information Transmission
- Vol. 43 (3), 225-232
- https://doi.org/10.1134/s0032946007030052
Abstract
A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 − ɛ) about the received vector and has the complexity of O(n ln2(min{ɛ −2, n})) binary operations.Keywords
This publication has 4 references indexed in Scilit:
- List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- List Decoding of$q$-ary Reed–Muller CodesIEEE Transactions on Information Theory, 2004
- Learning Polynomials with Queries: The Highly Noisy CaseSIAM Journal on Discrete Mathematics, 2000
- A hard-core predicate for all one-way functionsPublished by Association for Computing Machinery (ACM) ,1989