Though initial claims of Turbo Code performance met with wide skepticism, critics quickly reversed course as a trickle of early positive reports turned into an avalanche of confirmations. At the same time, attention shifted from the question, "Do Turbo Codes achieve near Shannon-limit performance?" to "What attributes enable Turbo Codes to perform so well?" Likewise, having introduced Turbo Codes in Part 1 of this series (Ref 1) and having described their basic construction in Part 2 (Ref 2), this article addresses the latter question. Key concepts addressed include the reason Turbo Codes use RSC (recursive systematic convolutional) encoders; interleaver impacts, code distance and distance-distribution properties, Turbo Code variations, and soft-output/iterative decoding. The following installment completes this series with a discussion of Turbo Code applications.

Illustrative example

To best illustrate the aforementioned issues, consider an example. Fig 1 shows a Turbo encoder that consists of the parallel concatenation of two simple RSC encoders.

It first divides the input bit stream d into blocks of length N bits, which go to each encoder. The first one operates on the block as is and generates N parity bits y¹ that it then transmits along with the N original information bits. The second encoder operates on the same data block but with the bits permuted (shuffled) in a fixed pattern as determined by the interleaver p. The system also transmits the resulting N parity bits y² along with d and y¹. The final block of 3N bits forms the output codeword the system produces from the original N bits. From Parts 1 and 2 of this series you know that this Turbo encoder is called a (3, 1, N) Turbo Code; in other words, a Rate 1/3 code with block size N.

Even with a fixed value of N, an infinite number of (3,1,N) Turbo Codes are possible. What distinguishes them are the types of constituent encoders, interleavers, puncturing and trellis termination techniques -- a myriad of choices, which is why the Turbo Code literature is so rich and growing. But let's return to Fig 1, which though simple, offers enough complexity and insight to be interesting (Ref 3).

Begin with the first RSC encoder and consider the effect of a weight-1 input block, d = [0100...000], where the weight is just the number of 1 bits. The input is impulsive, and the output is the encoder's impulse response. Fig 2 shows a trellis state diagram for this case, where S₀ is the value (state) of the leftmost memory shows the state of the register, and S₁ shows the state of the other register. The input bits d_k output bits y_k appear along the bottom as a function of the bit number, k. It also shows, left to right, the state transitions that result after each new input bit.

The critical observation is that an RSC encoder has an infinite impulse response, where the encoder transforms a low-weight input to an infinitely weighted output. Obviously, limiting the block size to N in turn limits the weight of the output codeword to a large number less than but on the order of N. This result greatly differs from the case of traditional non-systematic convolutional (NSC) encoders, which have a finite impulse response whose weight is never much larger than the number of registers. Later you'll see why this weakness discourages their use in Turbo Codes.

Next consider the case of a weight-2 input such as d = [01100...000]. The system again transforms it into an infinite-weight response, or large-weight codeword for block size N. Such a transformation occurs with many, but not all, possible weight-2 inputs. Indeed, some weight-2 inputs can lead to low-weight outputs. Consider the sequence d = [0100100...000] and its resulting trellis diagram (Fig 3). This input sequence is self-terminating; in other words, the second One bit causes the memory registers to clear and results in zeroing the remaining portion of the codeword. The output parity codeword is y = [0111100...000], which is only a weight-4 codeword, regardless of size N.

Now why is this situation bad? It certainly isn't obvious, but extensive analyses (as in Ref 4 and elsewhere) have determined that the limiting factor in Turbo Code performance is due to such weight-2 input sequences. The basic argument deals with the minimum distance (weight difference) between possible codewords generated at the transmitter.

For example, assume that the system encodes an all-Zero information block. At the transmitter, not only d but each of the ys is a weight-zero block. At the receiver, the decoder must determine the most likely transmitted sequence. You'd think the job should be easy because all the transmitted bits are Zero, but now imagine that the receiver reads some of them in error. Even if just a few errors occur, the received codeword might look more like one of the other (low-weight) codewords the transmitter could've sent rather than the actual all-Zero codeword. For example, if the receiver sees just six erroneous bits, the received codeword might look exactly like the one in Fig 3. This situation would cause the first decoder at the receiver to think that the transmitter sent the weight-2 information sequence [0100100...000] instead of all Zeros.

