Error correcting codes
Given m message bits and r checkbits. Design a code that will allow all single bit errors to be corrected.
- Each of the 2^m legal messages has n illegal codewords at a distance 1 from it (just invert each of the n bits in the n-bit codeword)
- Thus each 2^m legal messages requires (n+1) bit patterns dedicated to it
- (n+1)2^m <= 2^n but n = m + r so (m+r+1) <= 2^r. Given m we get a lower limit on r (number of check bits) to correct single bit errors.