Hamming Code

This is a bit of a departure from data structures (which I'm in the middle of), but I wanted to cover Hamming Code and Error Checking since I had just covered bitwise operations.

Checking for bit stream errors with Hamming code

I'm really impressed with this marvel. If you don't know, Hamming Code is a special way of laying out informational bits and interspersing parity bits within the stream. For each position in the data that is a power of 2, a parity bit is injected. The responsibility of the bit is to act as a checksum by recording a 0 or a 1 to ensure that number of bits it is checksumming, including itself, is even (when using the even parity method). In 7-bit Hamming Code, there are 4 data bits and 3 parity bits. Each parity bit is responsible for 3 data bits. When the bit stream is transmitted, the parity bits are checked on the other end. If the parity checks fail, you can use the checks to figure out which bit was corrupted and correct it. It takes 3 parity bits to detect and correct for 1 error in 4 data bits. Without correction, the 3 parity bits can detect corruption of 2 bits.

The 7-bit code is very common, but the code can be used with larger bitstreams, with a parity bit placed at each power of 2. This means in a 7-bit code, 42% of the stream is parity bits, but in a larger stream, the parity bits would be farther apart.

Richard Hamming

This handsome devil is Richard Hamming, who published the method in 1950 while working at Bell laboratories. The method is still used in Error Correcting Code memory, but I'm unsure if the method is still used in data transmission.

comments powered by Disqus