Error-control coding options abound

Last month we covered applications and limitations of error-control codes and some of the theory behind their operation. This month we cover coding techniques. Specifically, we will discuss automatic repeat request, or ARQ, forward error correction, hybrid ARQ, interleaving and concatenation.

An error-detection code by itself does not control errors, but it can be used to request repeated transmission of errored code words until they are received error-free. This technique is called ARQ. In terms of error performance, ARQ outperforms forward error correction (FEC) because code words always are delivered error-free (provided the error-detection code doesn’t fail). However, this performance does not come free of charge — we pay for it with decreased throughput.

The chief advantage of ARQ is that error detection requires simpler decoding than error correction. ARQ also is adaptive because it only re-transmits information when errors occur. On the other hand, ARQ schemes require a feedback path that may not be available.

There are two types of ARQ:

• Stop-and-wait ARQ: With stop-and-wait ARQ, the transmitter sends a single code word and waits for a positive acknowledgement (ACK) or negative acknowledgement (NAK) before sending any more code words. The advantage of stop-and-wait ARQ is that it only requires a half-duplex channel. The main disadvantage is that it wastes time waiting for ACKs, resulting in low throughput.

• Continuous ARQ: Continuous ARQ requires a full duplex channel because code words are sent continuously until a NAK is received. Typically, only the code word corresponding to the NAK is re-transmitted. Continuous ARQ offers greater throughput efficiency than stop-and-wait ARQ at the cost of greater memory requirements.

FEC is appropriate for applications where the user must get the message right the first time. A voice circuit is one example. Today’s error-correction codes fall into two categories:

• Block codes: The repetition code introduced in last month’s column (MRT, January, page 51) is an example of a binary block code. It is important to note that not all block codes are binary. In fact, one of the most popular block codes is the Reed-Solomon code that operates on m-bit symbols, not bits. Because Reed-Solomon codes correct symbol errors rather than bit errors, they are very effective at correcting burst errors. For example, a 2-symbol error-correcting Reed-Solomon code with 8-bit symbols can correct all bursts of 16 bits or less in length. Reed-Solomon codes are used in JTIDS, a NASA deep-space standard, and CD players.

• Convolutional codes: With con-volutional codes, the incoming bit stream is applied to a K-bit-long shift register. For each modification to the shift register, b new bits are inserted and n code bits are delivered, so the code rate is b/n. The power of a convolutional code is a function of its constraint length, K. Large constraint-length codes tend to be more powerful.

Unfortunately, with large constraint length comes greater decoder complexity. There are several effective decoding algorithms for convolutional codes, but the most popular is the Viterbi algorithm, discovered by Andrew Viterbi in 1967.

One drawback of the codes we have examined so far is that they require bandwidth expansion to accommodate the added parity bits should the user wish to maintain the original unencoded information rate. In 1976, Gottfried Ungerboeck discovered a class of codes that integrates the encoding and modulation functions and does not require bandwidth expansion [1]. These codes are called Ungerboeck codes or trellis coded modulation (TCM). Nearly every telephone line modem or DSL modem on the market today operating above 9.6 kb/s uses TCM.

Other coding techniques exist that are worth examining, such as hybrid ARQ. Hybrid ARQ schemes combine error detection and FEC to make more efficient use of the channel. At the receiver, the decoder first attempts to correct any errors present in the received code word. If it cannot correct all the errors, it requests retransmission using an ARQ technique.

Another technique to consider is interleaving. Many real-world channels are burst-error channels. For example, the mobile radio channel is a burst-error channel as a consequence of multipath fading. The most popular way to correct burst errors is to take a code that works well on random errors (e.g., a convolutional code) and interleave the bursts to “spread out” the errors so that they appear random to the decoder. There are two types of interleavers commonly in use today, block interleavers and convolutional interleavers. Figure 1 on page 38 illustrates the operation of a block interleaver.

The block interleaver is loaded row by row with L code words, each with a length of n bits. These L code words are then transmitted column by column until the interleaver is emptied. Then the interleaver is loaded again, and the cycle repeats. At the receiver, the code words are de-interleaved before they are decoded. A burst of length L bits or less will cause no more than 1 bit error in any single code word. The random error decoder is much more likely to correct this single error than the entire burst.

The parameter L is called the interleaver degree, or interleaver depth. The interleaver depth is chosen based on worst-case channel conditions. It must be large enough so that the interleaved code can handle the longest error bursts expected on the channel. The main drawback of interleavers is the delay introduced with each row-by-row fill of the interleaver. The delay is a function of the interleaver depth, which, in turn, is a function of the fade duration on the channel. The delay on some channels can be several seconds long. This long delay is often unacceptable. On voice circuits, for example, interleaver delays confuse the unfamiliar listener by introducing long pauses between speaker transitions. Even short delays of less than one-half second are sufficient to disrupt normal conversation.

In theory, interleaving is a poor way to handle burst errors. Why? From a strict probabilistic sense, we are converting “good” errors into “bad” errors. Burst errors have structure, and that structure can be exploited (in theory). Interleavers “randomize” the errors and destroy the structure. Despite this theoretical disadvantage, interleaving is one of the best burst-error-correcting techniques in practice. In fact, the greatest advance in coding theory in the past 15 years, turbo coding, employs a very long random interleaver [2]. Until the coding theorists discover a better way, interleaving will be an essential error-control-coding technique for bursty channels.

Yet another technique worth exploring is concatenation. When two codes are used in series, the combination is called a concatenated code. Concatenated codes often are used when a single code cannot correct all types of errors encountered on the channel. The operation of concatenated codes is best illustrated by example. Figure 2 on page 40 shows the Consultative Committee for Space Data Systems (CCSDS) Blue Book standard for Telemetry Channel Coding (interleaving is omitted for clarity) [3].

The inner code — a rate ½, K=7, convolutional code with Viterbi decoding — corrects most random errors and the outer code — a 16-symbol error correcting Reed-Solomon code — cleans any burst errors that slip through the Viterbi decoder. The Reed-Solomon code operates on 8-bit symbols and therefore is a very powerful burst-error correcting code. The overall code rate is simply the product of the two individual code rates, i.e., (½)(223/255) 0.44. It should be noted that coding gains for concatenated codes are very large.

Next month: Error-control coding in APCO 25 Radios.

Jay Jacobsmeyer is president of Pericle Communications Co., a consulting engineering firm located in Colorado Springs, Colo. He holds bachelor’s and master’s degrees in Electrical Engineering from Virginia Tech and Cornell University, respectively, and has more than 20 years experience as a radio frequency engineer.

References:

1. G. Ungerboeck, “Trellis coded modulation with redundant signal sets Parts I and II,” IEEE Communications Magazine, vol. 25, No. 2, pp. 5-21, February 1987.

2. C. Berrou, A. Glavieux and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes,” IEEE Transactions on Communications, pp. 1261-71, October 1996.

3. E. R. Berlekamp et al., “The application of error control to communications,” IEEE Communications Magazine, vol. 25, No. 4, pp. 44-57, April 1987.