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.
Previous Page Next Page