- Hamming Code Definition: Hamming code is an error-correcting code that helps detect and correct single-bit errors in data transmission.
- Hamming Distance: The Hamming distance measures the bit differences between code words, indicating the error detection and correction power.
- Redundant Bits: Adding more redundant bits improves the code’s ability to detect and correct errors.
- Parity Bit Positions: Parity bits are placed at positions that are powers of 2, such as 1, 2, 4, and 8.
- Group Formation for Parity Bits: Parity bits check specific groups of data bits, alternating between checking and skipping bits based on their positions.
What is Hamming Code?
Hamming code is a binary member of the error detection and correction codes that adds parity bits at power-of-two positions so a single flipped bit produces a unique syndrome. That syndrome names the error position and therefore locates the bit that must be inverted.
Those extra bits also set the code’s Hamming distance. Hamming distance is the number of bit positions that differ between two code words.
For example, adding a single overall parity bit to otherwise unconstrained data gives a code with a Hamming distance of at least two. In a threefold repetition code, the smallest Hamming distance is three. A larger minimum distance raises the number of errors the code can detect or correct.
Therefore Hamming’s code raises the Hamming distance to 3 while keeping the number of parity bits small relative to the data bits.
The algorithm for writing the generalized Hamming code is as follows:
- The generalized form of code is P1P2D1P3D2D3D4P4D5D6D7D8D9D10D11P5, where P and D respectively represent parity and data bits.
- We can see from the generalized form of the code that all bit positions that are powers of 2 (positions 1, 2, 4, 8, 16) are used as parity bits.
- All other bit positions (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15) are used to encode data.
- Each parity bit is set to 0 or 1 so that its assigned group of bits has the chosen even or odd parity.
- Groups are formed by starting at the parity bit and then alternately checking N bits and skipping N bits. Here, N is the position of the parity bit; 1 for P1, 2 for P2, 4 for P3, 8 for P4 and so on. For the generalized form above, the groups are P1D1D2D4D5D7D9D11, P2D1D3D4D6D7D10D11, P3D2D3D4D8D9D10D11 and P4D5D6D7D8D9 D10D11. P3 sits at position 4, so its group starts at position 4, takes the next four bits, skips four bits and takes the next four bits.
Hamming codes can correct single-bit errors in messages of any length. A second flipped bit produces a nonzero syndrome that points to the wrong position, so the original distance-3 code cannot also name a double error. Extended Hamming adds one overall parity bit when simultaneous double-error detection is required.
The number of parity bits required to be transmitted along with the message, however, depends upon the message length, as shown above. The number of parity bits n required to encode m message bits is the smallest integer that satisfies the condition (2n – n) > m.
