UNREASONABLE EFFECTIVENESS OF NUMBER THEORY 13

ak+4 = ak+1 + ak (8)

is obtained. Beginning with the initial condition 1000 (or almost any other

tuple, except the all-zero tuple) (8) generates the binary Galois sequence of

periodic of period length 24 - 1 = 15:

1000,10011010111; etc. (repeated periodically) .

The error correcting properties of codes based on such sequences result

from the fact that the 24 = 16 different initial conditions generate 16 different

code words of length 15, that form a "linear code" (the sum of two code

words is another code word). These code words define therefore a 4-

dimensional linear subspace of the 15-dimensional space with coordinates 0

and 1. In fact, the 16 code words describe a simplex (in 3 dimensions a

simplex is a tetrahedron) in that space and the resulting code is therefore

called a Simplex Code [4].

Its outstanding property is that every pair of code words has the same

Hamming distance (the number of 0,1 disparities), namely 2

m _ 1

= 8. Thus,

the code can recognize up to

2m~2

= 4 errors and correct up to

2m"2

- 1

errors. The price for this error correcting property is a reduced signaling

efficiency, namely m/n = 4/15, where n = 2m - 1 is the length of the code

word.

Several other codes can be derived from the simple Simplex Code. For

example, the famous (and historically early) Hamming Codes. The code

words of a Hamming Code are given by the orthogonal subspace of the

Simplex Code of the same length. Hamming codes carry n - m information

bits and m check bits, and can correct precisely one error. The functioning of

the Hamming Code for m = 3, n = 7, is illustrated in Fig. 4.