Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ames!sgi!rpw3@rigden.wpd.sgi.com From: rpw3@rigden.wpd.sgi.com (Rob Warnock) Newsgroups: comp.dcom.modems Subject: Re: Want info on Trellis encoding for V.32 Message-ID: <65806@sgi.sgi.com> Date: 1 Aug 90 05:40:35 GMT References: <3685@hsfmsh.UUCP> Sender: rpw3@rigden.wpd.sgi.com Reply-To: rpw3@sgi.com (Rob Warnock) Organization: Silicon Graphics, Inc., Mountain View, CA Lines: 80 In article <3685@hsfmsh.UUCP> tnixon@hsfmsh.UUCP (Toby Nixon) writes: +--------------- | In article <1397@wet.UUCP>, Eric P. Scott writes: | - What does it do? Do all V.32 modems support it? If not, how | - serious is not having it? | Trellis coding is a technique whereby additional bits are transmitted... | [...brief overview of trellis coding...] +--------------- By the way, if you go look in the algebraic coding theory or error-correcting coding theory literature, you may not be able to find the term "trellis coding". Instead, look for "convolutional coding", which is the much more traditional name. The name "trellis coding" seems to have arisen from the pictures -- or "trellis diagrams", for their resemblence to the shape of a garden trellis -- people drew to illustrate the internal states of one particular kind of decoder for convolutional codes: the "Viterbi algorithm". A "trellis" shape results when you graph the states and state transitions (due to input data) of a Viterbi decoder as a function of time. After a while (very quickly, really), the state transitions stop expanding exponentially and start folding back on themselves, giving the "trellis" pattern. For some reason, in the area of low-speed modems the term "trellis coding" became popular at a time when few low-speed modem designers knew anything about error-correcting codes and weren't really familiar with the literature. I keep saying "low-speed modems" because with really *high*-speed modems used in satellite work (1 to 100 Mbit/s), the term has always been "convolutional coding". And if we really want to look at jargon, since one of the principle character- istics of a convolutional code is the ratio of actual data bits to data-plus- error-correcting bits (always less than one), and these ratios tend to be small-integer fractions, you will often hear satellite people refer to a "rate 2/3 code" or a "rate 7/8 code", meaning a convolutional code of that rate. So when Toby Nixon said that the "V.32 trellis code" actually transmits 12000 bits/sec for a 9600 b/s RS-232 interface, he was *really* talking about a "rate 4/5 code". ;-} ;-} In addition to Viterbi ("trellis") decoders, another important family of techniques is the "sequential decoders", which pre-dated [1961] the Viterbi method [1967]. Well-known sequential decoding algorithms include the "stack" or "ZJ" algorithm and the "Fano algorithm". When Viterbi published his algorithm, Viterbi decoders gained popularity because they required much less storage, and a constant (though quite high) computational rate. Sequential decoders use a variable-length-path tree searching technique (so instead of a "trellis" you'll see diagrams of a "scraggly bush"), compared to the Viterbi decoders ("all paths in parallel"). While sequential decoders may be able to correct a longer isolated error burst than the Viterbi, their computational load is highly variable, and they can "run out of time" (more correctly, out of buffer space) if they get several error bursts in a row. But by 1980 or so, sequential decoders were regaining some popularity, due to the ready availability of fast microprocessors and cheap large RAMs. These days, the choice of which decoding technique to use will be based on other considerations. For example, while sequential decoding can usually give a dB or so more coding gain over Viterbi when using a "hard-decision" quantizer (A/D converter in the receiver), the Viterbi can gain that back (and a little more) if a "soft-decision" quantizer is available (one which digitizes to several bits more resolution than are necessary just to separate the received symbols). Finally, there is "majority-logic" or "threshold" decoding, which is not as good as either Viterbi or sequential decoders, but whose implementation is quite cheap. I have no idea which of the above (if any) the V.32 people are actually using, by the way... ;-} ;-} -Rob [Reference: Lin & Costello, "Error Control Coding" (P-H 1983), chapters 11-13.] ----- Rob Warnock, MS-9U/510 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311