Cryptography Reference
In-Depth Information
stay zero. If these are combined in the proper order,
1011
, then they
point directly at bit
b
1011
.
These equations also correct errors that occur in the parity bits.
If one of these is flipped, only one of the equations will produces a
1. The rest yield zeros because the parity bits are not part of their
equations.
The general steps for constructing such an error-correcting code
for
n
bits can be summarized:
1. Find the smallest
k
such that
2
k
−k−
1
≤ n
. This set of equations
will encode
2
k
− k −
1
bits and produce
2
k
−
1
bits.
2. Enumerate the output bits withbinary subscripts:
b
00...01
...b
11...11
.
3. The parity bits will be the output bits with a single
1
in their
subscript.
4. Assign the input bits to the nonparity output bits. Any order
will suffice, but there is no reason not to be neat and do it in
order.
5. Compute the parity bit with a
1
at position
i
by adding up all of
the output bits with a
1
at the same position,
i
,
except
the parity
bit itself. Do the addition modulo 2.
6. To decode, compute
c
i
which is the sum of all output bits that
have a
1
in position
,
including
the parity bit. This will yield a
0
if the parity bit matches and a
1
if it doesn't. Aggregating the
c
i
values will reveal the position of the error. This code will only
detect one error.
i
for this algorithm? Given
that the number of parity bits is proportional to the log of the num-
ber of input bits, it is tempting to lump the entire file into one big
block and use only a small number of parity bits. This requires a large
number of additions. There are about
n log n
2
Whatisthemostefficientchoiceof
k
additions in a block of
n
bits. Large blocks require fewer parity bits but need more compu-
tation. They also correct only one error in the entire block and this
substantially limits their usefulness. The best trade off must be based
on the noisiness of the channel carrying the information.
Implementations of Hamming codes like this one are often fastest
when they are done a word at a time. Most CPUs have instructions
that will do a bitwise XOR of an instruction word, which is usually ei-
ther 32 or 64 bits long. XOR is addition modulo 2. These fast XORs
