Noisy-channel coding theorem: Difference between revisions

Revision as of 09:33, 26 July 2006

Revision as of 12:35, 28 August 2006

Line 46:

{{section-stub}}

As with several other major results in information theory, the proof of the noisy channel coding theorem includes an achievability result and a matching converse result. These two components serve to bound, in this case, the set of possible rates at which one can communicate over a noisy channel, and matching serves to show that these bounds are tight bounds.

The following outlines are only one set of many different styles available for study in information theory texts.

Line 75 ⟶ 74:

#The receiver receives a sequence according to <math>P(y^n|x^n(w))= \prod_{i = 1}^np(y_i|x_i(w))</math>

#Sending these codewords across the channel, we receive <math>Y_1^n</math>, and decode to some source sequence if there exists exactly 1 codeword that is jointly typical with Y. If there are no jointly typical codewords, or if there are more than one, an error is declared. An error also occurs if a decoded codeword doesn't match the original codeword. This is called ''typical set decoding''.

The probability of error of this scheme is divided into two parts:

Line 124 ⟶ 122:

C=\lim\;\inf\;\;\frac{1}{n}\sum_{i=1}^n C_i

</math>

where <math>C_i</math> is the capacity of the i<i>''th</i>'' channel.

=== Outline of the proof===

The proof runs through in almost the same way as that of channel coding theorem. Achievability follows from random coding with each symbol chosen randomly from the capacity achieving distribution for that particular channel. Typicality arguments use the definition of typical sets for non-stationary sources defined in [[Asymptotic Equipartition Property]].

Line 133 ⟶ 131:

*C. E. Shannon, The Mathematical Theory of Information. Urbana, IL:University of Illinois Press, 1949 (reprinted 1998).

* David J. C. MacKay. ''[http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms]'' Cambridge: Cambridge University Press, 2003. ISBN 05216429810-521-64298-1

* Thomas Cover, Joy Thomas, Elements of Information Theory. New York, NY:John Wiley & Sons, Inc., 1991. ISBN 04710625960-471-06259-6

==See also==