Hardware Reference
In-Depth Information
This theoretical lower limit can be achieved using a method due to Richard
Hamming (1950). Before taking a look at Hamming's algorithm, let us look at a
simple graphical representation that clearly illustrates the idea of an error-cor-
recting code for 4-bit words. The Venn diagram of Fig. 2-14(a) contains three cir-
cles,
A
,
B
, and
C
, which together form seven regions. As an example, let us encode
the 4-bit memory word 1100 in the regions
AB
,
ABC
,
AC
, and
BC
, 1 bit per region
(in alphabetical order). This encoding is shown in Fig. 2-14(a).
A
A
A
Error
0
0
0
0
1
C
C
C
1
1
1
1
1
1
11
0
0
0
0
0
Parity
bits
B
B
B
(a)
(b)
(c)
Figure 2-14.
(a) Encoding of 1100. (b) Even parity added. (c) Error in
AC
.
Next we add a parity bit to each of the three empty regions to produce even
parity, as illustrated in Fig. 2-14(b). By definition, the sum of the bits in each of
the three circles,
A
,
B
, and
C
, is now an even number. In circle
A
, we have the four
numbers 0, 0, 1, and 1, which add up to 2, an even number. In circle
B
, the num-
bers are 1, 1, 0, and 0, which also add up to 2, an even number. Finally, in circle
C
,
we have the same thing. In this example all the circles happen to be the same, but
sums of 0 and 4 are also possible in other examples. This figure corresponds to a
codeword with 4 data bits and 3 parity bits.
Now suppose that the bit in the
AC
region goes bad, changing froma0toa1,
as shown in Fig. 2-14(c). The computer can now see that circles
A
and
C
have the
wrong (odd) parity. The only single-bit change that corrects them is to restore
AC
back to 0, thus correcting the error. In this way, the computer can repair single-bit
memory errors automatically.
Now let us see how Hamming's algorithm can be used to construct error-cor-
recting codes for any size memory word. In a Hamming code,
r
parity bits are
added to an
m
-bit word, forming a new word of length
m
r
bits. The bits are
numbered starting at 1, not 0, with bit 1 the leftmost (high-order) bit. All bits
whose bit number is a power of 2 are parity bits; the rest are used for data. For ex-
ample, with a 16-bit word, 5 parity bits are added. Bits 1, 2, 4, 8, and 16 are parity
bits, and all the rest are data bits. In all, the memory word has 21 bits (16 data, 5
parity). We will (arbitrarily) use even parity in this example.
Each parity bit checks specific bit positions; the parity bit is set so that the total
number of 1s in the checked positions is even. The bit positions checked by the
parity bits are
+
