In this paper we start by presenting some rsults on the state-space complexity of Turbo codes. Next, we establish the connection between the upperbound on the ocmplexity of permutations, and their structural properties; in particular, their decomposition into product of cycles. We conclude that the most complex decoder for a given Turbo code as a function of the interleaver is obtained using an interleave whereby the permutation it performs is not decomposable into product of cycles. Subsequently, we develop an expression selectedpermutations, for different size permutations. Finally, using informatio about the mean and variance of jthe number of cycles in random permutations, we conclude that most randomly chosen large interleavers lea to Turbo codes with high complexity.
展开▼