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 which is useful for correcting transmission errors in digital communications.

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 redundant 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. Replacing 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.

Difficult to speak of decoding strictly speaking, but rather of error correction in a received code.

— Calculate extra bits (sometimes called vector).

— Find the position of the error in the code word according to the values of the vector.

— Correct the error: invert the bit at the corresponding position.

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.

The Hamming Correcting Code can detect and correct a limited number of transmission errors. If there are too many errors, the code will not be able to correct them and the transmission will be considered a failure.

dCode retains ownership of the "Hamming Error-Correcting Code" source code. Except explicit open source licence (indicated Creative Commons / free), the "Hamming Error-Correcting Code" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, 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, or API access for "Hamming Error-Correcting Code" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "Hamming Error-Correcting Code" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!

Exporting results as a .csv or .txt file is free by clicking on the *export* icon

Cite as source (bibliography):

*Hamming Error-Correcting Code* on dCode.fr [online website], retrieved on 2024-11-11,

hamming,code,error,correction,detection,communication,bit,parity

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

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

Feedback