Coding Theory

Home pages: JEHS | Stats | SCU | WRI | Maths | Warwick

Overview

Error-correcting codes are designed to transmit information (a 'signal') concisely and reliably, using sequences of code-words. To minimise the effect of errors or noise in transmission, the code-words must be clearly different from each other.

For example, one code comprises the following sixteen binary code-words of length seven:

  1101000    0010111
  0110100    1001011
  0011010    1100101
  0001101    1110010
  1000110    0111001
  0100011    1011100
  1010001    0101110
  0000000    1111111
which mutually differ in at least 3 places, implying that if each received code-word contains at most 1 error, then the correct signal can still be extracted. Thus if the first code-word 1101000 is sent, but becomes corrupted en route and is received as 1111000 (with one error), it will still be correctly decoded as 1101000 (the closest valid code-word ).

Coding theory can identify points at which to evaluate a function for efficient numerical integration. For example, a parity bit can be added to each of the above code-words, giving 16 code-words of length 8, of which the following 14 have four '0's and four '1's:

  11010001    00101110
  01101001    10010110
  00110101    11001010
  00011011    11100100
  10001101    01110010
  01000111    10111000
  10100011    01011100
from which to construct nice configurations of points around the origin in 8-dimensional space, such as
  1. the 14 points (lying in a 7-d subspace) obtained by replacing each '0' by '-1', or

  2. the 16*14 = 224 points obtained by replacing each '1' independently by '+1' or '-1' (and by adding the 16 points with one coordinate = +2 or -2, and the other seven all 0, we obtain Gosset's 8-dimensional polytope, an important configuration in geometry, that also arises as the minimal vectors in the E8 lattice, or equivalently as the centres of the 240 'spheres' touching a given one in the densest possible 8-dimensional sphere packing).
Note also that the matrix
  1101000
  0110100
  0011010
  0001101
  1000110
  0100011
  1010001
is the incidence matrix of a regular graph, also represents the balanced incomplete block design ABD BCE CDF DEG AEF BFG ACG, and (by adjoining a row and a column of '1's) produces a Hadamard matrix, important throughout combinatorial theory. The symmetries of structures like these are best studied using group theory.


Books

MacWilliams & Sloane (1977)
The coding theory 'Bible' (or at least the Old Testament).
van Lint (1992)
a contender for the title of 'New Testament'.
Assmus & Key (1992)
Cameron & van Lint (1991)
Conway & Sloane (1992)

WWW Resources

E.F.Assmus
Home page.
Neil J.A.Sloane
Home page.

Cryptic Quotes

I have always sought to be understood, and when my words were garbled by critics or colleagues, I considered it no fault of theirs but my own, because I had not been clear enough to be comprehended.
Henri Matisse, Testimonial.

We exchanged many frank words in our respective languages.
Peter Cook, Beyond the Fringe.

This page is maintained by J.E.H.Shaw@warwick.ac.uk.