In coding and modulation theory, an interesting parameter is called Euclidean distance. Euclidean distance is associated with the "analog" measure of separation between points in signal space (Fig. 1). Clearly, the two points chosen in the plot are the closest in Euclidean distance for this signal set. When detecting the 8-PSK signal that's embedded in noise and distortion, the points separated by this smallest distance are more likely to be mistaken for one another. These adjacent points contrast, for example, to two points on opposite sides of the ring. As such, the symbol error probability for 8-PSK (or any modulation defined by discrete signal space points) is dominated by points closest to one another in Euclidean distance.

Euclidean distance is an important concept, because coding theory has much history in the use of Hamming distance. Hamming distance measures the number of different digits in a digital word, one that typically has overhead attached for coding-gain purposes. It's thus a "digital" difference, and because of that, some geometric signal space information is lost. As an example, for QPSK, adjacent symbol states normalized to a magnitude of unity are separated in Euclidean distance by the square-root of 2, and separated in Hamming distance by 1. Adjacent symbols in Hamming distance, for example, are 00 and 01.

One of TCM's great strengths is that it is based on Euclidean distance. It's always been a key part of modulation or signal design to create signal spaces aimed at maximizing Euclidean distance among symbols, because it's best for successful detection probability. By contrast, for coding theory, traditionally a separate entity, among many of its key principles historically is a significant theoretical basis using Hamming distance properties.

Sequences versus symbols
Another of the key underlying concepts associated with TCM, is that performance enhancements from coding are limited if we consider only the hard decision, or a symbol-by-symbol approach to detection. Hard decision decoding makes a "hard" (1/0-like) decision on each symbol. This process eliminates some information in the analog sense for a noise and distortion impaired symbol. Soft decision detection determines symbols as part of an overall determination of a complete or partial sequence of symbols.

Soft decision detection is well suited to dependent symbols such as in distorting channels, or deliberately dependent symbols. Symbol dependency is an inherent part of TCM encoding, as well as in other traditional codes. Clearly, sequence detection is complicated by the fact that many different possible sequences exist compared to individual possible symbol states. However, algorithms powerful enough to handle the necessary processing have been developed and matured in response to this need. Sequence detection isn't unique to TCM, but important to it.

The unique aspect of TCM that creates its important system gain value is the mapping used to create coded modulation symbols from incoming data in a process called set partitioning. However, it's important to recognize that an important goal of set partitioning is to maximize Euclidean distances. If we integrate the Euclidean distance concept with the idea of sequence detection, we can envision a total Euclidean distance by adding up all of the individual distances between the observed values, against all possible ideal symbol sequences the observed sequence might represent. "All possible sequences" sounds onerous, so again, powerful processing (Viterbi decoding) intervenes. If we're trying to determine the most likely sequence sent, the best choice is the one with the smallest error between the ideal and actual Euclidean distance of a possible sequence.

In terms of error performance, the most likely sequences to be confused are those that differ the least in Euclidean Distance, or the possible sequences of symbols with the smallest Euclidean Distance between them. This is analogous to the 8-PSK symbol case, where the most likely errors are between symbols that are closest to one another. In the sequence case, we're talking about many such symbols in aggregate, as a sequence. This minimum distance is called the free distance.

Soft decision detection determines symbols by observing an entire symbol sequence before making a sequence selection, instead of making a decision on each individual symbol. This is important because once a hard decision is made on an individual symbol, all of the analog information about what was received is gone. This information might otherwise be useful when there's dependence among symbols. A soft decision makes note of the analog samples, and uses it to make an informed sequence decision. The use of soft decision detection, which preserves and takes advantage of analog information, and the unique concept of set partitioning, are what make TCM powerful in terms of coding gain.

Set partitioning and encoding
The key to TCM encoding is the set partitioning (Fig. 2). The convolutional encoder's output of the—k of the payload bits becoming n output bits (n is greater than k) for a rate k/n encoder—selects one of the set partition'ssubsets in the TCM mapper. There are 2n subsets. The remaining bits delivered to the TCM mapper choose a point within the subset selected by the other two bits. In the example, one symbol is sent the convolutional encoder, which is basically a delay and multiply operation that outputs two coded symbols. This dependent, coded pairing is sent to the mapper. The two bits pick a sub-constellation from the subsets which have been methodically broken down into bipolar pairs. The final bit chooses one of the signal space points of the two within the chosen subset.

How does this represent an improvement over a regular signal space code? The important part of this methodical pairing process called set partitioning is that the mapping approach results in a coded signal space with subsets of maximum Euclidean distance (Figs. 1 and 2, again). There are two input bits, a1 and a2. Uncoded, they could represent inputs to a QPSK modulator. To convert into a TCM signal, one of them, a2, is used in the convolutional encoder of rate 0.5, creating two symbols, b1 and b2. Two symbols are needed to select one of four constellation subsets, each of size two. The last "uncoded" input bit, a1, completes the set partition by choosing one of the two.

Note that the selection of which bipolar constellation pair using b1 and b2 is hardened from a sequence detection standpoint, because it passes though a convolutional encoder that ties the output bits together in a known dependent relationship. The remaining bit, a1, selects one symbol from the set of two selected by b1 and b2. This "uncoded" bit is used to select for transmitting one or two Euclidean separated points, providing the least possible chance of error. Notice how the choice between any set of two is between maximally separated symbols in Euclidean distance. Thus, even this raw input to the TCM mapper is made maximally robust through the strength of the set partitioning rules.

A smooth transition
TCM concepts and theory smoothly became TCM hardware systems. One of the reasons for this is because the ideas are straightforward and relatively non-complex. While modulation and coding grew up independently, once the value of coding gain became apparent, broader thinking about overall communication system optimization came into play. Subsequently, some great minds realized that 1 + 1 = 3 when it comes to the intelligent combining of these once independent subsystems.

About the author
Rob Howald rhowald@xytrans.com) is the vice president of engineering at Xytrans Inc. He is also the former director of systems engineering in the transmission network systems group of Motorola's Broadband Communications Sector in Horsham, Pa. He has a BSEE and an MSEE from Villanova University, a PhD from Drexel University, and an MBA from DeSales University.

References
Biglieri, E., D. Divsalar, P. McLane, and M. Simon, Introduction to Trellis-Coded Modulation with Applications, Macmillan Publishing, NY, NY, 1991.
Ungerboeck, G., “Channel Coding with Multilevel/phase Signals”, IEEE Trans. Information Theory, IT-28, Jan. 1982, pgs.55-67.
Ungerboeck, G., “Trellis-Coded Modulation with Redundant Signal Sets – Part 1: Introduction”, IEEE Communications Magazine, Feb. 1987, pgs. 5-11.