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.

dCode retains ownership of the online "Hamming Error-Correcting Code" source code. Except explicit open source licence (indicated CC / Creative Commons / free), the "Hamming Error-Correcting Code" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or the "Hamming Error-Correcting Code" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, copy-paste, or API access for "Hamming Error-Correcting Code" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

hamming,code,error,correction

Source : https://www.dcode.fr/hamming-error-correction

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲
Thanks to your feedback and relevant comments, dCode has developed the best 'Hamming Error-Correcting Code' tool, so feel free to write! Thank you!