Editing Binary symmetric channel (section)

== Converse of Shannon's capacity theorem ==

The converse of the capacity theorem essentially states that <math>1 - H(p)</math> is the best rate one can achieve over a binary symmetric channel. Formally the theorem states:

{{math_theorem|If <math>k</math> <math>\geq</math> <math>\lceil</math> <math>(1 - H(p + \epsilon)n)</math> <math>\rceil</math> then the following is true for every [[Code|encoding]] and [[Code|decoding]] function <math>E</math>: <math>\{0,1\}^k</math> <math>\rightarrow</math> <math>\{0,1\}^n</math> and <math>D</math>: <math>\{0,1\}^{n}</math> <math>\rightarrow</math> <math>\{0,1\}^{k}</math> respectively: <math>\Pr_{e \in \text{BSC}_p}</math>[<math>D(E(m) + e)</math> <math>\neq</math> <math>m]</math> <math>\geq</math> <math>\frac{1}{2}</math>.}}

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 <math>k</math>, while the channel <math>\text{BSC}_p</math> introduces transmission errors. When the capacity of the channel is <math>H(p)</math>, the number of errors is typically <math>2^{H(p + \epsilon)n}</math> for a code of block length <math>n</math>. The maximum number of messages is <math>2^{k}</math>. The output of the channel on the other hand has <math>2^{n}</math> possible values. If there is any confusion between any two messages, it is likely that <math>2^{k}2^{H(p + \epsilon)n} \ge 2^{n}</math>. Hence we would have <math>k \geq \lceil (1 - H(p + \epsilon)n) \rceil</math>, a case we would like to avoid to keep the decoding error probability exponentially small.