Hamming Code is yet another error detection and correction code. In this code, the parity bits are added to increase the Hamming distance between the valid code words. Here, the parity bits are arranged in a way that different error bits produce different error results. This enables the Hamming Code to both detect and localize the error bit.
Number of Parity bits in Hamming Code
The most popular Hamming code is Hamming (7,4) code. In this code, the length of the code word c = 7, the number of data bits (information bits) d = 4, and the number of parity bits (check bits) p = 3. So, in a Hamming code, if the number of parity bits is ‘p’, then the length of the code word can be a maximum of c = 2p – 1; and the number of data bits can be a maximum of d = 2p – 1 – p.
Therefore, the number of parity bits p required to encode d data bits is the smallest integer that satisfies the condition (2p – p) > d.
Rules of Hamming Code
Since Hamming (7,4) is the most popular one, we will understand the rules of Hamming code keeping Hamming (7,4) code in mind.
1. The Hamming code is represented in the following form:
Representation of Hamming Code
Here, P represents parity bits, and D represents data bits.
2. All the bit positions that are the power of 2 (e.g. 20, 21, 22, 23, …) are occupied by the parity bits.
3. Remaining bit positions (e.g. 3, 5, 6, 7, …) are used for data bits.
|
According to points 1 to 3, for Hamming (7,4) code, the representation will be: P1P2D1P3D2D3D4 |
4. Each parity bit is assigned a group of data bits that decide the value of the parity bit according to the type of parity used.
5. To form the group for a parity bit, the corresponding parity bit and the bits following the parity bit in the code word are considered. The group is formed by adding the first N-1 bits and then alternately skipping and adding N bits following the parity bit. N is the position of the parity bit (e.g. 1 for P1, 2 for P2, 4 for P3 and so on).
|
According to points 4 and 5, for Hamming (7,4) code, the groups for the parity bits are as follows: P1: D1D2D4 ; P2: D1D3D4 ; P3: D2D3D4 Let’s clarify the process by considering P2 For constructing the group for P2 we will take the bits after P2 : D1P3D2D3D4 Here, N = 2 First taking N-1 bits, that means taking 2-1 = 1 bit, which is taking D1 Then skipping N bits; means skipping 2 bits, which is skipping P3D2 Then taking N bits; means taking 2 bits, which is taking D3D4 Thus, the group of bits to decide the value of P2 is D1D3D4 |
Generation of Hamming code
Now, we will compute the even parity bits for an example, 4-bit data bits “1001” and the complete Hamming (7,4) code word.
| P1 | P2 | D1 | P3 | D2 | D3 | D4 | |
| Only data bits | 1 | 0 | 0 | 1 | |||
| Data bits and P1 | 0 | 1 | 0 | 0 | 1 | ||
| Data bits and P2 | 0 | 1 | 0 | 0 | 1 | ||
| Data bits and P3 | 1 | 1 | 0 | 0 | 1 | ||
| Code word | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
An Example Case of Error Detection and Correction
Here, we will consider the above code word: P1P2D1P3D2D3D4 = 0011001
Let’s say during the transmission, D3 got corrupted and flipped from 0 to 1.
So, the received code is: P1P2D1P3D2D3D4 = 0011011
The following steps are followed to detect and localize the fault so that it can be corrected.
1. Perform the parity check by computing X = P1D1D2D4 ; Y = P2D1D3D4 ; Z = P3D2D3D4 on the received bits
|
X (0101) = 0 ; Y (0111) = 1 ; Z (1011) = 1 |
2. If X, Y, and Z values are ‘0’, then there is no error. If at least any one or more of X, Y, and Z is/are ‘1’, then there is an error.
3. If there is any error, then ZYX value gives the position of the erroneous bit.
|
ZXY = 110. This implies that the 6th bit from the MSB, that is, D3 is the erroneous bit. So, D3 will be flipped to get the correct value. |
Reference: Maini, Anil K. Digital electronics: principles, devices and applications. John Wiley & Sons.
Previous Table of Content Next