What is Hamming Code in C?

A linear error-correcting code called Hamming code can find and fix single-bit data faults. Early in the 1950s, Richard W. Hamming created it. In order to construct a coded word, which is then communicated or stored, the code adds extra bits (known as parity bits) to the original data. The parity bits are used to verify the received coded word for faults during decoding, and if one is found, the code can be corrected.

What are the types of Hamming code?

There are various Hamming code types, and each is intended to find and fix a specific number of data problems. The most typical varieties of Hamming codes include:

Hamming (7,4) Code: This is the most basic variation of Hamming code, in which 3 parity bits are added to convert 4 data bits into a 7-bit code. It is able to recognise and fix single-bit mistakes.
Hamming (15,11) Code: This code uses 4 parity bits to encode 11 data bits into a 15-bit code. Both some two-bit mistakes and single-bit errors can be found and fixed by it.
Hamming (31,26) 26 data bits are encoded using this technique, which creates a 31-bit code with 5 parity bits. It has the ability to recognise and fix some single-bit and two-bit faults.
Single Error Correction, Double Error Detection, or SEC-DED: In situations where error detection is more important than error correction, Hamming code is utilised. Similar to the Hamming (7,4) code, it encodes 4 data bits into a 7-bit code with 3 parity bits, however it can only identify and fix single-bit errors.
Error-Correcting Code (ECC) Hamming Code: This is a broader phrase that refers to a variety of Hamming codes created for particular error-correction needs. It might be referring to enhanced variants with bigger word sizes and more parity bits, such Hamming (15,11) and Hamming (31,26).

The aforementioned constitute some of the most frequently employed Hamming code varieties. Various Hamming code variants or other error-correction codes may be used, depending on the application's requirements for error detection and correction.

Describe the hamming rule?

The Hamming distance, commonly referred to as Hamming's rule, is a notion used in information theory and coding theory to calculate how many bits separate two binary strings from one another. In plain English, it measures the difference between two binary sequences of equal length.

The Hamming distance, written as d(A, B), is defined as the number of points at which the corresponding bits in the two strings differ, given two binary strings A and B, both of length N. It can be modelled mathematically as follows:

If A[i] > B[i], then d (A, B) = (1 for i).

Where:

The ith bit of string A is denoted as A[i].
The ith element of string B is denoted as B[i].
All of the bits between i = 1 and N are included in the summation.

Applications for hamming distance include data compression methods, DNA sequence analysis, and error detection and correction codes. It is a fundamental idea in code theory that is used to formulate error-correcting algorithms consisting of Hamming codes, that have been adept at identifying and fixing oversights based on the Hamming distance, which is the difference between transmitted and received codes. It also aids in determining how similar or dissimilar binary sequences are.

Objectives of Hamming code in c

Error detection and repair in data transmission or storage are the goals of implementing Hamming code in C (or any other computer language). Hamming code is an error-correcting code that augments the original data with redundancy to enable the detection and, in many circumstances, correction of faults made during transmission.

The following are the primary goals of utilising Hamming code in C:

Error detection: It is the main goal of Hamming code, which is used to identify mistakes in transmitted or stored data. The Hamming code turns the raw data into a coded word by adding parity bits. The parity bits will enable identifying the presence of an error if, during transmission or storage, any bit in the received code flips owing to noise or other problems.
Error Correction: Hamming code is made to fix single-bit defects in the received data in addition to error detection. The code can locate the mistake's position by examining the parity bits, and it can flip the incorrect bit to fix the error. The original data can be accurately retrieved in this manner.
Single-Bit Error Correction: Hamming codes are very helpful for rectifying single-bit errors because they can pinpoint and change the precise bit that has been flipped. Throughout many situations whereby confidentiality of information is essential, which includes computer memory, data transfer, and storage systems, this feature is essential.
Efficiency: Hamming code strikes a fair mix between efficiency and error correcting capabilities with regard to of the variety of redundant bits that are added to the original data. Although the technique is relatively straightforward to put into effect, language proficiency is a desirable option in numerous applications in real life.
Wide Application: Hamming algorithm codes provide an extensive variety of usages in an assortment of distinct industries, notably memory for computer infrastructure, protocols for communications, information storage infrastructure, and other types of electronic equipment wherein correction and identification of mistakes are required.

You are able to achieve the aforementioned goals and guarantee data accuracy and integrity in applications where mistakes in data transmission or storage may occur by implementing Hamming code in C.

