InnoWave Telecommunications

Effectiveness Of Errordetection Codes

The effectiveness of an error-detection code is measured by the probability that the system fails to detect an error. To calculate this probability of error-detection failure, we need to know the probabilities with which various errors occur. These probabilities depend on the particular properties of the given communication channel. We will consider three models of error channels: the random error vector model, the random bit error model, and burst errors.

Suppose we transmit a codeword that has n bits. Define the error vector e = (e1; e2, ■■■, en) where et = 1 if an error occurs in the zth transmitted bit and et = 0 otherwise. In one extreme case, the random error vector model, all 2n possible error vectors are equally likely to occur. In this channel model the probability of e does not depend on the number of errors it contains. Thus the error vector (1,0, ■■■, 0) has the same probability of occurrence as the error vector (1, 1, ■■■, 1). The single parity check code will fail when the error vector has an even number of 1s. Thus for the random error vector channel model, the probability of error detection failure is 1/2.

Now consider the random bit error model where the bit errors occur independently of each other. Satellite communications provide an example of this type of channel. Let p be the probability of an error in a single-bit transmission. The probability of an error vector that has j errors is pp (1 — p)n—', since each of the j errors occurs with probability p and each of the n — j correct transmissions occurs with probability 1 — p. By rewriting this probability we obtain:

where the weight w(e) is defined as the number of Is in e. For any useful communication channel, the probability of bit error is much smaller than 1, and so p < 1/2 and p/(1 — p) < 1. This implies that for the random bit error channel the probability of e decreases as the number or errors (1s) increases; that is, an error pattern with a given number of bit errors is more likely than an error pattern with a larger number of bit errors. Therefore this channel tends to map a transmitted codeword into binary blocks that are clustered around the codeword.

The single parity check code will fail if the error pattern has an even number of 1s. Therefore, in the random bit error model:

where the number of terms in the sum extends up to the maximum possible even number of errors. In the preceding equation we have used the fact that the number of distinct binary «-tuples with j ones and n — j zeros is given by

In any useful communication system, the probability of a single-bit error p is much smaller than 1. We can then use the following approximation: y(1 — pi « p!(1 — pj) ^p. For example, if p = 10—3 then p2(1 — p)n—2 « 10—6 and p4(1 — p)n—4 ^ 10—12. Thus the probability of detection failure is determined by the first term in equation 4. For example, suppose n = 32 and p = 10—4. Then the probability of error-detection failure is 5 x 10—6, a reduction of nearly two orders of magnitude.

We see then that a wide gap exists in the performance achieved by the two preceding channel models. Many communication channels combine aspects of these two channels in that errors occur in bursts. Periods of low error-rate transmission are interspersed with periods in which clusters of errors occur. The periods of low error rate are similar to the random bit error model, and the periods of error bursts are similar to the random error vector model. The probability of error-detection failure for the single parity check code will be between those of the two channel models. In general, measurement studies are required to characterize the statistics of burst occurrence in specific channels.