Cryptography Reference
In-Depth Information
stream of bits. For instance, every fourth bit in a stream might be a
parity bit that is computed from some of the previous bits. As before,
the location of the parity bits can be varied if the number of parity
bits per set of bits is kept constant, but it is often cleaner to arrange
for them to occur periodically.
The Hamming codes are designed to work with predefined blocks
of bits. The convolutional codes described here will work with rolling
blocks of bits that overlap. The same convolutional technique will
also work with fixed blocks, but it is left out here for simplicity. To
avoid confusion, this section will use the word
subblock
to refer to
the smaller sets of bits that are used to create the rolling block.
The periodic code will consist of a subblock of bits followed by a
set of parity bits that are computed from the bits that are present in
any number of the preceding subblocks. The parity might also de-
pend on some of the bits in the following subblocks, but this config-
uration is left out in the interest of simplicity.
A set of bits from a convolutional code might look like this:
b
(i,1)
,b
(i,2)
,b
(i,3)
,b
(i,4)
,b
(i,5)
,p
(i,1)
.
Here,
is the first
parity bit. There are five data bits and one parity bit in this example.
The parity bit could be any function of the bits in the previous
subblocks. For simplicity, let
b
(i,1)
stands for the first data bit in subblock
i
.
p
(i,1)
p
(i,1)
=
b
(i,1)
+
b
(i
−
1,2)
+
b
(i
−
2,3)
+
b
(i
−
3,4)
+
b
(i
−
4,5)
mod 2
.
That is, each parity bit is affected by one of the bits in the previous
five subblocks.
These parity bits can detect one burst of up to five bits that oc-
curs in each rolling set of five subblocks. That means that the error
will be detected if every two error bursts have at least five subblocks
between them. The error, once detected, can be fixed by asking for a
retransmission of the data.
The error can be detected by watching the trail it leaves in the
parity bits that follow it. A burst of errors in this case might affect any
of the five parity bits that come after it. When the parity bits don't
match, the previous set of five subblocks can be retransmitted to fix
the problem. It should be easy to see how spreading out the parity
bits makes it possible for the code system to detect bursts of errors.
None of the equations used to calculate the parity bits depends on
neighboring bits. In this example, there are at least five bits in the
bit stream between each of the bits used to calculate each parity bit.
In the Hamming example, each of the parity equations depended on
some adjacent bits. If both of those bits were flipped because of a
