Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!mips!sgi!rpw3@rigden.wpd.sgi.com From: rpw3@rigden.wpd.sgi.com (Rob Warnock) Newsgroups: sci.electronics Subject: Re: Information, channel capacity, and feedback Message-ID: <81035@sgi.sgi.com> Date: 14 Jan 91 06:32:20 GMT References: <27992@cs.yale.edu> Sender: guest@sgi.sgi.com Reply-To: rpw3@sgi.com (Rob Warnock) Distribution: sci.electronics Organization: Silicon Graphics, Inc., Mountain View, CA Lines: 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