### 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:

x

x

x

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

x

x

x

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:

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.

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

x

_{1}=x_{3}+x_{5}+x_{7}x

_{2}=x_{3}+x_{6}+x_{7}x

_{4}=x_{5}+x_{6}+x_{7}One day I noticed that the above equations could be rewritten as follows:

x

_{5}=x_{2}+x_{3}+x_{4}x

_{6}=x_{1}+x_{2}+x_{5}x

_{7}=x_{4}+x_{5}+x_{6}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 Code | Original Data(Decimal) | Original Data(Binary) | |
---|---|---|---|

0 | 0000000 | 0 | 0000 |

1 | 0001111 | 7 | 0111 |

2 | 0010110 | 14 | 1110 |

3 | 0011001 | 9 | 1001 |

4 | 0100101 | 5 | 0101 |

5 | 0101010 | 2 | 0010 |

6 | 0110011 | 11 | 1011 |

7 | 0111100 | 12 | 1100 |

8 | 1000011 | 3 | 0011 |

9 | 1001100 | 4 | 0100 |

10 | 1010101 | 13 | 1101 |

11 | 1011010 | 10 | 1010 |

12 | 1100110 | 6 | 0110 |

13 | 1101001 | 1 | 0001 |

14 | 1110000 | 8 | 1000 |

15 | 1111111 | 15 | 1111 |

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.

## Comments