codeword. In order for the decoded codeword not to be equal to the message , one of the following events must occur: does not lie within the Hamming ball of radius centered at . This condition is mainly used to make the calculations easier. There is another message such that . In other words, the errors due to noise take the transmitted codeword closer to another encoded message. We can apply the Chernoff bound to ensure the non occurrence of the first event; we get: This is exponentially small for large (recall that is fixed). For the second event, we note that the probability that is where is the Hamming ball of radius centered at vector and is its volume. Using approximation to estimate the number of codewords in the Hamming ball, we have . Hence the above probability amounts to . Now using the union bound, we can upper bound the existence of such an by which is , as desired by the choice of . |} {| class="toccolours collapsible collapsed" width="80%" style="text-align:left" !Continuation of proof (detailed) |- |From the above analysis, we calculate the probability of the event that the decoded codeword plus the channel noise is not the same as the original message sent. We shall introduce some symbols here. Let denote the probability of receiving codeword given that codeword was sent. Let denote We get the last inequality by our analysis using the Chernoff bound above. Now taking expectation on both sides we have, by appropriately choosing the value of . Since the above bound holds for each message, we have Now we can change the order of summation in the expectation with respect to the message and the choice of the encoding function . Hence: Hence in conclusion, by probabilistic method, we have some encoding function and a corresponding decoding function such that At this point, the proof works for a fixed message . But we need to make sure that the above bound holds for all the messages simultaneously. For that, let us sort the messages by their decoding error probabilities. Now by applying Markov's inequality, we can show the decoding error probability for the first messages to be at most . Thus in order to confirm that the above bound to hold for every message , we could just trim off the last messages from the sorted order. This essentially gives us another