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:
“The American doctrinaire is the converse of the American demagogue, and, in this way, is scarcely less injurious to the public. The first deals in poetry, the last in cant. He is as much a visionary on one side, as the extreme theoretical democrat is a visionary on the other.”
—James Fenimore Cooper (1789–1851)
“The Anglo-American can indeed cut down, and grub up all this waving forest, and make a stump speech, and vote for Buchanan on its ruins, but he cannot converse with the spirit of the tree he fells, he cannot read the poetry and mythology which retire as he advances. He ignorantly erases mythological tablets in order to print his handbills and town-meeting warrants on them.”
—Henry David Thoreau (1817–1862)
“If your child is going to develop a healthy personality with the capacity to remain intact and grow, she must learn how to test reality, regulate her impulses, stabilize her moods, integrate her feelings and actions, focus her concentration and plan.”
—Stanley I. Greenspan (20th century)
“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)