مرکز منطقه ای اطلاع رساني علوم و فناوري - Asymptotic performance and complexity of a coding scheme for memoryless channels

Abstract :

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 $C$ at any rate $R < C$ with a probability of error of less than $2^{-E(R)\\nu}, E(R) > 0$ , per block of a length approximately proportional to $\\nu^{2}$ and with a computational decoding complexity per digit which is asymptotically proportional to $\\nu^{\\alpha }$ when $\\nu$ is large, $\\nu^{\\alpha }$ being finite for $R < C$ . $(\\alpha \\rightarrow mbox{as} R \\rightarrow C, \\alpha \\rightarrow 2 mbox{as} R \\rightarrow 0)$ .