Coding Theory

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

the 14 points (lying in a 7-d subspace) obtained by replacing each '0' by '-1', or
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

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.