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