Cryptography Reference
In-Depth Information
Figure 3.4: A better approach to packing the circles from Figure 3.3.
This is about 86.6% of the original height. It is wider by one half of
the radius of a circle.
to build general Hamming codes. It is possible to use the algorithm
given there to construct an error-correcting code that packs 4 bits
of information, or 16 different messages, into one 7-bit code word.
That's one extra bit of data. The code can also resist up to 1 bit of
error. The 16 centers generated by this method are:
0000000 0001111 0010011 0011100
0100101 0101010 0110110 0111001
1000110 1001001 1010101 1011010
1100011 1101100 1110000 1111111
There aremany other types of error-correcting codes. Themetaphor
of sphere packing is a good way to understand the basic idea, but it
offerslittleguidanceonhowitcanbedoneeffectively. Itiseasyto
imagine stacking pool balls in a rack, but it is impossible to visualize
howtodothisinmultipledimensions—especiallyiftheHamming
distance is used.
In practice, error-correcting codes rest on algorithms that take the
data and add extra
parity bits
that can be used to recover the data.
The parity bits “puff up” the data into more dimensions and move
the points away from each other. For instance, in four dimensions
the points
1110
and
1111
are right next to each other. But if three
parity bits are added to the end of each one, the results,
1110000
and
1111111
,arefourunitsapart.
