Trellis coded modulation
   HOME

TheInfoList



OR:

In
telecommunication Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...
, trellis modulation (also known as trellis coded modulation, or simply TCM) is a modulation scheme that transmits information with high efficiency over band-limited channels such as
telephone line A telephone line or telephone circuit (or just line or circuit industrywide) is a single-user circuit on a telephone communication system. It is designed to reproduce speech of a quality that is understandable. It is the physical wire or ot ...
s. Gottfried Ungerboeck invented trellis modulation while working for IBM in the 1970s, and first described it in a conference paper in 1976. It went largely unnoticed, however, until he published a new, detailed exposition in 1982 that achieved sudden and widespread recognition. In the late 1980s,
modem A modulator-demodulator or modem is a computer hardware device that converts data from a digital format into a format suitable for an analog transmission medium such as telephone or radio. A modem transmits data by Modulation#Digital modulati ...
s operating over
plain old telephone service Plain old telephone service (POTS), or plain ordinary telephone system, is a retronym for voice-grade telephone service employing analog signal transmission over copper loops. POTS was the standard service offering from telephone companies from 1 ...
(''POTS'') typically achieved 9.6 
kbit/s In telecommunications, data-transfer rate is the average number of bits (bitrate), characters or symbols (baudrate), or data blocks per unit time passing through a communication link in a data-transmission system. Common data rate units are multi ...
by employing four bits per symbol
QAM Quadrature amplitude modulation (QAM) is the name of a family of digital modulation methods and a related family of analog modulation methods widely used in modern telecommunications to transmit information. It conveys two analog message signa ...
modulation at 2,400 baud (symbols/second). This bit rate ceiling existed despite the best efforts of many researchers, and some engineers predicted that without a major upgrade of the public phone infrastructure, the maximum achievable rate for a POTS modem might be 14 kbit/s for two-way communication (3,429 baud × 4 bits/symbol, using QAM). 14 kbit/s is only 40% of the theoretical maximum bit rate predicted by
Shannon's theorem In information theory, the noisy-channel coding theorem (sometimes Shannon's theorem or Shannon's limit), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (dig ...
for POTS lines (approximately 35 kbit/s). Ungerboeck's theories demonstrated that there was considerable untapped potential in the system, and by applying the concept to new modem standards, speed rapidly increased to 14.4, 28.8 and ultimately 33.6 kbit/s.


A new modulation method

The name ''trellis'' derives from the fact that a state diagram of the technique closely resembles a trellis lattice. The scheme is basically a
convolutional code In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of t ...
of rates (''r'', ''r''+1). Ungerboeck's unique contribution is to apply the parity check for each symbol, instead of the older technique of applying it to the bit stream then modulating the bits. He called the key idea ''mapping by set partitions''. This idea groups symbols in a tree-like structure, then separates them into two limbs of equal size. At each "limb" of the tree, the symbols are further apart. Though hard to visualize in multiple dimensions, a simple one-dimension example illustrates the basic procedure. Suppose the symbols are located at , 2, 3, 4, ... Place all odd symbols in one group, and all even symbols in the second group. (This is not quite accurate, because Ungerboeck was looking at the two dimensional problem, but the principle is the same.) Take every other symbol in each group and repeat the procedure for each tree limb. He next described a method of assigning the encoded bit stream onto the symbols in a very systematic procedure. Once this procedure was fully described, his next step was to program the algorithms into a computer and let the computer search for the best codes. The results were astonishing. Even the most simple code (4 state) produced error rates nearly one one-thousandth of an equivalent uncoded system. For two years Ungerboeck kept these results private and only conveyed them to close colleagues. Finally, in 1982, Ungerboeck published a paper describing the principles of trellis modulation. A flurry of research activity ensued, and by 1984 the
International Telecommunication Union The International Telecommunication Union is a specialized agency of the United Nations responsible for many matters related to information and communication technologies. It was established on 17 May 1865 as the International Telegraph Unio ...
had published a standard, V.32,{{Cite web, url=https://www.itu.int/ITU-T/recommendations/rec.aspx?rec=2752&lang=en, title = ITU-T Recommendation database for the first trellis-modulated modem at 9.6 kilobit/s (2,400 baud and 4 bits per symbol). Over the next several years further advances in encoding, plus a corresponding symbol rate increase from 2,400 to 3,429 baud, allowed modems to achieve rates up to 34.3 kilobits/s (limited by maximum power regulations to 33.8 kilobits/s). Today, the most common trellis-modulated V.34 modems use a 4-dimensional set partition—achieved by treating two two-dimensional symbols as a single lattice. This set uses 8, 16, or 32 state convolutional codes to squeeze the equivalent of 6 to 10 bits into each symbol the modem sends (for example, 2,400 baud × 8 bits/symbol = 19,200 bit/s).


Relevant papers

* G. Ungerboeck, "Channel coding with multilevel/phase signals," ''IEEE Trans. Inf. Theory'', vol. IT-28, pp. 55–67, 1982. * G. Ungerboeck, "Trellis-coded modulation with redundant signal sets part I: introduction," ''IEEE Communications Magazine'', vol. 25-2, pp. 5–11, 1987.


See also

*
Modems A modulator-demodulator or modem is a computer hardware device that converts data from a digital format into a format suitable for an analog transmission medium such as telephone or radio. A modem transmits data by modulating one or more ca ...
, for the history of various encoding modulations from 0.3 to 56 kbit/s * Trellis diagram, in the article about
convolutional code In telecommunication, a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of t ...
s


References


External links


TCM tutorial

Oral-History:Gottfried Ungerboeck
Engineering and Technology History Wiki (IEEE Global History Network) Telecommunication theory Telecommunications engineering