4. ERROR DETECTING CODES. Shannon proved the surprising result that information can
reliably be transmitted on a channel up to a maximum rate, called the channel capacity. At rates
above capacity reliable communication is impossible, but an arbitrarily small probability of error
can be achieved at rates below capacity,provided one is willing to jointly encode and decode large
numbers of information bits. This requires complex and expensive equipment.
Shannon's theory has had little practical effects on commercial communication systems in that
error correcting codes are little used. This is due to two reasons. First, the relationships between
signal and noise powers, and data rate and channel bandwidth are such that the probability of
error cannot be reduced by error correcting codes. Secondly, channels are typically two way. This
property does not increase capacity but makes it simple to achieve reliability by using error
detecting codes and requesting data retransmissions when errors are detected. The situation is just
the opposite on the deep space channel; space probes make successful use of error correcting codes.
We will spend the rest of this section examining the fundamentals of the theory of error
detecting codes.
Error detecting codes are usually implemented as polynomial codes, also known as cyclic
redundancy codes. The operations described below are extremely easy to implement using digital
A block of N binary digits that is to be protected by L check bits is viewed as a polynomial
Mix) of degree N+L—l on the finite field with two elements. The N high order coefficients are
the data bits themselves, the L low order coefficients being zero.
Both the transmitter and receiver agree on a generator polynomial Gix) of degree L. The
transmitter computes the remainder Rix) of the division of Mix) by Gix) and transmits the
N+L coefficients of Gix)-Rix).
The receiver just checks that the received polynomial is divisible by Gix). If it is, no error is
assumed to have occurred and the N high order coefficients are retained as data bits. If it is not,
then the receiver requests a retransmission of the block. Insuring that blocks are never lost or
duplicated requires non trivial protocols between transmitter and receiver. They are beyond the
scope of these notes.
We now turn our attention to the kinds of errors that are detected by these codes. An error
pattern can also be viewed as a polynomial Eix) of degree N+L—l. It will be detected unless it
is divisible by Gix).
Previous Page Next Page