Hardware Reference
In-Depth Information
Bit
1 checks bits 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21.
Bit
2 checks bits 2, 3, 6, 7, 10, 11, 14, 15, 18, 19.
Bit
4 checks bits 4, 5, 6, 7, 12, 13, 14, 15, 20, 21.
Bit
8 checks bits 8, 9, 10, 11, 12, 13, 14, 15.
Bit 16 checks bits 16, 17, 18, 19, 20, 21.
In general, bit b is checked by those bits b 1 , b 2 , ..., b j such that b 1 +
b 2 +
...
+
b . For example, bit 5 is checked by bits 1 and 4 because1+4=5. Bit6is
checked by bits 2 and 4 because2+4=6,andsoon.
Figure 2-15 shows construction of a Hamming code for the 16-bit memory
word 1111000010101110. The 21-bit codeword is 001011100000101101110. To
see how error correction works, consider what would happen if bit 5 were inverted
by an electrical surge on the power line. The new codeword would be
001001100000101101110 instead of 001011100000101101110. The 5 parity bits
will be checked, with the following results:
b j
=
Parity bit
1 incorrect (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 contain five 1s).
Parity bit
2 correct (2, 3, 6, 7, 10, 11, 14, 15, 18, 19 contain six 1s).
Parity bit
4 incorrect (4, 5, 6, 7, 12, 13, 14, 15, 20, 21 contain five 1s).
Parity bit
8 correct (8, 9, 10, 11, 12, 13, 14, 15 contain two 1s).
Parity bit 16 correct (16, 17, 18, 19, 20, 21 contain four 1s).
The total number of 1s in bits 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, and 21 should be an
even number because even parity is being used. The incorrect bit must be one of
the bits checked by parity bit 1—namely, bit 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, or 21.
Parity bit 4 is incorrect, meaning that one of bits 4, 5, 6, 7, 12, 13, 14, 15, 20, or 21
is incorrect. The error must be one of the bits in both lists, namely, 5, 7, 13, 15, or
21. However, bit 2 is correct, eliminating 7 and 15. Similarly, bit 8 is correct,
eliminating 13. Finally, bit 16 is correct, eliminating 21. The only bit left is bit 5,
which is the one in error. Since it was read as a 1, it should be a 0. In this manner,
errors can be corrected.
A simple method for finding the incorrect bit is first to compute all the parity
bits. If all are correct, there was no error (or more than one). Then add up all the
incorrect parity bits, counting 1 for bit 1, 2 for bit 2, 4 for bit 4, and so on. The re-
sulting sum is the position of the incorrect bit. For example, if parity bits 1 and 4
are incorrect but 2, 8, and 16 are correct, bit 5 (1 + 4) has been inverted.
Search WWH ::




Custom Search