Hamming code implementation in C++
In this article, we will discuss the hamming code implementation in C++ with its example, advantages, and disadvantages.
A type of error-correcting code called a Hamming code is used in digital communication and data storage systems to find and fix faults that could happen while data is being sent or stored. It bears Richard W. Hamming's name and was created by him in the 1950s.
A Hamming code's primary function is to add extra bits to the original data to identify and fix transmission or storage faults. It inserts parity bits into the data stream at specific places. These parity bits enable error rectification by assisting in locating where it occurred.
The (7, 4) Hamming code converts 4 bits of data into a 7-bit code by adding three parity bits, the most popular and extensively used type of Hamming code. Following that, the 7-bit code is delivered or stored. The Hamming code is used to check for errors and, if necessary, fix them when the data is received or retrieved.
As follows is how the Hamming code (7, 4) operates:
- The four bits of data that must be transferred are denoted by the letters D1, D2, D3, and D4.
- A 7-bit code adds three parity bits, P1, P2, and P4, to the data stream at specific points. These positions are P1 at position 1, P2 at position 2, D1 at position 3, P4 at 3. position 4, D2 at position 5, D3 at position 6, and D4 at position 7.
- The receiver calculates 3 syndrome bits, S1, S2, and S4, using the seven-bit code received.
- The receiver can identify errors and, if necessary, fix them based on the values of the syndrome bits.
Generation with an example:
A linear block called hamming code has parity bits interspersed between the data bits.
- When n=0,1,2,3, the parity bits are inserted at each point every 2n bits.
- For n=0, the initial bit position (20 = 1), or the P0 parity bit, will be used.
- For n=1, the P1 parity bit will be put at position 2, or 21 = 2.
- For n=2, the P2 parity bit will be put at position 4 or 22, etc.
- The following equation states how many parity bits (r) must be inserted for a given number of data bits (m).
- 2r m+r+1, where m denotes the number of data bits and r denotes the number of parity bits.
- Find r that satisfies the previous equation for the bit word 1011 with m=4.
- For r=1, 21 4+1+1, which is false, is also false for r=2.
- Since r=3, 23 4 + 3 + 1 à 8 8 is true.
Therefore, to create a hamming code, bit word 1011 needs to add three parity bits.
![Hamming code implementation in C++](https://static.tutorialandexample.com/cpp/hamming-code-implementation-in-cpp1.png)
- The first, second, and fourth positions will contain the three parity bits P0, P1, and P2.
- Below is a picture of bit word 1011's hamming code format.
- Let's get the parity bits now. You can think of even parity or odd parity for this.
- Even parity requires that the word's total number of 1s, including the parity bit, be even, i.e., 2, 4, 6.
- Odd parity requires that the word's total number of 1s, including the parity bit, be odd, i.e., 1,3,5.
- Consider the bit word 1011's even parity for the hamming code.
The bits that must be checked to set the parity bits in Hamming code are shown in the following table.
![Hamming code implementation in C++](https://static.tutorialandexample.com/cpp/hamming-code-implementation-in-cpp2.png)
- Consider the bits for P0 at positions 1, 3, and 5 or P0, 1, 1.
- Put P0 = 1, so that the bits sequence becomes 1 1 1 1, which has even parity, as the bits sequence P0, 1, 1, should now have even parity.
- Consider bits at positions 2, 3, and 6, or P1, 1, and 1, for P1.
- P1 will therefore be 0, making the sequence P1 1 0 1 even parity.
- Similarly, we arrive at P2 = 0.
- Consequently, the complete code for word 1011 is displayed below.
![Hamming code implementation in C++](https://static.tutorialandexample.com/cpp/hamming-code-implementation-in-cpp3.png)
Now, the target receiver receives this hamming code via a communication link.
Example:
Let us see an example to understand the hamming code implementation in C++:
#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;
int check_parity(int n,int i,int code[])
{
int p=0,k;
for(int j=i;j<=n;j=k+i)
{
for(k=j;k<j+i && k<=n;k++) //for i=1 ->bits=1,3,5,7,9,11 for i=2 ->bits 2,3,6,7,10,11
{ //i is the parity bit position
if(code[k]==1)
p++;
}
}
if(p%2==0)
return 0; //if no. of 1 is even return 0
else
return 1; //if no. of 1 is odd, return 1
}
int main()
{
int data[50], num;
cout<<"Enter the size of data";
cin>>num;
cout<<"Enter the data:";
for(int i=num;i>0;i--)
cin>>data[i];
hamming_code(data, num);
return 0;
}
void hamming_code(int data[], int num)
{
int r=0,m=0,n,j=1,c,code[50];
while((r+num+1)>(pow(2,r))) //calculating no. of parity/redundant bits
r++;
n=num+r; //adding no. of redundant bits to array size
for(int i=1;i<=n;i++)
{
if(i==pow(2,m) && m<=r)
{
code[i]=0; //initializing all the bit positions of power 2 to zero
m++;
}
else
{
code[i]=data[j]; //assgning data to remaining positions
j++;
}
}
m=0;
for(int i=1;i<=n;i++)
{
if(i==pow(2,m) && m<=r)
{
c=check_parity(n,i,code); //assigning parity bit to position of power 2
code[i]=c;
m++;
}
}
cout<<"The hamming code for given data is:";
for(int i=n;i>0;i--)
cout<<code[i];
cout<<"\nEnter the received code:";
for(int i=n;i>0;i--)
cin>>code[i];
m=j=c=0;
for(int i=1;i<=n;i++)
{
if(i==pow(2,m) && m<=r)
{
c=c+(pow(2,j)*check_parity(n,i,code)); // decimal value of error code
j++;
m++;
}
}
if(c==0)
cout<<"\nReceived word is correct.";
else
{
cout<<"\nThere is error in bit "<<(n-c)+1<<"\nThe corrected code is:";
if(code[c]==1)
code[c]=0;
else
code[c]=1;
for(int i=n;i>0;i--)
cout<<code[i];
}
}
Output:
![Hamming code implementation in C++](https://static.tutorialandexample.com/cpp/hamming-code-implementation-in-cpp4.png)
Advantages of Hamming code in C++:
Hamming code has several advantages. Some main advantages of hamming code are as follows:
Error detection and correction: Hamming code can detect and fix single-bit errors, essential in settings where data integrity is necessary, such as telecommunications, computer memory systems, and storage devices. It guarantees that the data is dependable and correct.
Low computational complexity: Hamming code has a low computational overhead since it uses straightforward XOR operations and bit manipulation. It is crucial when effectiveness is critical in situations or applications with limited resources.
Implementation simplicity: The (7, 4) Hamming code, one of the most popular variants, is a basic form of Hamming code that can be implemented in C++ with reasonable ease. Developers with moderate programming experience can use it because it uses fundamental bitwise operations.
Real-time error correction: Hamming code is appropriate for real-time processing applications like audio and video streaming because it can instantly fix single-bit errors.
Widespread application: Hamming code has been applied extensively in various fields for many years, making it a well-known and dependable error-correcting method.
Efficiency: Hamming code strikes a nice mix between redundancy and error repair ability. It works well for error repair since the overhead it adds to the original data is minimal.
Versatility: Hamming code is adaptable to different data amounts and configurations, making it useful in various situations. Depending on the unique requirements of your application, you can use a variety of code parameters.
Note:
It's necessary to remember that while Hamming code is effective at fixing single-bit errors, it is ineffective at fixing multiple or burst faults. More sophisticated codes like Reed-Solomon or Turbo may be required for more effective error correction. However, they are often more complex.
Disadvantages of Hamming code in C++:
Hamming code has some drawbacks, in addition to helpful error correction features.
Encoding and decoding time: Time spent encoding and decoding data with Hamming code can be time-consuming, especially when working with big data blocks or intricate code variants. Real-time applications may be concerned about this increased processing time.
Redundancy: Hamming code increases the total data size by adding extra bits (parity bits) to the original data. This overhead can increase significantly for more extensive data amounts, decreasing the overall data transport or storage effectiveness.
Interoperability: The sender and receiver must utilize the same code parameters to repair errors while using Hamming code. It is challenging to guarantee error correction compatibility when systems with various parameters must communicate.
Inefficiency for large data blocks: As the size of the data block rises, the Hamming code's efficiency falls. More extended data blocks demand more parity bits, which results in a worsened overhead-to-correction-capability ratio.
Non-adaptive error correction: Hamming code operates with set code parameters, so it cannot adjust to changing error rates or patterns. It is known as non-adaptive error correction. Error rates may vary in real-world circumstances, and different error-correction methods might be better suited to handle these fluctuations efficiently.
Limited error correction: Depending on the code parameters, Hamming code can only identify and fix a limited amount of faults. For instance, the (7, 4) Hamming code can detect and repair single-bit errors but not multiple-bit ones or those that exceed a specific threshold. This restriction might need to be revised for applications with higher error rates or more demanding requirements for error correction.
The complexity of higher-level codes: While the primary (7, 4) Hamming code is reasonably easy to use, more advanced Hamming codes with better error-correcting capabilities can be challenging to develop and implement since they need a lot of calculation.
Not suitable for burst errors: Hamming code is not appropriate for burst errors, which are several errors that happen quickly after one another. In some transmission or storage channels, burst faults are frequent, and Hamming code needs to be better adapted to handle them adequately.
Encoding and decoding time: Time spent encoding and decoding data with Hamming code can be time-consuming, especially when working with big data blocks or intricate code variants. Real-time applications may be concerned about this increased processing time.
Despite these drawbacks, Hamming code is a helpful error correction method, especially in applications where its limits are not a significant issue and the ease of implementation is advantageous. However, other error correction codes like Reed-Solomon or Turbo codes may be better appropriate for requirements for error correction that are more demanding or in situations with various error patterns.