Error Control With Binary Cyclic Codes

  • Martin Grymel

Student thesis: Phd


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, offering powerful error detection and correction capabilities. They can easily be generated and verified 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 specific error detection strength. The optimal choice of polynomial depends on many factors that may be influenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a flexible choice of polynomial to be applied to different requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-efficient 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 finite fields that are represented as the polynomial ring over the binary field 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 fields. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of defining polynomial, enabling an efficient correction of single-bit errors based on the corresponding cyclic codes.
Date of Award1 Aug 2013
Original languageEnglish
Awarding Institution
  • The University of Manchester
SupervisorSteve Furber (Supervisor) & James Garside (Supervisor)


  • Linear Feedback Shift Register
  • Discrete Logarithm
  • Algorithm
  • Generic
  • Polynomial Ring
  • Primitive Polynomial
  • Maximum Length Sequence
  • Deterministic
  • LFSR
  • SpiNNaker
  • Parallel
  • Circuit
  • Error Control
  • Error Detection
  • Error Correction
  • Cyclic Redundancy Checksum
  • CRC
  • Programmable
  • Cyclic Code

Cite this