Page 201 -

170 CHAPTER 5 / INTERNAL MEMORY

(a) A B (b)

1 1
1 0
1 1
1 0 1 0
0

C
(c) (d)

1 1
1 0 1 0
1 1
0 0 0 0
0 0

Figure 5.8 Hamming Error-Correcting Code

The simplest of the error-correcting codes is the Hamming code devised by
Richard Hamming at Bell Laboratories. Figure 5.8 uses Venn diagrams to illustrate
the use of this code on 4-bit words (M = 4).With three intersecting circles, there are
seven compartments. We assign the 4 data bits to the inner compartments (Fig-
ure 5.8a). The remaining compartments are filled with what are called parity bits.
Each parity bit is chosen so that the total number of 1s in its circle is even (Fig-
ure 5.8b).Thus, because circle A includes three data 1s, the parity bit in that circle is
set to 1. Now, if an error changes one of the data bits (Figure 5.8c), it is easily found.
By checking the parity bits, discrepancies are found in circle A and circle C but not
in circle B. Only one of the seven compartments is in A and C but not B. The error
can therefore be corrected by changing that bit.
To clarify the concepts involved, we will develop a code that can detect and
correct single-bit errors in 8-bit words.
To start, let us determine how long the code must be. Referring to Figure 5.7,
the comparison logic receives as input two K-bit values. A bit-by-bit comparison is
done by taking the exclusive-OR of the two inputs.The result is called the syndrome
word. Thus, each bit of the syndrome is 0 or 1 according to if there is or is not a
match in that bit position for the two inputs.
The syndrome word is therefore K bits wide and has a range between 0 and
K
2 - 1. The value 0 indicates that no error was detected, leaving 2 - 1 values to
K
indicate, if there is an error, which bit was in error. Now, because an error could
occur on any of the M data bits or K check bits, we must have
2 K - 1 Ú M + K