Interleaver and 2nd encoder

To mitigate against such confusion, Turbo Codes use a second encoder that double checks the first one. However, the second encoder would do no good if it operated on exactly the same information block d. For this reason, an interleaver permutes the bits in block d before the second encoder operates on it. The permuted block retains the same weight, and as just mentioned, not all weight-2 input sequences lead to low-weight output codewords. Thus the interleaver's goal is to permute all the "bad" input-sequences (those that result in low-weight codewords) into ones that lead to large-weight output codewords. But note the rub: different interleavers achieve this goal to varying degrees, and interleaver design is complex enough that it's a major research area.

To illustrate interleaver impact, consider a block size of N = 16 and continue the illustrative example by including the second encoder and interleaver from Fig 1. Assume the interleaver is rectangular, 4 x 4, and that it reads in data row by row and writes them out column by column. Also consider a weight-2 input block d = [1001:0000:0000:0000] that leads to a low-weight output codeword y¹ = [1111:0000:0000:0000] from Encoder 1. Reading d row-wise into the 4 x 4 array yields:

and reading it out column-wise yields d' = [1000:0000:0000:1000]. Using this vector as the input to the second encoder yields a codeword y² = [1110:1101:1011:1000], which has a relatively large weight = 10 (decimal). Hence it appears that the interleaver has truly helped. (Note that the total weight of the transmitted Turbo codeword equals the sum of the weights of d, y¹ and y ² , in this case 16 = 2 + 4 + 10).

Yet, things don't always work out so well. Consider the nearly identical weight-2 input block d = [0100:1000:0000:0000]. As shown in Fig 3, y¹ = [0111:1000:0000:0000], an undesirable low-weight codeword. Again you'd like the interleaver to mitigate this result. Feeding d into the interleaver results in the following array:

and reading d' out column-wise yields d' = [0100:1000:0000:0000]. In this case, the interleaver permutes the input into the identical information sequence -- a very bad result.

As it turns out, rectangular interleavers are notoriously poor in achieving the goal of mapping poor-codeword producing inputs, d, to better ones, d'. Much better are pseudorandom interleavers that scramble the input data in a relatively unordered fashion. But which pseudorandom interleaver is best? It's impossible to test them all, especially as N gets large, but Ref 4 shows that the average pseudorandom interleaver has very good properties -- and finding one that works as well as average isn't extremely hard. However, all this searching is intricately related to the specific constituent encoders used, and finding a set of design rules would be of major benefit. Researchers have discovered some such rules (Ref 3), but the search continues.

Turbo Code variations

In addition to finding better interleavers, numerous other methods can improve Turbo Code performance:

• Instead of using identical constituent encoders, use two entirely different ones. This method introduces additional diversity and reduces the likelihood that low-weight input sequences will have a negative impact at both encoders. On the down side, this approach complicates the decoding process and leads to difficult implementation.

• Instead of using just two constituent encoders in a parallel concatenation and a single interleaver (Fig 1), add a third encoder and second interleaver. Doing so provides opportunities for even more codeword diversity at the expense of increased overhead due to transmission of the added parity bits.

