Error Correction - Disappearing Cryptography - page 44

provide a good way of computing up to 32 or 64 encodings in paral-
lel. This is done by using all of the above equations, but doing the cal-
culations with words instead of bits and XOR instead of basic arith-
metic.
This approach is a very fast way to encode the error-correcting
bits and it is a quick way to detect errors, but correcting the error can
be slow. Testing for errors can be done just by seeing if all of the c i

values are zero. If one of the c i is not zero, then the code must step

through each of the bits individually and compute the location of the
errors. This is much slower, but not any slower than computing the
code in a bitwise fashion.
The Hamming codes described in this section are particularly el-
egant, in my opinion, because of the way that the results of the

c i are
aggregated to find the location of the error. This is just a result of
the arrangements of the parity bits. The same basic algorithm could
be used no matter what order the bits were found. Any permuta-
tion of the bits

b 0001 through b 1111 would work. The recovery process

wouldn't be as elegant.
This elegant arrangement is not necessary for hardware-based
implementations because the correction of the error does not need
to be done by converting the

c i values into an index that points to
the error. It is quite possible to create a set of AND gates for each bit
that looks for a perfect match. This means the parity bits could be
placed at the beginning or the end of each block. This might simplify
stripping them out.

3.3.1 Periodic Codes

The codes described in the previous section correct only one bit error
per block. This may suffice, but it can be pretty inefficient if the block
sizesaresmall.TheHammingcodesneedthreeparitybitstocorrect
one error in four bits. That's almost a 50% loss just to correct one bit
out of four.
The Hamming codes are also less than optimal because of the
nature of the noise that can corrupt digital data. The errors may not
be randomly distributed. They are often grouped in one big burst
that might occur after an electrical jolt or some other physical event
disrupts the stream. A scratch on a CD-ROM may blur several bits
that are right next to each other. These errors would destroy any
Hamming solution that is limited to correcting one bit in each block.
Periodic codes are a better solution for occasions that demand
detecting and recovering errors that occur in bursts. In this case,
the parity bits will be distributed at regular intervals throughout the