Editing Hamming code (section)

== History ==
[[Richard Hamming]], the inventor of Hamming codes, worked at [[Bell Labs]] in the late 1940s on the Bell [[Model V]] computer, an [[electromechanical]] relay-based machine with cycle times in seconds. Input was fed in on [[punched paper tape]], seven-eighths of an inch wide, which had up to six holes per row. During weekdays, when errors in the relays were detected, the machine would stop and flash lights so that the operators could correct the problem. During after-hours periods and on weekends, when there were no operators, the machine simply moved on to the next job.

Hamming worked on weekends, and grew increasingly frustrated with having to restart his programs from scratch due to detected errors. In a taped interview, Hamming said, "And so I said, 'Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?'".<ref>{{citation|last=Thompson|first=Thomas M.|title=From Error-Correcting Codes through Sphere Packings to Simple Groups|url=https://books.google.com/books?id=ggqxuG31B3cC&q=%22From%20Error-Correcting%20Codes%20through%20Sphere%20Packings%20to%20Simple%20Groups%22&pg=PA16|pages=16–17|year=1983|series=The Carus Mathematical Monographs (#21)|publisher=Mathematical Association of America|isbn=0-88385-023-0}}</ref> Over the next few years, he worked on the problem of error-correction, developing an increasingly powerful array of algorithms. In 1950, he published what is now known as Hamming code, which remains in use today in applications such as [[ECC memory]].

=== Codes predating Hamming ===
A number of simple error-detecting codes were used before Hamming codes, but none were as effective as Hamming codes in the same overhead of space.

==== Parity ====
{{main|Parity bit}}

Parity adds a single [[bit]] that indicates whether the number of ones (bit-positions with values of one) in the preceding data was [[even number|even]] or [[odd number|odd]]. If an odd number of bits is changed in transmission, the message will change parity and the error can be detected at this point; however, the bit that changed may have been the parity bit itself. The most common convention is that a parity value of one indicates that there is an odd number of ones in the data, and a parity value of zero indicates that there is an even number of ones. If the number of bits changed is even, the check bit will be valid and the error will not be detected.

Moreover, parity does not indicate which bit contained the error, even when it can detect it. The data must be discarded entirely and re-transmitted from scratch. On a noisy transmission medium, a successful transmission could take a long time or may never occur. However, while the quality of parity checking is poor, since it uses only a single bit, this method results in the least overhead.

====Two-out-of-five code====
{{main|Two-out-of-five code}}

A two-out-of-five code is an encoding scheme which uses five bits consisting of exactly three 0s and two 1s. This provides <math>\binom{5}{3}=10</math> possible combinations, enough to represent the digits 0–9. This scheme can detect all single bit-errors, all odd numbered bit-errors and some even numbered bit-errors (for example the flipping of both 1-bits). However it still cannot correct any of these errors.

====Repetition====
{{main|Triple modular redundancy}}

Another code in use at the time repeated every data bit multiple times in order to ensure that it was sent correctly. For instance, if the data bit to be sent is a 1, an {{nowrap|1=''n'' = 3}} ''[[repetition code]]'' will send 111. If the three bits received are not identical, an error occurred during transmission. If the channel is clean enough, most of the time only one bit will change in each triple. Therefore, 001, 010, and 100 each correspond to a 0 bit, while 110, 101, and 011 correspond to a 1 bit, with the greater quantity of digits that are the same ('0' or a '1') indicating what the data bit should be. A code with this ability to reconstruct the original message in the presence of errors is known as an ''error-correcting'' code. This triple repetition code is a Hamming code with {{nowrap|1=''m'' = 2,}} since there are two parity bits, and {{nowrap|1=2<sup>2</sup> − 2 − 1 = 1}} data bit.

Such codes cannot correctly repair all errors, however. In our example, if the channel flips two bits and the receiver gets 001, the system will detect the error, but conclude that the original bit is 0, which is incorrect. If we increase the size of the bit string to four, we can detect all two-bit errors but cannot correct them (the quantity of parity bits is even); at five bits, we can both detect and correct all two-bit errors, but not all three-bit errors.

Moreover, increasing the size of the parity bit string is inefficient, reducing throughput by three times in our original case, and the efficiency drops drastically as we increase the number of times each bit is duplicated in order to detect and correct more errors.