14 M. R. SCHROEDER

Figure 4. Venn diagram to illustrate the single-error correcting property of the

original Hamming code having 4 information bits (fat Os and Is) and 3 check

bits (thin Os and Is). The parity in each of the 3 circles must be even. A

single error, which entails one or several odd parities, can be uniquely

detected and corrected.

The n - m = 4 information bits, say 1001, are entered into the 4 inner

areas of the Venn diagram (indicated by fat characters in Fig. 4). The m = 3

check bits (thin characters) are entered into the 3 outer areas such that the

parity in each circle is even (the sum modulo 2 equals 0).

The receiver of a code word, which may have been contaminated in

transmission, checks the parity in each circle and marks all circles with odd

parity. The intersection of these circles then specifies uniquely a single bit

error (including in the check bits themselves). These 3 parity checks allow