Asymptotic performance and complexity of a coding scheme for memoryless channels
J. Ziv · IEEE Transactions on Information Theory · 1967
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 capacityCat any rateR 0, per block of a length approximately proportional to u^{2}and with a computational decoding complexity per digit which is asymptotically proportional to u^{\alpha}when uis large, u^{\alpha}being finite forR < C.(\alpha \rightarrow \mbox{as} R \rightarrow C, \alpha \rightarrow 2 \mbox{as} R \rightarrow 0).