Binary Codes
43
Table 2.9 Generation of Hamming code.
P 1
P 2
D 1
P 3
D 2
D 3
D 4
Data bits (without parity)
0
1
1
0
Data bits with parity bit P 1
1
0
1
0
Data bits with parity bit P 2
1
0
1
0
Data bits with parity bit P 3
0
1
1
0
Data bits with parity
1
1
0
0
1
1
0
The most commonly used Hamming code is the one that has a code word length of seven bits with
four message bits and three parity bits. It is also referred to as the Hamming (7, 4) code. The code word
sequence for this code is written as P 1 P 2 D 1 P 3 D 2 D 3 D 4 , with P 1 , P 2 and P 3 being the parity bits and D 1 ,
D 2 , D 3 and D 4 being the data bits. We will illustrate step by step the process of writing the Hamming
code for a certain group of message bits and then the process of detection and identification of error
bits with the help of an example. We will write the Hamming code for the four-bit message 0110
representing numeral ‘6’. The process of writing the code is illustrated in Table 2.9, with even parity.
Thus, the Hamming code for 0110 is 1100110. Let us assume that the data bit D 1 gets corrupted
in the transmission channel. The received code in that case is 1110110. In order to detect the error,
the parity is checked for the three parity relations mentioned above. During the parity check operation
at the receiving end, three additional bits X, Y and Z are generated by checking the parity status of
P 1 D 1 D 2 D 4 , P 2 D 1 D 3 D 4 and P 3 D 2 D 3 D 4 respectively. These bits are a ‘0’ if the parity status is okay,
and a ‘1’ if it is disturbed. In that case, ZYX gives the position of the bit that needs correction. The
process can be best explained with the help of an example.
Examination of the first parity relation gives X =1 as the even parity is disturbed. The second
parity relation yields Y = 1 as the even parity is disturbed here too. Examination of the third relation
gives Z = 0 as the even parity is maintained. Thus, the bit that is in error is positioned at 011 which is
the binary equivalent of ‘3’. This implies that the third bit from the MSB needs to be corrected. After
correcting the third bit, the received message becomes 1100110 which is the correct code.
Example 2.6
By writing the parity code (even) and threefold repetition code for all possible four-bit straight binary
numbers, prove that the Hamming distance in the two cases is at least 2 in the case of the parity code
and 3 in the case of the repetition code.
Solution
The generation of codes is shown in Table 2.10. An examination of the parity code numbers reveals
that the number of bit disagreements between any pair of code words is not less than 2. It is either 2
or 4. It is 4, for example, between 00000 and 10111, 00000 and 11011, 00000 and 11101, 00000 and
11110 and 00000 and 01111. In the case of the threefold repetition code, it is either 3, 6, 9 or 12 and
therefore not less than 3 under any circumstances.
Example 2.7
It is required to transmit letter ‘A’ expressed in the seven-bit ASCII code with the help of the Hamming
(11, 7) code. Given that the seven-bit ASCII notation for ‘A’ is 1000001 and that the data word gets
43
Table 2.9 Generation of Hamming code.
P 1
P 2
D 1
P 3
D 2
D 3
D 4
Data bits (without parity)
0
1
1
0
Data bits with parity bit P 1
1
0
1
0
Data bits with parity bit P 2
1
0
1
0
Data bits with parity bit P 3
0
1
1
0
Data bits with parity
1
1
0
0
1
1
0
The most commonly used Hamming code is the one that has a code word length of seven bits with
four message bits and three parity bits. It is also referred to as the Hamming (7, 4) code. The code word
sequence for this code is written as P 1 P 2 D 1 P 3 D 2 D 3 D 4 , with P 1 , P 2 and P 3 being the parity bits and D 1 ,
D 2 , D 3 and D 4 being the data bits. We will illustrate step by step the process of writing the Hamming
code for a certain group of message bits and then the process of detection and identification of error
bits with the help of an example. We will write the Hamming code for the four-bit message 0110
representing numeral ‘6’. The process of writing the code is illustrated in Table 2.9, with even parity.
Thus, the Hamming code for 0110 is 1100110. Let us assume that the data bit D 1 gets corrupted
in the transmission channel. The received code in that case is 1110110. In order to detect the error,
the parity is checked for the three parity relations mentioned above. During the parity check operation
at the receiving end, three additional bits X, Y and Z are generated by checking the parity status of
P 1 D 1 D 2 D 4 , P 2 D 1 D 3 D 4 and P 3 D 2 D 3 D 4 respectively. These bits are a ‘0’ if the parity status is okay,
and a ‘1’ if it is disturbed. In that case, ZYX gives the position of the bit that needs correction. The
process can be best explained with the help of an example.
Examination of the first parity relation gives X =1 as the even parity is disturbed. The second
parity relation yields Y = 1 as the even parity is disturbed here too. Examination of the third relation
gives Z = 0 as the even parity is maintained. Thus, the bit that is in error is positioned at 011 which is
the binary equivalent of ‘3’. This implies that the third bit from the MSB needs to be corrected. After
correcting the third bit, the received message becomes 1100110 which is the correct code.
Example 2.6
By writing the parity code (even) and threefold repetition code for all possible four-bit straight binary
numbers, prove that the Hamming distance in the two cases is at least 2 in the case of the parity code
and 3 in the case of the repetition code.
Solution
The generation of codes is shown in Table 2.10. An examination of the parity code numbers reveals
that the number of bit disagreements between any pair of code words is not less than 2. It is either 2
or 4. It is 4, for example, between 00000 and 10111, 00000 and 11011, 00000 and 11101, 00000 and
11110 and 00000 and 01111. In the case of the threefold repetition code, it is either 3, 6, 9 or 12 and
therefore not less than 3 under any circumstances.
Example 2.7
It is required to transmit letter ‘A’ expressed in the seven-bit ASCII code with the help of the Hamming
(11, 7) code. Given that the seven-bit ASCII notation for ‘A’ is 1000001 and that the data word gets