Error Control with Binary Cyclic Codes

Martin Grymel

Abstract

Error-control codes provide a mechanism to increase the reliability of digital data being processed, transmitted, or stored under noisy conditions. Cyclic codes constitute an important class of error-control code, oUering powerful error detection and correction capabilities. They can easily be generated and veriVed in hardware, which makes them particularly well suited to the practical use as error detecting codes. A cyclic code is based on a generator polynomial which determines its properties including the speciVc error detection strength. The optimal choice of polynomial depends on many factors that may be inWuenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a Wexible choice of polynomial to be applied to diUerent requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-eXcient and minimise implementation resources. It can be shown that the correction of a single-bit error on the basis of a cyclic code is equivalent to the solution of an instance of the discrete logarithm problem. A new approach is proposed for computing discrete logarithms; this leads to a generic deterministic algorithm for analysed group orders that equal Mersenne numbers with an exponent of a power of two. The algorithm exhibits a worst-case runtime in the order of the square root of the group order and constant space requirements. This thesis establishes new relationships for Vnite Velds that are represented as the polynomial ring over the binary Veld modulo a primitive polynomial. With a subset of these properties, a novel approach is developed for the solution of the discrete logarithm in the multiplicative groups of these Velds. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of deVning polynomial, enabling an eXcient correction of single-bit errors based on the corresponding cyclic codes.

The thesis is available as PDF (4.8MB).