Trellis modulation

In telecommunication, 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 lines. 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, modems operating over plain old telephone service (POTS) typically achieved 9.6 kbit/s by employing four bits per symbol QAM 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 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. 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 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 [1, 2, 3, 4, .