Error detection and correction
Error detection and correction use functions that transform one bit-string into another bit-string.
Example: adding a parity bit
Given an input bit-string, we add a parity bit to make the number of ones odd.
01101 ↦ 011010
01000 ↦ 010001
Example: repeating bits
Unlike parity, this method doesn't just add to the end of the bit-string.
e.g:
011 ↦ 000111111
This can detect all double bit errors and correct all single bit errors correctly. It corrects some two-bit errors the wrong way, and could correct a three-bit error if each flipped bit was in a separate triple.
1-bit error example
011 ↦ 000111111 which is corrupted to 000111101
Then the closest correct code is 000111111, so the error is detected and corrected.
2-bit error example
011 ↦ 000111111 which is corrupted to 000111100
The corrupted code is not a valid code (there's no input that would give it), so the error is detected.
However, the closest code is 000111000 - i.e. the code for 010 - so the error is corrected wrongly.
Hamming Distance
Given a function like the one above s.t. its output is always the same length, the Hamming distance between two strings in its image is the number of bits that must be flipped to transform one into another. The minimum Hamming distance of the function is the minimum value of this number for any two strings in the image.
Consider the the parity function earlier, but for 2 bit inputs:
00 ↦ 001
01 ↦ 010
11 ↦ 111
10 ↦ 100
Each of these is at least 2 bit-flips apart (in fact each is exactly two apart) so the minimum Hamming distance is two.
CRC
Cyclic redundancy code (CRC) is a popular error detection technique.
Read my Haskell implementation of CRC to see what it does.
Links
Copyright (C) 2006-8 Ryan Lothian. All rights reserved.