Error Correction - Disappearing Cryptography - page 35

sure the distance between two numbers as the number of different
bits. So 11111100 and 11111101 are one unit apart because they dif-
fer in only one bit. So are 11111100 and 01111100. But 01111100 and
11111101 are two units apart. This distance is often called the Ham-
ming distance .
This measure has the same feel as finding the distance between
two corners in a city that is laid out on a Manhattan-like grid. The
distance between the corner at 10th Avenue and 86th Street and the
corner at 9th Avenue and 83rd Street is four blocks, although inMan-
hattan they are blocks of different lengths. You just sumup the differ-
ences along each of the different dimensions. In the street example,
there are two dimensions that are the avenues that run north and
south or the streets that run east and west. In the numerical exam-
ple, each bit position is a different dimension and the 8-bit examples
above have eight dimensions. Error-correcting codes

spread the information
out over a number of
bits in the same fashion
as the spread-spectrum
algorithms in
Chapter 14.

The simplest example of an error-correcting code uses 3 bits to
encode each bit of data. The code can correct one error in a bit but
not two. There are eight possible combinations of three bits: 000,
001, 010, 011, 100, 101, 110, and 111. You can think of these as the
eight corners of a cube as shown in Figure 3.1. A message 0 can be
encoded as “000,” and a 1 can be encoded as “111”. Imagine there
is an error and the “000” was converted into a “001”. The closest
possible choice, “000”, is easy to identify.
The sphere of “000” includes all points that are at most one Ham-
ming unit away: 001, 010, and 100. Two errors, however, nudge a
point into the adjacent sphere.
Obviously, the technique can be extended into higher-dimen-
sional spaces. The trick is to find an optimal number of points that
can be packed into a space. Imagine, for instance, a five-dimension-
al space made up of the points 00000, 00001, 00010 11111 .Every

point has an opposite point that is five units away from it. 00000 is
five steps away from 11111 and 10111 is five units away from 01000 .It
is easy to construct a sphere with a radius of two units around each
point. That means 0 can be encoded as 00000 and 1 can be encoded
as 11111 . Up to two errors could occur and the correct answer would
be found. 10110 is two units away from 11111 , so it would fall in its
sphere of influence and be decoded as a 1 .
Generally, odd-dimensional spaces are much better than even-
dimensional spaces for this basic scheme. Imagine the six-dimen-
sional space created from the points 000000, 000001, 000010

,...,

111111 .
Both 000000 and 111111 are six units apart. But if you draw a sphere
of radius 3 around each point, then the spheres overlap. The point
010101 , for instance, is both three units away from 000000 and three

,...,