I. Introduction
THE invention of turbo codes in 1993 [6], and the explosion of research that followed, has revolutionized every aspect of channel coding. Turbo codes appear to offer nothing less than a solution to the challenge issued by Shannon in 1948 [33]: to devise practical methods of communicating reliably at rates near channel capacity. And while there has been a good deal of excellent theoretical work on turbo codes, it seems fair to say that practice still leads theory by a considerable margin. In particular, there has been little previous Shannon-theoretic work on turbo codes. By “Shannon-theoretic” we mean a study of the average performance of the codes in the turbo-code ensemble under maximum-likelihood decoding (MLD). Of course, there is little possibility that MLD of turbo codes can be implemented practically, but since the turbo decoding algorithm seems to be, in most cases, a close approximation to MLD, it is important to know the MLD potential for this class of codes. In any case, this paper is devoted to a Shannon-theoretic study of turbo codes. In particular, it may be viewed as an elaboration of the following remark, which was made in [24]:
“The presence [in turbo-codes] of the pseudorandom interleavers between the component codes ensures that the resulting overall code behaves very much like a long random code, and by Shannon's theorems, a long random code is likely to be 'good' .”