. We conclude that the channel capacity for our binary symmetric channel is . |} Noisy-channel coding theorem Shannon's noisy-channel coding theorem gives a result about the rate of information that can be transmitted through a communication channel with arbitrarily low error. We study the particular case of . The noise that characterizes is a random variable consisting of n independent random bits (n is defined below) where each random bit is a with probability and a with probability . We indicate this by writing "". What this theorem actually implies is, a message when picked from , encoded with a random encoding function , and sent across a noisy , there is a very high probability of recovering the original message by decoding, if or in effect the rate of the channel is bounded by the quantity stated in the theorem. The decoding error probability is exponentially small. Proof The theorem can be proved directly with a probabilistic method. Consider an encoding function that is selected at random. This means that for each message , the value is selected at random (with equal probabilities). For a given encoding function , the decoding function is specified as follows: given any received codeword , we find the message such that the Hamming distance is as small as possible (with ties broken arbitrarily). ( is called a maximum likelihood decoding function.) The proof continues by showing that at least one such choice satisfies the conclusion of theorem, by integration over the probabilities. Suppose and are fixed. First we show that, for a fixed and chosen randomly, the probability of failure over noise is exponentially small in n. At this point, the proof works for a fixed message . Next we extend this result to work for all messages . We achieve this by eliminating half of the codewords from the code with the argument that the proof for the decoding error probability holds for at least half of the codewords. The latter method is called expurgation. This gives the total process the name random coding with expurgation. {| class="toccolours collapsible collapsed" width="80%" style="text-align:left" !Continuation of proof (sketch) |- |Fix and . Given a fixed message , we need to estimate the expected value of the probability of the received codeword along with the noise does not give back on decoding. That is to say, we need to estimate: Let be the received