Trellis code
The trellis coded modulation , as Ungerboeck code , trellis coding , trellis modulation , abbreviated as TCM is designated, one in the digital signal processing combination used in channel coding for forward error correction of transmission errors, and a modulation technique for digital information via electric lines such as transferring phone lines .
Trellis code modulation was developed by Gottfried Ungerböck in 1982 and was widely used in the following years in telephone modems that work according to the ITU-T standards V.32, V.32bis, V.34 and V.fast. However, it is also used in newer transmission systems and is used, for example, with Gigabit Ethernet (1000BASE-T) in combination with a 5-PAM modulation technology. The trellis code is also used in combination with a 16-PAM or 32-PAM for symmetrical DSL access according to the G.SHDSL and SHDSL.bis standards .
Trellis code modulation is a very efficient channel coding or modulation technique that is close to the theoretical limit of the channel capacity and, depending on the specific implementation, only slightly different from the Low Density Parity Check Code (LDPC) and has only lasted a few years Turbo-Codes developed later ( Turbo-Convolutional-Code and Turbo-Product-Code ) is exceeded.
Procedure
Trellis code modulation is one of the coded modulation techniques and is divided into two main functional blocks:
- The channel coding, which in TCM is always a convolutional code with a code rate of (k, k + 1). This means that a code word of length k +1 is formed at the encoder input from a set of k information bits by the convolutional encoder . The additional redundancy bit of the code word is dependent on the k information bits and is used in the context of decoding to detect possible transmission errors. Various types of convolutional encoders can be used with TCM, which differ in length and type of convolutional encoder, whether linear or non-linear.
- The digital modulation on a carrier. A QPSK , 8-PSK , 16-QAM , 64-QAM or the like can be used as the modulation . The k +1 bits of the code word are assigned to exactly one transmission symbol. A modulation consisting of 2 k +1 symbols is therefore necessary . If, for example, a 64-QAM modulation is selected, 64 transmission symbols are available, resulting in k to 5 useful data bits that can be transmitted simultaneously per symbol.
The main difference between trellis code modulation and other separate channel codings and the methods of digital modulation is that the channel coding and the modulation are functionally linked to one another in TCM. With TCM, a code word may only be exactly long enough to be able to be assigned as a whole to a transmission symbol during modulation.
One consequence of this, which only results in the additional code gain of the trellis code modulation, is that, for evaluating possible errors, it is not possible to assume the minimum Hamming distance between two code words, as is the case with channel coding methods designed individually , but instead of the Euclidean distance , which describes the geometric distance between two points in a complex plane. This level is spanned by the amplitude and phase position of the carrier oscillation and assigns individual points in this level to the transmission symbols.
Encoder
The individual bit combinations, from which a code word is formed, are assigned to the respective symbol for the modulation at the encoder. Instead of an assignment that is common with other modulation techniques, for example using the Gray code , Ungerböck chose a structure that is known in mathematics as a binary tree . In the top node, as the individual branch points are called in a binary tree, all 2 k +1 symbols occur. The low-order bit of the code word is taken as a decision to move down one level in the binary tree: Depending on whether the bit of the code word in question is logical 0 or logical 1 . This creates two nodes on the level below, each comprising half of the total possible symbols.
The division of the individual symbols is chosen so that the Euclidean distance between adjacent symbols is maximized. In the case of 8-PSK modulation with 8 symbols on the unit circle , symbols with an even index are written on the right and symbols with an odd index on the left in the binary tree. In the mostly English-language literature, this procedure is referred to as set partitioning : The available transmission symbols are divided (halved) at each level.
The same scheme is then used with the next bit from the code word until all code word bits have been assigned corresponding transitions in the binary tree. In the case of a convolutional code with a 3-bit code word, i.e. 2 useful data bits at the input, a modulation with 8 symbols (2 3 ) such as 8-PSK must be used. This results in 3 transitions between the levels in the binary tree. Only in the lowest level is the specific assignment of a certain symbol, which in this example is selected from the 3 bits of a code word.
The specialty is that with each step down one level in the binary tree the Euclidean distance between remaining symbols on this level increases. The greater the Euclidean distance between the individual symbols, the greater the interference on the transmission channel must be in order for the decoder to make a wrong decision.
If the redundancy bit added by the convolutional encoder is selected as the low-order code bit, in the example with a three-bit long code word the 3rd bit, this bit has the greatest error probability of being incorrectly decoded during transmission because it has the smallest distance to neighboring symbols . At the same time, however, it also carries the least amount of information, since it is only derived from the other two data bits. In the TCM, depending on the selected convolutional encoder, the more significant bits in the code word are often not specially coded at all, but correspond directly to the useful data bits. With these bits, due to the symbol division ( set partitioning ), there is already a significantly larger Euclidean distance between the transmission symbols and thus a significantly lower probability of errors in the decoding.
decoder
When decoding TCM signals, the methods known from convolutional codes such as the Viterbi algorithm are used. The decoding process can be shown in what is known as a trellis diagram, as shown on the right for a convolutional encoder with four states. A trellis diagram is the representation of a state transition diagram that is "scrolled" over the time axis. The transitions from one state to the next are assigned different probability values, as a result of which a single path in the trellis, which has the lowest cumulative error probability compared to all other paths, is usually clearly established over several states. The symbols assigned to this path are then regarded by the decoder as the symbols most likely to be transmitted.
| Number of states in the convolutional encoder |
Code gain of the TCM at 8-PSK (dB) |
|---|---|
| 4th | 3.0 |
| 8th | 3.6 |
| 16 | 4.1 |
| 32 | 4.6 |
| 64 | 5.0 |
| 128 | 5.2 |
| 256 | 5.8 |
| 1024 | 6.1 |
| 4096 | 6.4 |
| 131072 | 6.9 |
A special feature of the decoding of the TCM is that the uncoded, higher-value data bits result in parallel branches in the trellis diagram. (This fact, which occurs with TCM, is not shown in the illustration opposite.) These ambiguities can be avoided by using a higher-order convolutional encoder with several states.
In general, the length of the convolutional code has a significant influence on the code gain, the longer the convolutional code and the more internal states it comprises, the greater the code gain associated with it . Since the code gain with TCM also depends on the modulation used, the following table shows the code gain only for the 8-PSK modulation , with a bit error rate (BER) of 10 −6 and depending on the specific convolutional encoder. Similar values are obtained for other modulations, and detailed tables can be found in the literature below.
In general, it can be said that convolutional encoders with only four internal states do not offer any advantage in TCM, since a convolutional code with four states alone already has a code gain of 3.6 dB. From a convolutional code of eight states upwards, however, the TCM as a combination is always superior to the convolutional code alone in terms of code gain.
Extensions of real implementations
In real implementations of trellis-coded modulation, such as in the ITU-T standard V.34, other methods are used to improve the transmission properties. These extensions include the following:
- Use of non-linear convolutional encoders. These are convolutional encoders which have various types of feedback between the state memories. The selection of usable, non-linear convolutional encoders is much more difficult than the selection of linear, forward-based convolutional encoders and, in the absence of systematic construction methods, can usually only be achieved through extensive simulations. The reason for using appropriately selected, non-linear convolutional encoders is, among other things, that the decoder can record the correct reference phase position (rotation of the complex plane) directly without error estimation during decoding and thus longer synchronization times or ongoing resynchronization times during operation can be avoided.
- Use of higher-dimensional or multidimensional TCM. The symbols in the complex level are divided into individual sub-areas, so-called lattice , and a separate TCM is carried out within each of these sub-areas. Among other things, this can increase the spectral efficiency of the entire transmission system.
Naming
Trellis is the English name for a trellis - for example, wooden slats crossed at right angles on house walls as a support for climbing plants such as wild grape and ivy . The graphic representation of the trellis graph as a two-dimensional grid structure corresponds to the arrangement of the slats of the scaffolding. The crossing points of the bars correspond as nodes to the states, the bars as edges correspond to the state transitions during the trellis coding.
literature
- Todd K. Moon: Error correction coding. Mathematical methods and algorithms . John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-64800-0 .
Web links
- Trellis Coded Modulation Tutorial. (PDF; 521 kB; English)
Individual evidence
- ↑ Gottfried Ungerböck: Channel coding with multilevel / phase signals. In: IEEE Trans. Inform. Theory. Vol. IT-28, 1982, pp. 55-67.
- ↑ Gottfried Ungerböck: Trellis-coded modulation with redundant signal sets part I: introduction. In: IEEE Communications Magazine. Vol. 25-2, 1987, pp. 5-11.
- ^ Todd K. Moon: Error correction coding. Mathematical methods and algorithms . John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-64800-0 , pp. 535-580 .
- ^ Christian Siemers, Axel Sikora: Taschenbuch Signaltechnik. ISBN 3-446-21862-9 .