User:Oli Filth/TCM

From Wikipedia, the free encyclopedia

In a digital communication system, the purpose of a channel code is to increase the average Hamming or Euclidean distance between symbols, so that a greater level of noise or interference may be tolerated. In layman’s terms, this is achieved by taking each source symbol (or sequence of symbols) and assigning it a code, such that the codes are more “different” from each other than the original symbols are…

Until the work of Ungerboeck, this could only be achieved by introducing redundancy, i.e. by replacing each source symbol (or sequence of symbols) by a longer sequence; this is the approach taken in block and convolutional coding. However, this increases the bandwidth of the signal, decreasing its spectral efficiency.

TCM is a method of increasing Euclidean distance without introducing redundancy. Instead, the modulation constellation (alphabet) is increased from 2r to 2r+1, and mapping the source symbols to the modulation symbols with a carefully-selected (r+1, r) convolutional code.

In general, the factors involved are of the form r+k, but k=1 is the simplest, and provides the greatest incremental benefit. This article will consider only the design for k=1.

The description below is not a definitive guide for the design of TCM systems, but I should illustrates the general principle of how it provides a benefit. To fully analyse the gain of a TCM system over an uncoded system, we must consider the average performance, distance spectrum, all paths… computer search, stochastic sampling, ...

In general, TCM may be used with many modulation schemes, including ASK, QAM, PSK and AM-PM.

[edit] Designing a TCM code

As an example, we will take uncoded 4-PSK, and show how a coding gain can be achieved by combining a (3,2) convolutional code with an 8-PSK constellation. The first step is to label the constellation points, as shown in the figure to the right. In this constellation, all points are assumed to lie on the unit circle.

A convolutional code may be described in terms of its transition diagram. A general figure of merit is the free distance, which is the minimum Euclidean distance between two paths which start and end at the same points; this corresponds to two symbol sequences that are the most similar. As convolutional codes are linear, we may take the all-zeros path as a convenient reference from which to measure the Euclidean distances of other paths.

Let us start with uncoded 4-PSK. As a memoryless system, it has only one state, so it may be described in terms of the following trellis, with four parallel transitions. Clearly, the free distance is \sqrt{2}.

Image:1_state_TCM.png

If we now use a two-state trellis, we see that we may now use all constellation points. The Euclidean distance of parallel transitions has now increased to 2, but a path with a smaller distance is marked in red, equating to \sqrt{(\sqrt{2})^2 + (2 \sin(\pi/8))^2} \approx 1.608.

Image:2_state_TCM.png

Continuing the pattern, the next trellis is 4-state. The free distance path is again marked in red, with a distance of \sqrt{(\sqrt{2})^2 + (2 \sin(\pi/8))^2 + (\sqrt{2})^2} \approx 2.141.

Image:4_state_TCM.png

[edit] Mapping by set partitioning

The branch labels used in the examples above were not selected arbitrarily; they correspond to what Ungerboeck termed mapping by set partitioning. If we consider the set of 8-PSK constellation points, we see that the minimum Euclidean distance is 2 \sin(\pi/8) \approx 0.765. We may, however, partition it into two subsets of equal size, whose minimum distance is now \sqrt{2} \approx 1.414. Each of these subsets may be partitioned in turn, and so on, with the minimum distance increasing in each child subset.

Image:Set_partitioning.png

In the 4-state example above, the labels were assigned according to Ungerboeck’s heuristic rules:

  1. All branches leaving a particular trellis node should be labelled from the same LEVEL-X SUBSET.
  2. All branches entering a particular trellis node should be labelled from the same LEVEL-X SUBSET.
  3. All parallel branches must be labelled from the same LEVEL-X SUBSET.
  4. All points must occur with the same probability.
  5. The code should exhibit symmetry.

Rules 1, 2 and 3 ensure the maximum Euclidean separation of paths where there would otherwise be the greatest ambiguity. Rule 4 ensures maximum utilisation of the constellation (Shannon showed that the greatest information transfer occurs when symbols are equi-probable). Rule 5 is not strictly necessary, but it aids the design of efficient TCM implementations.

These rules become increasingly hard to apply manually as the number of trellis states increases, therefore a computer is typically employed to assign the labelling.


As mentioned earlier, the design of good TCM codes is actually more complicated than this. Free distance is only an indicator of performance; a more complete picture is only obtained by considering the distances of all paths and the probability with which each will occur. As with any system involving a convolutional code, the number of distinct paths is generally infinite, as they can be arbitrarily long. However, the probability of a path approaches zero as its length goes up, so performance is bounded. Finding this bound is difficult, so approximations may be made, or computerised stochastic simulations may be carried out.

[edit] Decoding

Due to the trellis-based nature of TCM, existing Viterbi algorithms may easily adapted for its decoding. The decoder must take soft-information into account, i.e. it must perform decoding using Euclidean metrics, not Hamming metrics.