epsilon@wet.UUCP (Eric P. Scott) (07/29/90)
What does it do? Do all V.32 modems support it? If not, how serious is not having it? Responses to the newsgroup/list please. -=EPS=-
tnixon@hsfmsh.UUCP (Toby Nixon) (07/30/90)
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 with the user data, calculated based on the preceding
data, so the that receiving modem can "predict" what at least one of
the transmitted bits will be and therefore have a better chance of
properly deciding what the received "symbol" actually represents
(this is greatly simplified). When trellis coding is enabled in
V.32 modems, one can conceive of them as operating at 12,000 bits
per second, with one of the bits in each "symbol" (2400 symbols are
transmitted per second) being a "coding" bit (so the actual user
data throughput is 9600 bit/s). The number of points in the
constellation is expanded from 16 to 32 as a result, but at the same
time the ability to "anticipate" what the coding bit "ought" to be
allows the modem to make a better guess at the subsequent symbols.
When V.32 modems were first shipped (it has been a standard size
1984), some did not have trellis coding (in fact, there are some
that only support 4800 bit/s). At the present time, however,
I would guess that all V.32 modems support trellis coding. It is so
ingrained, as a matter of fact, that the new proposed V.32bis
standard (which adds 7200, 12000, and 14400 bit/s to the V.32 speeds
of 4800 and 9600) mandates trellis coding at all speeds except 4800.
The main problem with operating without trellis coding is that
you'll experience more line noise. Trellis coding allows the modem
to tolerate about 3.5 dB additional signal-to-noise ratio than a
modem without trellis coding, at the same bit error rate. That can
be quite significant. On some alternative long-distance networks
that use tandem ADPCM links (adaptive differential pulse code
modulation is a technique for squeezing twice as many calls onto a
digital trunk) you'll find that a non-trellis-coded V.32 modem
probably won't work AT ALL at 9600, but would be limited to 4800.
Operation on ADPCM links (which are common on intercontinental
circuits) is one of the reasons the Group 3 Fax standards committees
have been anxious to adopt a standard (the proposed V.17 standard)
which will add trellis coding to Group 3 fax at 7200 and 9600 (the
V.29 standard currently used at those speeds doesn't have trellis
coding and won't work well on tandem ADPCM links).
Anyway, that's a lot of words to basically advise you that if I were
you, I wouldn't even consider buying a V.32 modem without trellis
coding! It would interwork with all other V.32 modems, but you'd
pay a real performance penalty.
-- Toby
-----------------------------------------------------------------------------
Toby Nixon, Principal Engineer Fax: +1-404-441-1213 Telex: 6502670805
Hayes Microcomputer Products Inc. Voice: +1-404-449-8791 CIS: 70271,404
Norcross, Georgia, USA BBS: +1-404-446-6336 MCI: TNIXON
Telemail: T.NIXON/HAYES AT&T: !tnixon
UUCP: ...!uunet!hayes!tnixon Internet: hayes!tnixon@uunet.uu.net
MHS: C=US / AD=ATTMAIL / PN=TOBY_L_NIXON / DD=TNIXON
-----------------------------------------------------------------------------rpw3@rigden.wpd.sgi.com (Rob Warnock) (08/01/90)
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