Example

Take the basic Hamming code as an illustration, Hamming (7,4), which converts 4 data bits into a 7-bit code by adding 3 parity bits. Using C code, we'll show how the encoding and decoding work. In the example, a 4-bit data word will be encoded, a single-bit mistake will be added during transmission, and the received code will be decoded to reveal the original data.

Here is an example of the Hamming (7,4) code in C:

#include <stdio.h>

int calculate_parity(int data, int p) {

    int parity = 0;

    for (int i = 0; i < 4; i++) {

        if (data & (1 << i)) {

            if (p & (1 << i)) {

                parity ^= 1;

            }

        }

    }

    return parity;

}

int hamming_encode(int data) {

    int p1 = calculate_parity(data, 0b001);

    int p2 = calculate_parity(data, 0b010);

    int p4 = calculate_parity(data, 0b100);

    int hamming_code = (data << 3) | (p1 << 2) | (p2 << 1) | p4;

    return hamming_code;

}

int hamming_decode(int received_code) {

    int s1 = calculate_parity(received_code, 0b001);

    int s2 = calculate_parity(received_code, 0b010);

    int s4 = calculate_parity(received_code, 0b100);

    int syndrome = (s4 << 2) | (s2 << 1) | s1;

    if (syndrome != 0) {

        received_code ^= (1 << (7 - syndrome));

    }

    int data = (received_code >> 3) & 0x0F;

    return data;

}

int main() {

    int original_data = 0b1100;

    int encoded_data = hamming_encode(original_data);

    printf("Original Data: %x\n", original_data);

    printf("Hamming Code: %x\n", encoded_data);

    int received_code = encoded_data;

    int error_bit_position = 3;

    received_code ^= (1 << error_bit_position);

    int decoded_data = hamming_decode(received_code);

    printf("Received Code: %x\n", received_code);

    printf("Decoded Data: %x\n", decoded_data);

    return 0;

}

Output

In this illustration, a 7-bit Hamming code 0111001 is created from the original 4-bit data 1100. We flip the fourth bit during transmission, resulting in a single-bit mistake that produces the received code 0111101. The problem is successfully identified and fixed by the decoder, allowing it to restore the original data of 1100.

Odd Parity and Even Parity

To make the total number of 1s (including the parity bit) odd, add a parity bit. When there are an even number of 1s, the single-bit error detection algorithm is used.

Even To make the total number of 1s (including the parity bit) even, parity: adds a parity bit. When the total number of 1s is odd, the single-bit error detection algorithm is used to find faults.

Advantages of Hamming Code in C

The benefits of using Hamming code in C are, in essence:

Hamming code can identify and fix single-bit defects, preserving the integrity of the data.
Simple Coding: Coding in C for the fundamental Hamming (7,4) code is simple.
Efficiency: It balances the need for redundancy with the capacity for error correction.
Provides on-the-fly data rectification without retransmission with real-time error correction.
Utilised in data storage, communication protocols, memory systems, and digital systems.
The encoding and decoding techniques have simple computational structures.
Graceful Degradation: Effective error detection in environments with low error rates.
Enhances data dependability in instances including noisy communication or storage.

Disadvantages of Hamming Code in C

The drawbacks of using Hamming code in C are, in brief, as follows:

Redundancy: By adding extra bits, the data capacity is increased.
Only capable of correcting single-bit errors. Limited error correction.
Increases processing time and memory utilisation, especially for larger data.
Burst error inefficiency: ineffective in finding or fixing successive bit faults.
Complication for Larger Codes: Putting larger Hamming codes into practise might be difficult and computationally demanding.
Even parity may be limited in its ability to detect mistakes with odd numbers.
Decoding Complexity: Complex algorithms may be required for decoding with error correction.
Errors must travel to the receiver in order to be corrected, which is a need for error propagation.
Other error-correcting codes may be better appropriate for certain criteria, making this one less than ideal for some applications.

Conclusion

In C, Hamming code is a useful technique for identifying single-bit inaccuracies data integrity, and error detection and correction. The implementation is rather simple, and the system finds a compromise amongst effectiveness and error-correction capabilities. It is incapable of handling multiple-bit errors or burst faults, though, which are limits. Notwithstanding these shortcomings, hamming programming continues to be often employed and acts as the basis for algorithms that correct errors in an assortment of contexts.

← Prev Next →

C Tutorial