Maintaining the authenticity of data is the most important criterion for any transmitting or receiving system. Hamming code plays a vital role in maintaining authenticity. Formulated as a set of error correction codes, the Hamming codes are used to detect the error while transmitting the data between the sending and receiving ends. . While transmitting the data often the errors are caused between sending and receiving end, which causes loss in data and transparency.
There are many reasons for the occurrence of transmitting errors, such as noise, distortion of the signal, crosstalk, etc. Developed by R W Hamming, this code generates errors based upon the discrepancy between transmitted and received data. Also known as error-correcting codes, these have found extensive applications in telecommunication networks and processing units.
What is Hamming Code?
Hamming codes are error-detecting codes that are designed to correct a single-bit error in digital data transmission. Hamming codes are more popular due to their ability to detect errors up to a single bit. The error correction is done based on the generation of a number of parity bits. The parity bits are generated based on the data transmitted between receiver and sender. For every data, we need to add parity bits in order to generate the Hamming code. All the code is represented in binary form.
Parity Bits
For generating Hamming code, we need to add parity codes to the data. For obtaining the parity bits, the following relations must hold true.
In the above expression, p is the number of parity bits to be generated, m is the number of bits or number of message bits. For example, let us say we want to determine the number of parity bits for 4-bit data. So the m value is 4. The above equation becomes
For a value of p=3, the above equation is satisfied. This means that, for 4-bit data, the number of parity bits required is 3. These parity bits are added for security purposes to the data. After adding the parity bits, the total size of data transmission now becomes 7 bits. Four bits as message bits and three bits as parity bits.
Placement of Parity Bits
Placement of parity bits is important since the receiver must know out of the seven bits received which are parity bits and which are message bits. Else, it would again cause an error while interpreting the data. So a protocol is followed for placing the parity bits which is explained as follows. Now, we have a total of seven bits, out of which four bits are message bits and three bits are parity bits. In the seven-bit data, the parity bits are added in the place of powers of two. Consider the following table.
Placement of Parity Bits
In the table above, P1, P2, and P3 are parity bits. M1, M2, M3, and M4 are message bits. As mentioned, the location of parity bits is the powers of two, i.e. two to the power zero, one, and two. Hence parity bit location is 1, 2, and 4. The rest of locations 3,5,6 and 7 are allotted to the four message bits. The overall bits are seven. The value of parity bits is evaluated based on the message which is transmitted. This code is also known as (7,4) code out of which total bits are seven, consisting of 4 message bits and 3 parity bits.
Hamming Code Equation
For developing the complete hamming code, we need to first determine the parity bit values. For determining the parity bit, again we have two types, the first one is called Hamming code with even parity and then Hamming code with odd parity. Let’s see the Hamming code with even parity first.
Hamming Code with Even Parity
Let us determine Hamming code for the message to be transmitted 1110. Once we get the message to be transmitted, we can fix the places for M1, M2, M3, and M4, as shown below.
Even Bit Parity
To determine the value of P1, since we are following even parity, we need to check for an even number of ones in (P1, M1, M2, M3, M4). To determine the exact sequence of bits to be checked along with the parity, the following rule is followed.
Rules to Determine the Parity Sequence
- Rule 1. The value of the parity bit is determined by the sequence of bits that is alternatively checked and skipped. For P1, check one, skip one. So The pattern becomes, start with location one, skip 2, check 3, skip 4, check 5 skips 6 and check 7. So it becomes (P1,3,5,7)
- Rule 2. To determine the value of parity bit P2, the rule is to check two bits and skip two bits. So, since the parity bit, P2 starts from location two, check locations 2 and 3, and then skip locations 4 and 5. Then check 6 and 7, and skip 8 and 9 (if available). The resultant sequence now becomes (P2,3,6,7).
- Rule 3. To determine the value of parity bit P3, the rule is to check four bits, skip four bits. Starting from P3 location, check location 4,5,6,7 and skip location 8,9,10,11 (if available). The resultant sequence now becomes, (P3,5,6,7).
Parity Generation with Even Parity
Now we will see how to determine the values of P1, P2, P3.
- To determine the value of P1, we have seen the sequence as (P1,3,5,7). From the location table, we know the values of locations 3,5, and 7 which we got from the message to be transmitted. So now the sequence becomes (P1,1,1,0). As the value of location 3 is 1, location 5 is 1, and location 7 is 0, it can be seen in table 2 also. In the sequence (P1,110) we have two ones and one zero. So a number of one is the sequence is two, which is an even number. So, if we are following parity generation with even parity, the number of ones should be even. For this to satisfy, the value of P1 should be 0.
- To determine the value of P2, first, let us see what is the sequence. The sequence is (P2,3,6,7). From the table, we can find the sequence as (P2,1,1,0). So a number of ones are two. Which is an even number. So to satisfy even parity, the value of P2 must be zero.
- To determine the value of P3, first, let see what is the sequence as explained in the previous section. The sequence is (P3,5,6,7). From the table, put the digits from the location number we get, (P3, 1,1,0). So the number of one’s is two. Which is an even number. So to satisfy even parity, the value of P3 must be zero.
- Finally, after obtaining the values of P1, P2, and P3, the complete hamming code along with the data message is given as
Hamming Code
The code shown above is transmitted through the receiver.
Parity Generation with Odd parity
Now we will see how to determine the values of P1, P2, P3 for odd parity generation
- To determine the value of P1, we have seen the sequence as (P1,3,5,7). From the location table, we know the values of locations 3,5, and 7 which we got from the message to be transmitted. So now the sequence becomes (P1,1,1,0). As the value of location 3 is 1, location 5 is 1, and location 7 is 0, it can be seen in table 2 also. In the sequence (P1,110) we have two ones and one zero. So a number of one is the sequence is two, which is an even number. So, if we are following parity generation with odd parity, the number of ones should be odd. For this to satisfy, the value of P1 should be 1.
- To determine the value of P2 the sequence is (P2,3,6,7). From the table, we can find the sequence as (P2,1,1,0). So a number of one’s is two. Which is an even number. So to satisfy odd parity, the value of P2 must be one.
- To determine the value of P3, first, let see what is the sequence as explained in the previous section. The sequence is (P3,5,6,7). From the table, putting the digits from the location number we get, (P3, 1,1,0). So a number of one’s is two. Which is an even number. So to satisfy odd parity, the value of P3 must be one.
- After obtaining the values of P1, P2, and P3, the complete hamming code along with the data message is given as
Hamming Code Odd Parity
The sequence for parity can be also found like this. Consider the following table.
Hamming Code Sequence
From the table, it can be observed how to get the sequence for P1, P2, and P3. For P1, the location of 1 should be at the LSB, or at the first position. From the digital equivalent we can see that, for the binary equivalent of the numbers 1,3,5, and 7 the position of one is at the first position(from the right-sided). Now for P2, the sequence is (2,36,7) i.e. the location of one should be in the middle. From the digital equivalent of the numbers (2,3,6,7) we see that the position of one is in the middle. Similarly, for P3 the sequence is (4,5,6,7), for whose the position of one is at MSB. Hence is the sequence.
Hamming Code Error Detection and Correction
Hamming code for error detection is again of two types, with even parity, and with odd parity. Let’s start with even parity.
Hamming Code Detection with Even Parity
Let us assume that the code transmitted in (7,4) format is 1110000. So we need to decode the same first.
Consider the following table.
Hamming Code Error Detection
As we have obtained the sequence for parity bits P1, P2, and P3, the same can be obtained for E1, E2, and E3. To detect the error with even parity, consider the following table
Hamming Code Error Detection Bits
First, from the location of bits, we can identify the bits. For example, for E1 the sequence is (1,3,5,7). From the hamming code location, we can see its value is (1100). Now in even parity mode, already we have an even number of one’s. So the value of E1=0 to maintain even parity mode. Similarly, we can see that, the value of E2=0, and E3=0. So the resultant error is now (000), which means that no error has been found in transmitting the data. Now let’s analyze the same in odd parity mode.
Hamming Code Detection with Odd Parity.
In odd parity mode, we will check for an odd number of one’s. Consider the following table
Hamming Code Error Detection Odd Parity
Again following the same, we can see that, to maintain odd parity for E1(1,3,5,7) the value of E1=1. Similarly, to maintain odd parity, (E2=1 and E3=1). Hence the error code now becomes (111).
Hamming Code Decoder
Hamming code decoder involves the steps to detect and correct the error of the coded bits. The algorithm for hamming code detection can be given as
- As we did in the generation of parity bit, first identity number of based on the relation which is mentioned below
- The location of parity bit as same i.e. they are placed at the location of powers of two.
- Then based on even or odd parity bit, evaluate the parity check.
For example, as we saw in Hamming code with odd parity, we have seen that the value of (E2E2E1) is (111). The decimal equivalent of 111 is seven. This means the data in the seventh location is wrongly sent. So the data sent was (1110000), and the seventh location is 0. This means that the actual data to be sent was (1110001). This is how we decode the hamming code up to single-bit data correction. It could be noted that for the same data which was sent in even parity the error was zero, but in odd parity, the error is one. Hence the parity setting is quite important in hamming code detection.
Advantages and Disadvantages of Hamming Code
The advantages of hamming code include the following.
- It can detect errors up to a single bit.
- Very effective
- Data streaming can be obtained
The disadvantages of hamming code include the following.
- Large bandwidth is required for transmitting data.
- It also can reduce the bit rate of the transmitter.
1). Where are Hamming code’s used?
Hamming codes are used in the field of data transmission, digitally and checking for errors in between the transmitter and receiver. It has also found applications in telecommunication and computer networks
2). What is the purpose of hamming code?
The purpose of hamming code is to find errors in the data transmitted in binary form.
3). Can Hamming code detect 3-bit errors?
The extended hamming code can detect 3-bit errors.
4). Is Hamming code a CRC?
Ans. No, the fundamental difference between Hamming code and CRC(Cyclic Redundancy Check) is, in CRC, the redundant bits are derived from binary division to data unit, but in Hamming code, they are the function of length of data bits. Also Hamming Codes are used for data which are fixed in size. Whereas, CRC code, which is also a convolutional code, can be used for data of any size. For generating CRC code, we use XOR logical operation among the bits. The check value is the redundancy and the algorithm is based on cyclic code.
Hence, we have seen the working and error detection and generation principles, using Hamming code, which has found extensive applications in computer networks and the telecommunication industry.