Trellis modulation

Trellis diagram

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, ...]. 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 had published a standard, V.32,[2] 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).

Trellis modulation was an important technology in the early years of the global Internet. Dial-up Internet access began to explode in early 1992 and the last restrictions on commercial traffic were lifted in 1995, this immediately fueling the dot-com bubble of 1997–2000. Modem access dominated for a ten-year period from roughly 1995 to 2005, including the entirety of the dot-com bubble.

In statistical terms, in 2000 there were just under 150 million dial-up subscriptions in the 34 OECD countries and fewer than 20 million broadband subscriptions. By 2004, broadband and dial-up were roughly equal at 130 million each. In 2010, in the OECD countries, over 90% of the Internet access subscriptions used broadband and dial-up subscriptions had declined to fewer than 30 million.

While the modem performance boost due to trellis modulation was of relatively minor significance for browsing simple web pages composed almost entirely of static text (of which link farms were once a prominent example), it was game-changer for everything else, in particular, the online distribution of bulky software packages and patches, and early experiments in Internet video such as RealPlayer, where a 56k-class modem could reasonably deliver an almost-smooth 320×200 video under optimal conditions (the effective video compression rate being also limited by the compute power of the era).

Advanced modulation also initiated the beginning of a rural/urban Internet class divide: cities tend to have shorter POTS loops, which better support higher operating rates. For many rural customers, a putatively high-speed modem would in practice degrade to a lower operating rate, approximating older technology. In the prevailing gold-rush mentality, web site design tended to cater to the well-heeled urban base by larding in ever more complex page design (often centered around online advertising business models and the race for eyeballs), until popular sites with even the most basic functionality—functionality which had been perfectly well served by basic text—became bandwidth profligate. For this reason, it was not uncommon following the advent of advanced modulation for rural users—users whose bandwidth was effectively capped by their physical copper loop rather than the modulation technology employed—to experience an actual decline in Internet usability.

• Modems, for the history of various encoding modulations from 0.3 to 56 kbit/s
• Trellis diagram, in the article about convolutional codes

In the December 8, 1991 edition of the Dilbert comic strip, Scott Adams refers to the mere mentioning of trellis code modulation as a means for stopping a casual conversation cold.[3]

In the 2017 track "We Do It Different on the West Coast," from the album Goths, John Darnielle of The Mountain Goats sings, "Trellis modulation for the children," in reference to dialing into Goth subculture-oriented BBSes in the pre-World Wide Web era.[4]

• 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.

• TCM tutorial
• Oral-History:Gottfried Ungerboeck, Engineering and Technology History Wiki (IEEE Global History Network)