42
Digital Electronics
sequence to get the cyclic code. The code word so generated is completely divisible by the divisor
used in the generation of the code. Thus, when the received code word is again divided by the same
divisor, an error-free reception should lead to an all ‘0’ remainder. A nonzero remainder is indicative
of the presence of errors.
The probability of error detection depends upon the number of check bits, n, used to construct the
cyclic code. It is 100 % for single-bit and two-bit errors. It is also 100 % when an odd number of bits
are in error and the error bursts have a length less than n + 1. The probability of detection reduces to
1 – (1/2)
n−1 for an error burst length equal to n + 1, and to 1 – (1/2)
n for an error burst length greater
than n + 1.
2.6.4 Hamming Code
We have seen, in the case of the error detection and correction codes described above, how an increase
in the number of redundant bits added to message bits can enhance the capability of the code to detect
and correct errors. If we have a sufficient number of redundant bits, and if these bits can be arranged
such that different error bits produce different error results, then it should be possible not only to detect
the error bit but also to identify its location. In fact, the addition of redundant bits alters the ‘distance’
code parameter, which has come to be known as the Hamming distance. The Hamming distance is
nothing but the number of bit disagreements between two code words. For example, the addition of
single-bit parity results in a code with a Hamming distance of at least 2. The smallest Hamming
distance in the case of a threefold repetition code would be 3. Hamming noticed that an increase
in distance enhanced the code’s ability to detect and correct errors. Hamming’s code was therefore
an attempt at increasing the Hamming distance and at the same time having as high an information
throughput rate as possible.
The algorithm for writing the generalized Hamming code is as follows:
1. The generalized form of code is P 1 P 2 D 1 P 3 D 2 D 3 D 4 P 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 P 5 , where P and D
respectively represent parity and data bits.
2. We can see from the generalized form of the code that all bit positions that are powers of 2 (positions
1, 2, 4, 8, 16, ) are used as parity bits.
3. All other bit positions (positions 3, 5, 6, 7, 9, 10, 11, ) are used to encode data.
4. Each parity bit is allotted a group of bits from the data bits in the code word, and the value of the
parity bit (0 or 1) is used to give it certain parity.
5. Groups are formed by first checking N − 1 bits and then alternately skipping and checking N bits
following the parity bit. Here, N is the position of the parity bit; 1 for P 1 , 2 for P 2 , 4 for P 3 , 8 for P 4
and so on. For example, for the generalized form of code given above, various groups of bits formed
with different parity bits would be P 1 D 1 D 2 D 4 D 5 , P 2 D 1 D 3 D 4 D 6 D 7 , P 3 D 2 D 3 D 4 D 8 D 9 ,
P 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 and so on. To illustrate the formation of groups further, let us examine
the group corresponding to parity bit P 3 . Now, the position of P 3 is at number 4. In order to form
the group, we check the first three bits (N − 1 = 3) and then follow it up by alternately skipping
and checking four bits (N = 4).
The Hamming code is capable of correcting single-bit errors on messages of any length. Although
the Hamming code can detect two-bit errors, it cannot give the error locations. The number of parity
bits required to be transmitted along with the message, however, depends upon the message length, as
shown above. The number of parity bits n required to encode m message bits is the smallest integer
that satisfies the condition (2
n – nn > m.
Digital Electronics
sequence to get the cyclic code. The code word so generated is completely divisible by the divisor
used in the generation of the code. Thus, when the received code word is again divided by the same
divisor, an error-free reception should lead to an all ‘0’ remainder. A nonzero remainder is indicative
of the presence of errors.
The probability of error detection depends upon the number of check bits, n, used to construct the
cyclic code. It is 100 % for single-bit and two-bit errors. It is also 100 % when an odd number of bits
are in error and the error bursts have a length less than n + 1. The probability of detection reduces to
1 – (1/2)
n−1 for an error burst length equal to n + 1, and to 1 – (1/2)
n for an error burst length greater
than n + 1.
2.6.4 Hamming Code
We have seen, in the case of the error detection and correction codes described above, how an increase
in the number of redundant bits added to message bits can enhance the capability of the code to detect
and correct errors. If we have a sufficient number of redundant bits, and if these bits can be arranged
such that different error bits produce different error results, then it should be possible not only to detect
the error bit but also to identify its location. In fact, the addition of redundant bits alters the ‘distance’
code parameter, which has come to be known as the Hamming distance. The Hamming distance is
nothing but the number of bit disagreements between two code words. For example, the addition of
single-bit parity results in a code with a Hamming distance of at least 2. The smallest Hamming
distance in the case of a threefold repetition code would be 3. Hamming noticed that an increase
in distance enhanced the code’s ability to detect and correct errors. Hamming’s code was therefore
an attempt at increasing the Hamming distance and at the same time having as high an information
throughput rate as possible.
The algorithm for writing the generalized Hamming code is as follows:
1. The generalized form of code is P 1 P 2 D 1 P 3 D 2 D 3 D 4 P 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 P 5 , where P and D
respectively represent parity and data bits.
2. We can see from the generalized form of the code that all bit positions that are powers of 2 (positions
1, 2, 4, 8, 16, ) are used as parity bits.
3. All other bit positions (positions 3, 5, 6, 7, 9, 10, 11, ) are used to encode data.
4. Each parity bit is allotted a group of bits from the data bits in the code word, and the value of the
parity bit (0 or 1) is used to give it certain parity.
5. Groups are formed by first checking N − 1 bits and then alternately skipping and checking N bits
following the parity bit. Here, N is the position of the parity bit; 1 for P 1 , 2 for P 2 , 4 for P 3 , 8 for P 4
and so on. For example, for the generalized form of code given above, various groups of bits formed
with different parity bits would be P 1 D 1 D 2 D 4 D 5 , P 2 D 1 D 3 D 4 D 6 D 7 , P 3 D 2 D 3 D 4 D 8 D 9 ,
P 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 and so on. To illustrate the formation of groups further, let us examine
the group corresponding to parity bit P 3 . Now, the position of P 3 is at number 4. In order to form
the group, we check the first three bits (N − 1 = 3) and then follow it up by alternately skipping
and checking four bits (N = 4).
The Hamming code is capable of correcting single-bit errors on messages of any length. Although
the Hamming code can detect two-bit errors, it cannot give the error locations. The number of parity
bits required to be transmitted along with the message, however, depends upon the message length, as
shown above. The number of parity bits n required to encode m message bits is the smallest integer
that satisfies the condition (2
n – nn > m.