Converse of Shannon's Capacity Theorem
The converse of the capacity theorem essentially states that is the best rate one can achieve over a binary symmetric channel. Formally the theorem states:
Theorem 2 If then the following is true for every encoding and decoding function : and : respectively: " src="http://upload.wikimedia.org/math/b/0/8/b08302ec38b2c181e928d905478f5fe1.png" /> .
For a detailed proof of this theorem, the reader is asked to refer to the bibliography. The intuition behind the proof is however showing the number of errors to grow rapidly as the rate grows beyond the channel capacity. The idea is the sender generates messages of dimension, while the channel introduces transmission errors. When the capacity of the channel is, the number of errors is typically for a code of block length . The maximum number of messages is . The output of the channel on the other hand has possible values. If there is any confusion between any two messages, it is likely that . Hence we would have, a case we would like to avoid to keep the decoding error probability exponentially small.
Read more about this topic: Binary Symmetric Channel
Famous quotes containing the words converse of, converse, capacity and/or theorem:
“There is a plain distinction to be made betwixt pleasure and happiness. For tho’ there can be no happiness without pleasure—yet the converse of the proposition will not hold true.—We are so made, that from the common gratifications of our appetites, and the impressions of a thousand objects, we snatch the one, like a transient gleam, without being suffered to taste the other.”
—Laurence Sterne (1713–1768)
“Were you to converse with a king, you ought to be as easy and unembarrassed as with your own valet-de chambre; but yet every look, word, and action should imply the utmost respect.... You must wait till you are spoken to; you must receive, not give, the subject of conversation, and you must even take care that the given subject of such conversation do not lead you into any impropriety.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“There seems almost a general wish of descrying the capacity and undervaluing the labour of the novelist, and of slighting the performances which have only genius, wit, and taste to recommend them.”
—Jane Austen (1775–1817)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)