4.2.3 Simple Coding Example
The basic principles of coding can be illustrated using a simple repetition code, which demonstrates how redundancy can be used to reduce the probability of transmission errors. This example follows the standard 3-bit repetition model commonly used to illustrate basic error-control principles.
Consider a binary data stream in which each bit is repeated three times before transmission. That is, a logical ‘0’ is transmitted as ‘000’, and a logical ‘1’ as ‘111’. At the receiver, each group of three received bits is decoded by majority decision, as shown conceptually in Figure 4.2.
For example, if the probability of a single-bit error in the channel is p=10–2, the receiver can still recover the original bit correctly whenever only one of the three bits is received in error (e.g., sequences 001, 010, or 100 for a transmitted 000).
An error occurs only when two or more bits are corrupted. The total probability of an incorrect decision, Pe, is:
Thus, the use of a simple threefold repetition code reduces the probability of error from 10−2 to approximately 3×10−4, albeit at the cost of tripling the bandwidth or data rate.
Theoretically, as illustrated in Figure 4.3 any desired level of reliability could be achieved by repeating each symbol multiple times. However, for a fixed data rate, the effective information rate would decrease in direct proportion to the repetition factor. Conversely, maintaining the same information rate would require a proportional increase in the transmitted data rate.
Of course, repeating each bit an infinite number of times is not practical, since it would require either infinite time or infinite bandwidth. The lesson of this brute-force example, however, is clear: the error rate can be reduced to an arbitrarily low level, provided that we are willing to pay the price in transmission time or bandwidth.
Fortunately, far more efficient coding schemes exist than simple bit repetition. Nevertheless, several useful general points about error-control codes can be noted, even from this simple case:
- Increasing redundancy reduces error probability. It is theoretically possible to reduce the bit-error probability to an arbitrarily low level—even with a simple repetition scheme. In the limiting case, as the redundancy approaches infinity, the probability of uncorrected error approaches zero.
- Sufficient redundancy allows both error detection and correction. The more redundant information introduced, the greater the code’s capability to recognize and correct bit errors.
- Adding redundancy requires additional bandwidth or lowers data throughput. The introduction of redundancy necessarily reduces spectral efficiency. For example, a triple-repetition code has a code rate of 1/3: to maintain the same information rate, the occupied bandwidth must triple; alternatively, for a fixed bandwidth, the information rate is reduced to one-third of the transmitted bit rate.
- Zero error probability is unattainable. Although error probability can be made arbitrarily small by increasing code length and redundancy, it cannot be driven strictly to zero for any finite system. Residual errors must therefore be anticipated and, where necessary, managed by higher-layer protocols or application mechanisms. The code designer must recognize that for any finite level of redundancy, some residual error probability will remain.
Finally, note that comparing the received sequence against every valid codeword to find the closest match is computationally impractical for real-world codes. Many practical codes contain on the order of 21000 (10300) to 22000 (10600) possible codewords. Fortunately, these codes are highly structured, and their internal mathematical properties can be exploited to locate the nearest valid codeword efficiently during decoding.
Back to reading