up to fraction of worst case errors and runs in time. The inner code is a code of block length , dimension , and a rate of . Additionally, we have a decoding algorithm for with a decoding error probability of at most over and runs in time. For the outer code , a Reed-Solomon code would have been the first code to have come in mind. However, we would see that the construction of such a code cannot be done in polynomial time. This is why a binary linear code is used for . For the inner code we find a linear code by exhaustively searching from the linear code of block length and dimension , whose rate meets the capacity of , by the noisy-channel coding theorem. The rate which almost meets the capacity. We further note that the encoding and decoding of can be done in polynomial time with respect to . As a matter of fact, encoding takes time . Further, the decoding algorithm described takes time as long as ; and . Decoding error probability A natural decoding algorithm for is to: Assume Execute on Note that each block of code for is considered a symbol for . Now since the probability of error at any index for is at most and the errors in are independent, the expected number of errors for is at most by linearity of expectation. Now applying Chernoff bound, we have bound error probability of more than errors occurring to be . Since the outer code can correct at most errors, this is the decoding error probability of . This when expressed in asymptotic terms, gives us an error probability of . Thus the achieved decoding error probability of is exponentially small as the noisy-channel coding theorem. We have given a general technique to construct . For more detailed descriptions on and please read the following references. Recently a few other codes have also been constructed for achieving the capacities. LDPC codes have been considered for this purpose for their faster decoding time. Applications The binary symmetric channel can model a disk drive used for memory storage: the channel input represents a bit being written to the disk and the output corresponds to the bit later being read. Error could arise from the magnetization flipping, background noise or the writing head making an error. Other objects which the binary symmetric