?

Log in

AlbertJayNock

FUN WITH HAMMING CODE!!!

When I teach hamming code in my networks class, I generally give examples with four data bits. This is enough to provide a meaningful (if not realistic) example.

With four data bits, the parity bits are computed as follows:

x1=x3+x5+x7
x2=x3+x6+x7
x4=x5+x6+x7


One day I noticed that the above equations could be rewritten as follows:

x5=x2+x3+x4
x6=x1+x2+x5
x7=x4+x5+x6

This rewriting shows that the full hamming code string can be determined by the first 4 bits.This isn't much use for error-checking, but it has one consequence I find interesting.

Since every 4 bit number has a unique hamming code, and the first four bits determine the hamming code, there is necessarily a bijection the first 4 bits and the original 4 bit string. So it gives a permutation of the numbers 1 through 14 (0 and 15 map to themselves) . The bijection is illustrated by the table below:

 Hamming CodeOriginal Data(Decimal)Original Data(Binary)
0000000000000
1000111170111
20010110141110
3001100191001
4010010150101
5010101020010
60110011111011
70111100121100
8100001130011
9100110040100
101010101131101
111011010101010
12110011060110
13110100110001
14111000081000
151111111151111

The cycle notation for this permutation is  (1  7  12  6  11  10  13)(2 14 8 3 9 4 5)

I think that's cooler than leftover grits.
Tags:

Comments