Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420876 | Discrete Applied Mathematics | 2006 | 17 Pages |
Abstract
Reed–Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlognnlogn and corrects most error patterns of weight (dlnd)/2(dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability pp, which yields a vanishing output error probability on long codes.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ilya Dumer, Kirill Shabunov,