Article ID Journal Published Year Pages File Type
420876 Discrete Applied Mathematics 2006 17 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,