Math 104 - Cooleymath for Elementary Teachers I OCC

Math 104 - CooleyMath For Elementary Teachers I OCC

Activity #14 – Hamming Codes

In telecommunication, a Hamming code is a linear error-correcting code named after its inventor,Richard

Hamming. Hamming codes can detect and correct single-bit errors, and can detect (butnot correct)

double-bit errors. In other words, the Hamming distance between the transmitted andreceived code-words

must be zero or one for reliable communication.

In contrast, the simple parity code cannot detect errors where two bits are transposed, nor can itcorrect the

errors it can find.

Here we will use Venn diagrams to detect single bit errors and then correct them.Hamming’s scheme

extends a four-bit code word abcd to a seven-bit error correcting codeword abcdefg by choosing e, f, and g

so that each loop contains an even number of 1’s.

4-bit word abcd 7-bit error-correcting word abcdefg

 Examples:

Determine if the following seven-bit code has an error in a single bit. If an errorexists,correct the error.

1)1101110.

Solution:Place the seven-digit word in the three-looped Venn diagram. You will notice that boththe left and

lower loops have an odd number of 1s, yet the right loop has an even number of 1s.Thus, the bit in the

intersection of the left and lower loops, and in the complement of the rightloops, is incorrect. That would be

the digit 1 that is in region b (as labeled from above). Thisneeds to be changed to 0. So, the corrected seven-

bit code is 1001110.

2)1111000.

Solution: In the three-looped Venn diagram, you will notice that all loops have an odd number of1s. Since

only one digit can be changed, it must be the digit 1 that intersects all three loops. Thatwould be the digit 1 that is in region c. This needs to be changed to 0. So, the corrected seven-bitcode is 1101000.

3)0001011.

Solution: In the three-looped Venn diagram, you will notice that all loops have an even numberof 1s,

although in the left loop there are quantity 0 of 1s digits’. 0 is still considered an evennumber. So there is no

single digit error and the correct seven-bit code is 0001011.

 Exercises:Determine if the following seven-bit code has an error in a single bit. If an errorexists,

correct the error.

1)11001102)10101013)1110111

1