Frances M. Gasman (fgasman@dimacs.rutgers.edu)
Building a (7,4) Hamming Code
Decoding 7 digit messages
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.
| For example: | compare the code word | 0001011 |
| with the received word | 1111010||
| they differ in 4 positions |
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.
Hamming Codes Activity 1 attachment
Hamming Codes Activity 2 attachment
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
