# Hamming Codes: Detecting and Correcting Errors

Frances M. Gasman (fgasman@dimacs.rutgers.edu)

• A little history
• How the code works
• Encoding and decoding
• Activities

Building a (7,4) Hamming Code

• Start with a 4 bit string
• Attach 3 check digits
• Encode the message
• Solve encoding problems

Decoding 7 digit messages

• Errors in transmission
• Hamming Distances
• Decoding using error correction
• "Hamming Town"
• Activities involving decoding

Hamming Codes-Construction

Begin with a 4 bit string. Recall that a bit is a digit which is either zero or one.

Call the string ala2a3a4.

Three check digits, cl, c2, and c3, will be attached to the 4 bit string to produce a 7 bit string.

cl, c2, and c3 are chosen as follows:
 C1 = 0 if a + a2 + a3 is even C1 = 1 if a1 + a2 + a3 is odd C2 = 0 if a1 + a3 + a4 is even C2 = 1 if a1 + a3 + a4 is odd C3 = 0 if a2 + a3 + a4 is even C3 = 1 if a2 + a3 + a4 is odd

The sums shown above are called parity check sums - so named because their purpose is to ensure that the sum of various components of the encoded message is even. For example, c1 is defined in so that a + a2 + a3 + c1 is even

Example: Construct the Hamming code word corresponding to the 4 bit string 0101

 a1 + a2 + a3 = 0 + 1 + 0 is odd so c1 = 1 a1 + a3 + a4 = 0 + 0 + 1 is odd so c2 = 1 a2 + a3 + a4 = 1 + 0 + 1 is even so c3 = 0

The Hamming code word corresponding to 4 bit string 0101 is 0101110.

See Activity 1 for a student activity to construct the entire (7,4) Hamming code.

The complete (7,4) Hamming Code is given on a separate sheet.

Every possible sequence of 7 bits is either a correct message (corresponds to a Hamming code word) or contains exactly one correctable error.

Hamming Codes - Error Detection and Error Correction

Sometimes , due to noisy transmission, code words contain errors. The Hamming Code is designed to detect and correct errors in 4 bit transmissions.

Suppose a message is received as 1111010.
Is this a Hamming code word?
If not, what word should it have been?

In order to determine if the message received is a Hamming Code word, we simply scan the code. If it is one of the 16 code words, we know the message is received as sent.

If it is not among the 16 code words, we compare the message received with each code word and compute the Hamming distance for each. The Hamming distance is defined as the number of times a bit in the received message differs from the bit in the code word. 1111010
 For example: compare the code word 0001011 with the received word they differ in 4 positions

The Hamming distance in this case is 4.

Using the (7,4) Hamming Code Sheet, we will compute all the Hamming distances for the received message 1111010.

Once all the distances are computed, we locate the Hamming code which produces the shortest distance for 1111010 - We also call this the "nearest" code word. This code will be the code used to correct the transmission error. In this case, 1011010 is the corrected code.

If there is more than one shortest distance, we do not correct the message.

See Activity 2 for student activities involving Hamm'ng distances and error correction. I I

Hamming Town

The grid shown on the transparency simulates a town in which all possible seven digit binary words reside. The legal Hamming codes live in the "face" squares. The illegal codes, codes with errors, live in the non "face" squares. The grid shows that each illegal string is in the neighborhood of exactly one legal code. When one digit of a code is changed, the new code moves one square away. If two digits are changed, the code moves two squares away.

Notice that if only one digit of a legal code is changed, the "errored" code is still in the neighborhood of the correct code and will be error corrected to the correct code. If two or three digits are changed, then the "errored" code will move into the neighborhood of a different code word and the word will be improperly decoded.

Each legal Hamming code is shown with eight neighbors. Actually only seven illegal words reside in each "neighborhood". The extra words can be thought of as empty houses on the block.

This grid may be help students visualize how error correction works.

References

Malkevitch, Joseph, Froelich, Gary, Codes Galore, COMAP, MA, 1991

Shiflet, Angela, Discrete Mathematics for Computer Science, West Publishing Company, Minnesota, 1987

Roman, Steven, An Introduction to Discrete Mathematics, Saunders College Publishing, 1986

Crisler, Nancy, et.al., Discrete Mathematics Through Applications, W.H. Freeman and Company for COMAP, 1994

Garfunkel,Solomon, et. al., For All Practical Purposes, 2nd ed., W.H.Freeman for COMAP, 1991

Internet and DREI Resources:

http:Hdimacs.rutgers-edu/drei/1997/classroom/lessons

http://www.astro.virginia.edu/-eww6n/math/Error-CorrectingCode.html

http://www.uniinc.msk.ru/techl/1994/er-cont/hamming.htm

http://www-history.mcs.st-and.ac.uk/-history/Mathematicians/Hamming.html