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, capacity and/or theorem:
““You are old, Father William,” the young man cried,
“And life must be hastening away;
You are cheerful, and love to converse upon death:
Now tell me the reason, I pray.”
“I am cheerful, young man,” Father William replied;
“Let the cause thy attention engage;
In the days of my youth I remembered my God,
And He hath not forgotten my age.””
—Robert Southey (1774–1843)
“Mankind’s common instinct for reality ... has always held the world to be essentially a theatre for heroism. In heroism, we feel, life’s supreme mystery is hidden. We tolerate no one who has no capacity whatever for it in any direction. On the other hand, no matter what a man’s frailties otherwise may be, if he be willing to risk death, and still more if he suffer it heroically, in the service he has chosen, the fact consecrates him forever.”
—William James (1842–1910)
“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)