INTRODUCTION TO DATA COMMUNICATION 9

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

logic.

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).