Asymptotic performance and complexity of a coding scheme for memoryless channels

The purpose of this paper is to show that decoding complexity need not grow exponentially with the code block length at rates close to channel capacity and also to show the expediency of the approach of imbedding codes in each other. It is demonstrated that it is possible to communicate over a memoryless channel of capacity at any rate with a probability of error of less than , per block of a length approximately proportional to and with a computational decoding complexity per digit which is asymptotically proportional to when is large, being finite for . .