🚀 go-pugleaf

In article <27992@cs.yale.edu> zador-anthony@cs.yale.edu (Tony Zador) writes:
+---------------
| Suppose you have a source A and a destination B to which you are trying to
| communicate... You have X units of channel capacity at your disposal...
| ...then according to Shannon you can transmit X but no more information
| per unit time with arbitrarily small error.  
+---------------

Close. The "channel capacity" is the amount of information that can move from
A to B over a channel of capacity C (or as you called it, X). The capacity of
a channel is a function of both its bandwidth and its error rate, or in the
continuous case, the noise power, namely: C (bits/s) = W * log2(1 + S/(N0*W))
[W = double-sided bandwidth, S = signal power, N0 = noise power in watts/Hz].

Note that for all real channels the capacity is strictly less than the Nyquist
limit of 2 baud/Hz because all real channels have noise. But simply knowing
the theoretical capacity doesn't help you separate the signal from the noise.

What Shannon showed was that for any channel of capacity C, there exist error-
correcting codes that will allow transmission at speeds "as close as you like"
to C, with error rates "as small as you like". That is, you pick a transmission
rate R (R < C), and an allowable error rate E (E > 0), and there *exists* a
code which will allow transmission at rate R or less with error rate E or less.

What Shannon's thorem *doesn't* do is:

1. Tell you how to find the code. It's an "existence" proof, not a
   "constructive" proof.

2. Put a limit on the *delay* encoding/decoding will add to the transmission.
   Codes that work at low error rates very close to the channel capacity also
   involve long "word lengths" (block lengths), with concomitant delays.

3. Put a bound on the amount of computation that might be required to
   execute the coding/decoding algorithms. Some codes are quite complex.

Nevertheless, current block and convolutional codes (names like "BCH" or
"Reed-Solomon" for block codes, "Viterbi" or "sequential" for convolutional
codes) have proved quite useful. Ask any NASA telemetry engineer or any
manufacturer of CD players. ;-}  They can actually get very close (for wide
bandwidths) to the absolute limit of Eb/N0 >= -1.6 dB [Eb = joules/bit =
signal power S / data rate R, N0 = noise watts/Hz, as above].

+---------------
| What if you allow feedback?  That is, what if you have a channel of
| Y capacity from A to B and X-Y units from B to A?  Does this win
| you anything?
+---------------

Depends. The forward channel capacity is not improved one bit (and may be
lessened if you have to steal time or bandwidth for the reverse channel).
What it *maybe* wins you is less computation in your error-correction process,
since you can use a simple CRC in the forward path and "ACKs" and "NACKs"
in the reverse channel instead of more complicated block codes. But the raw
channel error rate, channel delay, and buffer sizes become significant issues.

There are tables/graphs (which I don't have handy) which show you the
tradeoffs of the "forward error-correcting" versus "go-back-N" methods.
On channels with high error rates or very high delay (deep-space work),
the FEC methods are generally better; on low-delay very "clean" channels
(Ethernet), ARQ or "go-back-N" is better. [I have bundled in "selective
retransmission" with "go-back-N". The details don't matter much at this
level of discussion.]

There are many intermediate cases (e.g., satellites) where a little bit
of FEC coding can help to "bunch up" errors, which are then corrected via
"go-back-N".

+---------------
| Does Shannon cover this?
+---------------

Yes, though his work was more oriented towards the FEC case. The main point
for you to remember is that a reverse channel doesn't improve the forward
channel's capacity, though it may assist the coding computations.

+---------------
| Is this even a well-posed question?
+---------------

Yes (though a beginner's question). See any good book on communications
theory or coding theory for more details.


-Rob

-----
Rob Warnock, MS-9U/515		rpw3@sgi.com		rpw3@pei.com
Silicon Graphics, Inc.		(415)335-1673		Protocol Engines, Inc.
2011 N. Shoreline Blvd.
Mountain View, CA  94039-7311