Cryptography Reference
In-Depth Information
burst of error noise, then the errors would cancel out and the error
would be recoverable.
Recovering a parity error is normally not possible with a simple
Section 14.4.2 describes
acodingschemethat
can produce the right
parity values when only
some of the bits can be
changed, a solution
that's useful when you
only want to tweak the
least damageable parts
of an image.
code like this example. If one of the parity bits doesn't agree in this
example, then the error could have been introduced by an error in
six different bits. Finding which one is impossible. To some extent,
a larger burst of errors will make the job easier. For instance, if three
bits in a row are flipped, then three consecutive parity bits will also
be flipped. If the parity bits are examined individually, then each one
could have been caused by up to six different errors. But periodic
codes like this are designed to handle bursts of errors. So it is accept-
able to assume that the three errors would be adjacent to each other.
This limits the location to two different spots.
For instance, here is a data stream with correct parity bits:
...
01010 0 01010 1 1001 1 01111 1 00011 1
...
If the first three bits are flipped, then the first three parity bits are also
flipped:
...
10110 1 01010 0 11001 0 01111 1 00011 1
...
Each individual error could have occurred in any of the previous five
blocks, but the overlapping nature of the code limits the error to the
first block shown here or either of the two blocks that preceded it.
If five bits were flipped in a row, then the exact location would be
known and it would be possible to correct the errors. This pushes
the code to an extreme and it would be better not to hope for bursts
to come at the extreme limit of the ability of the codes to detect the
errors.
Both [LJ83] and [Ara88]
are good sources.
The periodic code described in this section is a goodway to detect
bursts of errors, but it cannot help correct them unless the burst is at
the extreme. There is some information available, but it is clearly not
enough to recover the data.
3.4 Summary
Error-correcting codes are one of the most important tools for build-
ing digital systems. They allow electronic designers to correct the
random errors that emerge from nature and provide the user with
some digital precision. If the electronics were required to offer per-
fect accuracy, then they would be prohibitively expensive.
These codes are useful for correcting problems that emerge from
the transmission systems.
It might be desirable, for instance, for