Hamming Code logo Hamming Code

Hamming Codes for Error Correction

Implementation of error detection and correction algorithms using Hamming codes.

Project Description

Hamming codes are a family of linear error-correcting codes that allow automatic detection and correction of single-bit errors during data transmission. This project implements both Hamming encoding and decoding.

Main Features

  • Hamming encoding: Generates parity bits to protect data.
  • Error detection: Identifies 1-bit and 2-bit errors.
  • Automatic correction: Corrects single-bit errors automatically.
  • Visualization: Shows the encoding and correction process step by step.

Technologies Used

  • Language: C/C++
  • Algorithms: Hamming (7,4) and Hamming (15,11)
  • Mathematics: Linear algebra over finite fields
  • Testing: Exhaustive test cases with error injection

How It Works

Encoding Process

  1. Data input: The information bits to be transmitted are received.
  2. Parity calculation: Parity bits are generated using XOR operations.
  3. Insertion: Parity bits are inserted at specific positions (powers of two).
  4. Output: The final codeword is produced for transmission.

Correction Process

  1. Reception: The codeword is received, possibly with errors.
  2. Syndrome calculation: The error syndrome is computed using the parity bits.
  3. Localization: The syndrome indicates the error position, if one exists.
  4. Correction: The faulty bit is corrected and the original data is extracted.

Implementation

Code Structure

// Structure to handle Hamming codes
typedef struct {
    int data_bits;      // Number of data bits
    int parity_bits;    // Number of parity bits
    int total_bits;     // Total bits in codeword
    int* parity_matrix; // Parity generation matrix
} HammingCode;

// Main functions
int* hamming_encode(int* data, int data_length);
int* hamming_decode(int* received, int* corrected_data);
int calculate_syndrome(int* received, HammingCode* code);
void correct_error(int* received, int error_position);

Correction Algorithm

The algorithm uses the error syndrome to determine the position of the faulty bit:

  • Syndrome = 0: No errors.
  • Syndrome > 0: The error position matches the syndrome value.
  • Double error: Detected, but not correctable.

Results and Analysis

Correction Capability

  • 1-bit errors: 100% effective detection and correction
  • 2-bit errors: Reliable detection, but not correction
  • 3+ bit errors: May go undetected

Efficiency

  • Code (7,4): 4 data bits + 3 parity bits = 57% efficiency
  • Code (15,11): 11 data bits + 4 parity bits = 73% efficiency
  • Overhead: Decreases logarithmically as the block size grows

Practical Applications

Hamming codes are used in:

  • RAM memory: ECC correction
  • Storage systems: Hard drives and SSDs
  • Communications: Reliable data transmission
  • Embedded systems: Protection against interference

Conclusions

This project highlights both the mathematical elegance of Hamming codes and their practical value in modern digital systems. The ability to automatically detect and correct errors is fundamental to the reliability of computing systems.

Key Learnings

  • Deeper understanding of error-correcting code theory
  • Efficient implementation of correction algorithms
  • Better analysis of the trade-off between redundancy and reliability
  • Practical use of abstract mathematical concepts