The Art of Doing Science and Engineering: Learning to Learn

by Richard Hamming

Having done all we are going to do about source encoding (though we have by no means exhausted the topic), we turn to channel encoding, where the noise is modeled. The channel, by supposition, has noise, meaning some of the bits are changed in transmission (or storage). What can we do? Detection of a single error is easy. To a block of n – 1 bits we attach an nth bit, which is set so that the total n bits has an even number of 1s (an odd number if you prefer, but we will stick to an even number in the theory). It is called an even (odd) parity check, or more simply a parity check. Thus if all the messages I send to you have this property, then at the receiving end you can check to see if the condition is met. If the parity check is not met then you know at least one error has happened; indeed, you know an odd number of errors has occurred. If the parity does check, then either the message is correct, or else there are an even number of errors. Since it is prudent to use systems where the probability of an error in any position is low, then the probability of multiple errors must be much lower. For mathematical tractability we make the assumption the channel has white noise, meaning: (1) each position in the block of n bits has the same probability of an error as any other position, and (2) the errors in various positions are uncorrelated, meaning independent.