2 ERROR CORRECTING CODES 15–2
u Information bit vector, u
0
, u
1
, … u
k–1
.
p Parity check bit vector, p
0
, p
1
, …, p
m–1
.
s Syndrome vector, s
0
, s
1
, …, s
m–1
.
15–2 The Hamming Code
Hamming’s development [Ham] is a very direct construction of a code that per-
mits correcting single-bit errors. He assumes that the data to be transmitted con-
sists of a certain number of information bits u, and he adds to these a number of
check bits p such that if a block is received that has at most one bit in error, then
p identifies the bit that is in error (which may be one of the check bits). Specifi-
cally, in Hamming’s code p is interpreted as an integer which is 0 if no error
occurred, and otherwise is the 1-origined index of the bit that is in error. Let k be
the number of information bits, and m the number of check bits used. Because the
m check bits must check themselves as well as the information bits, the value of p,
interpreted as an integer, must range from 0 to which is distinct
values. Because m bits can distinguish cases, we must have
(1)
This is known as the Hamming rule. It applies to any single error correcting (SEC)
binary FEC block code in which all of the transmitted bits must be checked. The
check bits will be interspersed among the information bits in a manner described
below.
Because p indexes the bit (if any) that is in error, the least significant bit of p
must be 1 if the erroneous bit is in an odd position, and 0 if it is in an even position
or if there is no error. A simple way to achieve this is to let the least significant bit
of p, p
0
, be an even parity check on the odd positions of the block, and to put p
0
in
an odd position. The receiver then checks the parity of the odd positions (includ-
ing that of p
0
). If the result is 1, an error has occurred in an odd position, and if the
result is 0, either no error occurred or an error occurred in an even position. This
satisfies the condition that p should be the index of the erroneous bit, or be 0 if no
error occurred.
Similarly, let the next from least significant bit of p, p
1
, be an even parity
check of positions 2, 3, 6, 7, 10, 11, … (in binary, 10, 11, 110, 111, 1010, 1011,
…), and put p
1
in one of these positions. Those positions have a 1 in their second
from least significant binary position number. The receiver checks the parity of
these positions (including the position of p
1
). If the result is 1, an error occurred in
one of those positions, and if the result is 0, either no error occurred or an error
occurred in some other position.
Continuing, the third from least significant check bit, p
2
, is made an even par-
ity check on those positions that have a 1 in their third from least significant posi-
tion number, namely positions 4, 5, 6, 7, 12, 13, 14, 15, 20, …, and p
2
is put in one
of those positions.
mk,+ mk1++
2
m
2
m
mk1.++≥
评论0