• Increase interleaver size. It's perhaps the most effective way of improving performance, assuming that you're working with good interleavers. (For instance, there's almost no benefit to increasing the size of a rectangular interleaver.) For dual-encoder Turbo Codes, the BER is roughly proportional to 1/N, so a tenfold increase in interleaver size can reduce BER (Bit Rate Error) by approximately a factor of 10. The penalty is the additional delay (tenfold) incurred at the receiver before it can decode a block.

• Use different concatenation arrangements. Turbo Codes have renewed interest in all types of concatenation schemes, particularly when they're coupled with iterative decoding. Though Turbo Codes have made parallel concatenation popular, evidence exists that serial concatenation and hybrid parallel/serial schemes also have great potential (Ref 7).

Performance bounds

As is evident from the previous discussion, the distance properties of a code are key determinants of its error-correcting ability. Every code has a minimum free distance, d_free, such that the Hamming distance between all possible codewords is >= d_free; the larger d _free becomes, the better the code's performance is likely to be. Hence, researchers continue to search for codes with ever larger minimum free distances.

The advent of Turbo Codes with relatively low free distances has caused a reevaluation of such efforts. Researchers now focus on a more complicated set of evaluation criteria, which include maximizing d _free, but that ascribe even more importance to the distribution of codewords across a code's distance spectrum (Ref 4). The following equation provides insight into these issues. It applies to both Turbo Codes and traditional convolutional codes, and it specifies an upper bound on the probability of bit error vs S/N ratio (E_b /N_o ).

The sum operates over all possible distance values for a given code, and the coefficients W(d) enumerate the number of codewords at a given distance from other codewords (that is, W(d) determines the code's distance spectrum). Clearly, it's desirable to minimize W(d) for the smallest distances because that's where most errors arise. Other variables in the equation are: α_code , a constant for a given code; N, the block size; m, the convolutional coder memory size; R, the code rate; and Q(x), the well-known integral of a Gaussian.

The key factor in assessing any code is to find the few terms that dominate the sum. Because Q(x) is an exponentially decreasing function, the Q component of the sum decreases rapidly with increasing d. However, this decrease is modulated by the coefficients W(d), so the largest term in the sum is not necessarily the first.

For good Turbo Codes, the dominant term is the first one, where d = d _free . The plot of this first term versus E_b /N_o is the free-distance asymptote (FDA), and Fig 4 shows how a Rate 1/2 Turbo Code's BER (P_b ) falls very quickly until it approaches the FDA, where it makes a dramatic turn for the worse.

Fig 4 also shows the performance of a traditional very complex maximum free distance (MFD) convolutional code (Rate 1/2, memory 14) along with its FDA. In contrast to the Turbo Code case, each MFD curve is very flat (at low E_b /N_o ) and becomes steeper only at higher S/N ratios. So for small E_b /N_o , the Turbo Code performs significantly better.

Fig 5 again shows Turbo Code performance and its FDA ( d _free = 6), but it also includes the effects of three additional terms from the above sum (d = 8, 10, and 12). Note how each additional term contributes less and less to the limit. In contrast, Fig 6 shows additional terms for the MFD convolutional code. Here, at low E_b /N_o , each additional term actually impacts the limit to a higher degree. The crossing point is at E_b /N_o = 2.7 dB, above which point the FDA (d _free = 18) dominates.

This amazing difference in performance at low E_b /N_o occurs despite the fact that the MFD code has a much larger d _free than the Turbo Code. The reason concerns the coefficients W(d), which impact the term-by-term contribution in the sum. Table 1 lists values of W(d) for both the Turbo Code and the MFD code for the first few values of d. Notice that the coefficients grow explosively for the MFD code in comparison to the relatively slower growth for the Turbo Codes. (The data come from Ref 4.)

At higher E_b /N_o (> 3.5 dB) the relatively flat error floor of the Turbo Code's FDA causes that code's performance to become worse than the MFD code (Fig 4). But at that point the BER is < 10^-7 , which for most systems is more than adequate.

"Thus it can be concluded that the outstanding performance of Turbo codes at low signal-to-noise ratios is a result of the dominance of the free-distance asymptote, which in turn is a consequence of the sparse distance spectrum of Turbo codes, as opposed to spectrally dense convolutional codes." (Ref 4)

Iterative decoding

No description of Turbo Codes would be complete without an examination of the Log Likelihood Ratio (LLR), which is the key to iterative decoding (Ref 5). The final step of any decoding process is a hard decision that yields an output bit stream of 0s and 1s. A soft-decision decoder includes with each hard decision a measure of that decision's quality. Turbo decoders use soft decisions in an ingenious way, allowing them to feed the quality information from one decoder into the next one (Fig 7). They can also feed the output of the last decoder back into the first one. In this way, each stage can utilize quality information gleaned from a previous stage, and the decoding process can iterate any number of times. This feature leads to the Turbo Code name, in reference to the feedback of a Turbo-charged engine.

To examine why the LLR is central to the soft-decision process, consider the transmission of an information bit i ∈ {0,1} across a noisy channel. The transmitter maps the logical values {0,1} to voltages {-1,1}, respectively; and then it sends a signal to the receiver, which measures a noisy voltage r. For a hard decision, the receiver can compare the received signal r with a zero threshold and decide whether i = 0 or i = 1 according to the sign of r.

Clearly, the quality of such a decision depends upon the extent that r deviates from zero: values close to zero don't lend much confidence that the decision is correct. If the receiver sees a voltage of 0.1V, it makes a decision i = 1 but with low confidence. The question then arises: Does a voltage of 0.2V lead to twice the confidence, and does 0.4V mean twice the confidence of 0.2V?

The answer, of course, depends on the type of distortion induced by the channel. Most commonly, the channel is Gaussian and the confidence levels follow a Gaussian distribution vs voltage deviation from ±1V. In other words, the probability density functions (PDFs) could be

Because you don't known a priori whether the transmitter sent a 0 or a 1, the receiver must determine which of the two a posteriori probabilities is greater, P(i=1|r) or P(i=0|r), and so it examines their ratio. When the ratio is < 1 it decides i = 1, otherwise i = 0. Working with ratios and exponentials motivates taking the logarithm of this ratio, the LLR:

For a hard decision, the receiver decides i = 1 whenever LLR > 0 and i = 0 when LLR < 0. For a soft decision, the LLR's magnitude is the quality measure.

Based on the last equation, you can say that the LLR is composed of two components:

The first term, Λ(i), takes into account the a priori probabilities of sending a 0 vs 1. If the probabilities are equal, as is often the case, then Λ(i) = 0. The second term, Λ(r|i), takes into account the channel distortion of the transmission because it includes the effect of the channel noise PDF as described above. This term is of most interest to the decoder algorithms that rely on the LLR.

Lastly, because Turbo Codes use systematic encoders, the channel LLR is itself composed of two parts:

where Λ _i is the LLR based on the i systematic part of the received data (the information bits), and Λ _e is the LLR of the received parity bits. Also called the extrinsic information, Λ _e is shared between Turbo Code decoder stages. These LLRs form the basis of the soft-decision measures used in the special maximum a posteriori probability (MAP) and maximum likelihood (ML) decoding algorithms employed in Turbo decoding. Ongoing research continues to improve these algorithms. For a leading example with a comprehensive list of references, see Ref 6.

Acknowledgment

The author would like to thank Scott Francis for reviewing this column.

References

1. Gumas, CC, "Turbo codes rev up error-correcting performance," Personal Engineering & Instrumentation News, Jan 1998, pgs 61-66.
2. Gumas, CC, "Turbo codes build on classic error-correcting codes and boost performance," Personal Engineering & Instrumentation News, Feb 1998, pgs 54-63.
3. Dolinar, S and Divsalar, D, "Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations," TDA Progress Report 42-122, JPL, Pasadena, CA,15 Aug. 1995, pgs 56-65.
4. Perez, LC, Seghers, J and Costello, DJ Jr, "A Distance Spectrum Interpretation of Turbo Codes," IEEE Trans Information Theory, Vol 42, No 6, Nov 1996, pgs 1698-1709.
5. Berrou, C and Glavieux, A "Near Optimum Error Correcting Coding and Decoding: Turbo Codes," IEEE Trans Communications, Vol 44, No 10, pgs 1261-1271, Oct 1996.
6. Benedetto, S, Montorsi, G, Divsalar, D and Pollara, F, "Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes," TDA Progress Report 42-124, Jet Propulsion Laboratory, Pasadena, CA, pgs 63-87, 15 Feb 1996,.
7. Divsalar, D and Pollara, F, "Hybrid Concatenated Codes and Iterative Decoding," TDA Progress Report 42-130, JPL, Pasadena, CA, pgs 1-23, 15 Aug, 1997.

Charles (Chuck) Gumas serves as Project Lead/Communications Engineer at the MITRE Corp's Information Systems and Technology Div (Reston, VA). He received an MSEE from Lehigh Univ and a BS in physics from the Univ of Pennsylvania. He maintains a web site at www.dc.net/spartan/chuck.html and can be contacted via email at cgumas@mitre.org.

This article originally appeared in Personal Engineering & Instrumentation News, March 1998, pgs 65-71. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.