Past exam question: 2072 Chaitra, Q9
Open in the Padhaiko appWhat are Hamming codes? Write the properties of Hamming codes. Visualize a 3-bit code words as code vector.
Solution
Definition of Hamming Codes: Hamming codes are a family of linear error-correcting block codes designed by Richard W. Hamming. They add redundant parity bits to datawords such that the code has a minimum Hamming distance of:
This allows the code to:
- Detect up to bit errors.
- Correct any single bit error ().
For any positive integer (where is the number of parity check bits):
- Total codeword length:
- Number of data/information bits:
- Number of parity check bits:
- Example: For , Hamming code.
Key Properties of Hamming Codes:
- Single-Error Correction: Because , every single bit error moves the codeword to a unique vector at Hamming distance 1, which belongs exclusively to the decoding sphere of that valid codeword.
- Systematic Structure: Parity check bits are placed at bit positions that are powers of 2 (). Each parity bit checks a specific subset of bits determined by the binary expansion of the position indices.
- Syndrome Decoding: The syndrome vector directly indicates the binary decimal position of the single inverted bit:
- Efficiency: Hamming codes are perfect codes, meaning they satisfy the Hamming bound with equality:
Visualization of 3-Bit Codewords as Code Vectors: The space of all possible 3-bit binary sequences forms a 3-dimensional vector space containing vertices, which can be visualized as the 8 corners of a unit cube:
(0,1,1)-----------------(1,1,1)
/| /|
/ | / |
/ | / |
(0,0,1)-----------------(1,0,1) |
| | | |
| (0,1,0)----------------|-(1,1,0)
| / | /
| / | /
|/ |/
(0,0,0)-----------------(1,0,0)
- Vector Representation: Each sequence is a vector originating from the origin to the vertex coordinates in Euclidean 3D space.
- Hamming Distance on the Cube: The Hamming distance between two binary vectors corresponds exactly to the minimum number of edges (Manhattan grid distance) traversed along the cube's perimeter to move from vertex to vertex :
- (adjacent vertices connected by 1 edge).
- (face diagonal, distance 2 edges).
- (body diagonal, diametrically opposite across the cube).
- Error Detection/Correction Geometry: If we select codewords that are separated by distance (e.g., diametrically opposite corners like
000and111), any single bit inversion moves the point by 1 edge, ensuring it cannot land on another valid codeword.
Hamming codes are systematic linear single-error-correcting block codes with , length , data bits , and parity bits at power-of-2 positions. The 8 possible 3-bit words form the vertices of a 3D unit cube , where Hamming distance equals the shortest edge path between vertices (e.g., ).