[sci.electronics] Information, channel capacity, and feedback

zador-anthony@cs.yale.edu (Tony Zador) (01/10/91)

Suppose you have a source A and a destination B to which you are trying to
communicate.  Everything is continuous.
You have X units of channel capacity at your disposal (perhaps
they correspond to n thin filaments of cable, sold in small units of X/n).
If you string your channel from A to B, then according to Shannon
you can transmit X but no more information per unit time with
arbitrarily small error.  

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? Does Shannon cover this?  Is this even a well-posed 
question?

Thanks for any help,
Tony Zador
zador@cs.yale.edu

rpw3@rigden.wpd.sgi.com (Rob Warnock) (01/14/91)

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

robert@wiliki.eng.hawaii.edu (Robert Morelos-Zaragoza) (01/15/91)

The capacity of a Gaussian channel with feedback can at most double,
as shown by Professor Thomas Cover and his students at Stanford
University. But the fact that feedback does not improve the capacity
much remains to be shown matematically.

You may write to Prof. Cover to find out the status of this
research problem. His address is

Prof. Thomas M. Cover
Durand Bldg., Rm. 121
Department of Electrical Engineering
Stanford University
Stanford, CA 94305


By the way, this is an excellent question. It is not covered by almost
all communications or coding theory books, which only discuss technical
methods of using feedback. So it is worthless to look into the books
for the answer. This is a question whose answer is a good research problem,
for a Ph.D. dissertation for instance.

Aloha,

Robert Morelos-Zaragoza
Department of Electrical Engineering
University of Hawaii
2540 Dole Street #483
Honolulu, HI 96822

morelos@uhunix2.uhcc.Hawaii.Edu (Robert Morelos) (01/16/91)

I should add to my last posting:

Shannon did prove that the capacity of a Gaussian channel with feedback and
without feedback is the SAME, iof the noise is white, i.e., its power spectral
density is constant over the bandwith. It remains to show that the same is
true or that capacity does not increase much when feedback is introduced, and
for other power spectral densities. This is the conjecture made by Prof. Cover
at Stanford.


Aloha,

Robert Morelos-Zaragoza
Department of Electrical Engineering
University of Hawaii
2540 Dole Street #483
Honolulu, Hawaii 96822