Coding Theory
Home pages:
JEHS 
Stats 
SCU 
WRI 
Maths 
Warwick
Overview
Errorcorrecting codes
are designed to transmit information (a 'signal') concisely and reliably,
using sequences of codewords.
To minimise the effect of errors or noise in transmission,
the codewords must be clearly different from each other.
For example, one code
comprises the following sixteen binary codewords 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 codeword contains at most 1 error,
then the correct signal can still be extracted.
Thus if the first codeword 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 codeword ).
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 codewords,
giving 16 codewords 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 8dimensional space,
such as

the 14 points (lying in a 7d 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 8dimensional
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 8dimensional
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.