ASYMPTOTIC CAPABILITIES OF CONCATENATED CODES AND ITERATED CODES

As the codes that can prove Shannon's channel coding theorem by constr ucting the code, only two classes of codes are known, i.e., the concat enated code proposed by Forney and the iterated code proposed by Elias . In spite of this fact, those two codes have not been compared by the common evaluation measure. The former is evaluated from the standpoin t of information theory and coding theory in terms of the average powe r from the viewpoint of the reliability function and the asymptotic di stance ratio of the constructed code. For the latter, it is shown unde r a restricted condition that the decoding error rate per binary symbo l converges to zero, only for the constructed code. With this as backg round, this paper compares the concatenated code and the iterated code by the common evaluation measure, considering the computational compl exity required for the decoding. It is shown that the concatenated cod e is better than the iterated code. It is shown also that those two ki nds of codes can be realized with the decoding complexity of polynomia l order of the code length. Under the foregoing condition, it is shown that it is impossible to construct an iterated code with the nonzero asymptotic distance ratio. For the Justesen code, which is a class of the constructive concatenated codes, and the Elias iterated code, whic h is a class of the iterated codes, the upper bound for the decoding e rror probability is separated into a function of code length and a fun ction of code rate. The code length is represented as a function of th e computational complexity required for the decoding, and the upper bo unds of the decoding error probabilities of the two codes are compared for the same computational complexity and the code rate. It is shown as a result that the upper bound for the decoding error probability of the Justesen code is asymptotically better than that of the Elias ite rated code.