Asymptotic capabilities of concatenated codes and iterated codes

Abstract As the codes that can prove Shannon's channel coding theorem by constructing the code, only two classes of codes are known, i.e., the concatenated 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 standpoint of information theory and coding theory in terms of the average power from the viewpoint of the reliability function and the asymptotic distance ratio of the constructed code. For the latter, it is shown under a restricted condition that the decoding error rate per binary symbol converges to zero, only for the constructed code. With this as background, this paper compares the concatenated code and the iterated code by the common evaluation measure, considering the computational complexity required for the decoding. It is shown that the concatenated code is better than the iterated code. It is shown also that those two kinds of codes can be realized with the decoding complexity of polynomial 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 distanc ratio. For the Justesen code, which is a class of the constructive concatenated codes, and the Elias iterated code, which is a class of the iterated codes, the upper bound for the decoding error probability is separated into a function of code length and a function of code rate. the code length is represented as a function of the computational complexity required for the decoding, and the upper bounds 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 iterated code.