encoding function with a corresponding decoding function with a decoding error probability of at most with the same rate. Taking to be equal to we bound the decoding error probability to . This expurgation process completes the proof. |} 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: 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. Codes Very recently, a lot of work has been done and is also being done to design explicit error-correcting codes to achieve the capacities of several standard communication channels. The motivation behind designing such codes is to relate the rate of the code with the fraction of errors which it can correct. The approach behind the design of codes which meet the channel capacities of or the binary erasure channel have been to correct a lesser number of errors with a high probability, and to achieve the highest possible rate. Shannon's theorem gives us the best rate which could be achieved over a , but it does not give us an idea of any explicit codes which achieve that rate. In fact such codes are typically constructed to correct only a small fraction of errors with a high probability, but achieve a very good rate. The first such code was due to George D. Forney in 1966. The code is a concatenated code by concatenating two different kinds of codes. Forney's code Forney constructed a concatenated code to achieve the capacity of the noisy-channel coding theorem for . In his code, The outer code is a code of block length and rate over the field , and . Additionally, we have a decoding algorithm for which can correct