Cryptography Reference
In-Depth Information
Figure 3.3: A poor way to pack circles. If the system error can't shift
the signal more than the radius of the sphere, then the space between
the circles is wasted. Figure 3.4 shows a better approach.
units away from
111111
. It's in both spheres. If you were to try and
construct an error-correcting code using this arrangement, then you
would only be able to fit two spheres of radius 2 in the space and
the code would only be able to resist up to two errors per block. Ob-
viously the 5-bit code in the five-dimensional space is just as error-
resistant while being more efficient.
There is no reason why you need to pack only two spheres into
each space. You might want to fit in many smaller spheres. In seven-
dimensional space, you can fit in two spheres of radius 3 centered
around any two points that are seven units apart. But you can also
fit in a large number of spheres that have a radius of only 1. For
instance, you can place spheres with a single unit radius around
0000000
,
0000111
,
1110000
,
0011001
,
1001100
,
1010001
,and
1000101
.
None of these spheres overlap and the space is not full. You could
also add a sphere centered around
1111110
.Thereareeightcode
words here, so eight different messages or 3 bits of information could
be stored in each 7-bit code word. Up to one bit error could be found
and resolved.
In general, packing these higher-dimensional spaces is quite dif-
ficult to do optimally. It should be clear that there are many other
points that are not in any of eight different spheres. This reflects a
gross inefficiency.
“Constructing Error-Correcting Codes” on page 46 describes how
