Hamming code: Difference between revisions

Revision as of 18:42, 23 September 2021

Revision as of 09:10, 12 October 2021

Line 57:

Hamming studied the existing coding schemes, including two-of-five, and generalized their concepts. To start with, he developed a [[wikt:nomenclature|nomenclature]] to describe the system, including the number of data bits and error-correction bits in a block. For instance, parity includes a single bit for any data word, so assuming [[ASCII]] words with seven bits, Hamming described this as an ''(8,7)'' code, with eight bits in total, of which seven are data. The repetition example would be ''(3,1)'', following the same logic. The [[code rate]] is the second number divided by the first, for our repetition example, 1/3.

Hamming also noticed the problems with flipping two or more bits, and described this as the "distance" (it is now called the ''[[Hamming distance]]'', after him). Parity has a distance of 2, so one bit flip can be detected, but not corrected, and any two bit flips will be invisible. The (3,1) repetition has a distance of 3, as three bits need to be flipped in the same triple to obtain another code word with no visible errors. It can correct one-bit errors or it can detect - but not correct - two-bit errors. A (4,1) repetition (each bit is repeated four times) has a distance of 4, so flipping three bits can be detected, but not corrected. When three bits flip in the same group there can be situations where attempting to correct will produce the wrong code word. In general, a code with distance ''k'' can detect but not correct {{nowrap|''k'' − 1}} errors.

Hamming was interested in two problems at once: increasing the distance as much as possible, while at the same time increasing the code rate as much as possible. During the 1940s he developed several encoding schemes that were dramatic improvements on existing codes. The key to all of his systems was to have the parity bits overlap, such that they managed to check each other as well as the data.