Tool for detecting and correcting errors in binary message transmissions via Hamming corrective codes.
Hamming Error-Correcting Code - dCode
Tag(s) : Informatics
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
Hamming codes are a series of codes / algorithms used to automatically correct binary messages if a corrupted / erroneous bit (0 or 1) is transmitted. The correction is done through minimal data redundancy.
The algorithm proposed by Richard Hamming takes a binary message (composed of bits 0 and 1) accompanied by a few additional bits encoding information on the number and position of 1 bits in the message.
Example: The Hamming code 7,4 proposes to transmit 4 bits of data, via a 7-bit message, therefore comprising 3 redundant bits. Hamming code 255,247 only uses 8 redondant bits (3% size increase)
The extra bits encode the parity of a series of bits of the original message. Parity is the process of calculating whether the number of bits at 1 is even or odd.
The series of bits of the original message are selected so as to crisscross the entire message.
The first additional bit counts the parity of the bits in positions 1,3,5,7,9,11,13,... it is stored in position 1
The second additional bit counts the parity of the bits in positions 2,3,6,7,10,11,14,15,... it is stored in position 2
The third additional bit counts the parity of the bits in positions 4,5,6,7,12,13,14,15... it is stored in position 4
By crossing the information of these bits, it is possible to find the position of the error.
Example: In a 7.4 Hamming code, the second bit detects an error: it indicates that the message should have an even parity of the bits in positions 2,3,6,7 but this is not the case. The other bits do not indicate an error, so there is no problem with the bits in position 1,3,5,7 and 4,5,6,7 so the error is in position 2. Replace the value of bit 2 (putting a 1 instead of a 0 or vice versa) corrects the error.
The Hamming code only makes it possible to detect a single alteration in the message, a single change of 1 or 0.
Example: The message 1100 (original) is coded as 0111100, the original message being coded on bits ..1.100, the first bit remains to be calculated (in position 1) which indicates the number of 1 (modulo 2) among positions 3,5,7 or 0 (because 2 = 0 modulo 2), then the second bit (in position 2) indicating the number of 1 (modulo 2) among positions 3,6, 7 is 1 and the third bit (position 4) indicating the number of 1 (modulo 2) among the positions 5,6,7 or 1. The message encoded by Hamming 7.4 is therefore 0111100.
In computer science, it is practical to use series of 8 bits (2 ^ 3), but Hamming codes are practical for messages encoded on 2 ^ n-1 bits. Adding an extra bit improves data redundancy at low cost of memory space.
The last bit added records the parity of the entire message, it is usually stored in position 1.
The message is binary, usually encoded with blocks of 2^n-1 or 2^n bits.
Any notion of error, alteration, erroneous information, etc. is a clue.