On complexity of decoding binary cyclic codes using covering polynomials.

Abstract

The problem of devising efficient, simple and flexible decoders for cyclic block codes has attracted a great deal of attention. Many of the proposed algorithms fall into the large class of error-trapping-based algorithms. The covering polynomial method is perhaps the simplest and most flexible of these. Like the other members of the family, it is computationally simple, amenable to parallel implementation, and is capable of decoding over a variety of channels. The determination of a minimal set of covering polynomials (a minimal complexity covering polynomial decoder) for a given cyclic code is an open problem. This thesis is concerned with obtaining a minimal set of covering polynomials for binary cyclic codes and other related problems. A computationally efficient algorithm to generate minimal covering polynomial sets for codes of rate $R < 2/\tau$ is proposed, where $\tau$ is the number of errors to be corrected. The algorithm is further refined to give simple recursive formulas that determine the covering polynomials for a given code with $\tau < 9.$ The minimal covering polynomial sets for important special cases of codes of rate $R \geq 2/\tau$ are also presented. These are analytically shown to be optimal and can be constructed by closed form specifications. The results are applied to determine the minimal complexity covering polynomial decoders for a large number of the short to medium length codes of practical interest. The asymptotic complexity of the covering polynomial method and other general decoding algorithms is also investigated.