Hamming Code
So far, we have examined the number of bits required to cover all of the possible single-bit error states in a transmission. But how do we manipulate those bits to discover which state has occurred? A technique developed by R.W. Hamming provides a practical solution.
Positioning the Redundancy Bits
The Hamming code can be applied to data units of any length and uses the relationship between data and redundancy bits discussed above. For example, a seven-bit ASCII code requires four redundancy bits that can be added to the end of the data unit or interspersed with the original data bus. In Figure 6.3-2, these bits are placed in positions 1, 2, 4, and 8 (the positions in an 11-bit sequence that are powers of 2). For clarity in the examples below, we refer to these bits as ri, r2, r4, and r8.
- 11 10 98765432 1
[ Redundancy bits J
Fig. 6.3-2 Positions of redundancy bits in Hamming code
[ Redundancy bits J
Fig. 6.3-2 Positions of redundancy bits in Hamming code
In the Hamming code, each r bit is the VRC bit for one combination of data bits; r2 is the VRC bit for another combination of data bits, and so on. The combinations used to calculate each of the four r values for a seven-bit data sequence are as follows:
r1: bits 1, 3, 5, 7, 7, 11 r2: bits 2, 3, 6, 7,10, 11 r4: bits 4, 5, 6, 7 r8: bits 8, 7, 10, 11
Each data bit may be included in more than one VRC calculation. In the sequences above, for example, each of the original data bits is included in at least two sets, while the r bits are included in only one.
To see the pattern behind this strategy, look at the binary representation of each bit position. The r1 bit is calculated using all bit positions whose binary representation includes a 1 in the rightmost position, The r2 bit is calculated using all bit positions with a 1 in the second position, and so on (see Figure 6.3-3).
Calculating the r Values
Figure 6.3-4 shows a Hamming code implementation for an ASCII character. In the first step, we fill in each bit of the original character in its appropriate position in the 11-bit unit. In the subsequent steps, we calculate the even parities for the various bit combinations. The parity value for each combination is the value of the corresponding r bit. For example, the value of r1 is calculated to provide even parity for a combination of bits 3, 5, 7, 9, and 12. The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10, and 11, and so on. The final 11-bit code is sent through the transmission line.
Error Detection and Correction
Now imagine that by the time the above transmission is received, the number 7 bit has been changed from 1 to 0 (see Figure 6.3-5).
- Fig. 6.3-3 Redundancy bits calculation
Fig. 6.3-4 Example of redundancy bit calculation
Fig. 6.3-4 Example of redundancy bit calculation
Post a comment