2009 | OriginalPaper | Chapter
List Decoding of Binary Codes–A Brief Survey of Some Recent Results
Author : Venkatesan Guruswami
Published in: Coding and Cryptology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We briefly survey some recent progress on list decoding algorithms for
binary
codes. The results discussed include:
Algorithms to list decode binary Reed-Muller codes of any order up to the minimum distance, generalizing the classical Goldreich-Levin algorithm for RM codes of order 1 (Hadamard codes). These algorithms are “local” and run in time polynomial in the
message
length.
Construction of binary codes efficiently list-decodable up to the Zyablov (and Blokh-Zyablov) radius. This gives a factor two improvement over the error-correction radius of traditional “unique decoding” algorithms.
The existence of binary linear
concatenated
codes that achieve list decoding capacity, i.e., the optimal trade-off between rate and fraction of worst-case errors one can hope to correct.
Explicit binary codes mapping
k
bits to
n
≤ poly(
k
/
ε
) bits that can be list decoded from a fraction (1/2 −
ε
) of errors (even for
ε
=
o
(1)) in poly(
k
/
ε
) time. A construction based on concatenating a variant of the Reed-Solomon code with dual BCH codes achieves the best known (cubic) dependence on 1/
ε
, whereas the existential bound is
n
=
O
(
k
/
ε
2
). (The above-mentioned result decoding up to Zyablov radius achieves a rate of
Ω
(
ε
3
) for the case of
constant
ε
.)
We will only sketch the high level ideas behind these developments, pointing to the original papers for technical details and precise theorem statements.