Hamming Code

What

An error correction system that can detect and correct errors when data is stored or transmitted.
Hamming code uses a block parity mechanism, dividing the data into blocks and adding parity to each block.

How

A Hamming code word is generated by multiplying the data bits by a generator matrix G using modulo-2 arithmetic. This multiplication’s result is called the code word vector (c1,c2.c3,…cn), consisting of the original data bits and the calculated parity bits.
The generator matrix G used in constructing Hamming codes consists of $I$ (the identity matrix) and a parity generation matrix $A$:
$G=[I:A]$

The multiplication of a 4-bit vector (d1,d2,d3,d4) by G results in a 7-bit code word vector of the form (d1,d2,d3,d4,p1,p2,p3).
It is clear that the A partition of G is responsible for the generation of the actual parity bits. Each column in A represents one parity calculation computed on a subset of d. The Hamming rule requires that p=3 for a (7,4) code, therefore A must contain three columns to produce three parity bits.

$H=[A^T:I]=G^T$

Why

$2^p\ge d+p+1$

• $p$: number of parity bits
• $d$: number of data bits
• $d+p$: size of code word
• 3b1b video

Links

• ECC Memory
• Forward Error Correction