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
Previous Page Next Page