Asymptotic analysis of turbo-like codes. Average spectra and minimum distances

The topic of this dissertation falls within channel coding theory, and consists in the analysis of a particular class of turbo-like codes, defined by a multiple concatenation of an arbitrary outer encoder with m truncated convolutional encoders through uniform random permutations. Fixed the number of inner encoders, structural properties of these coding schemes are studied when the truncation length goes to infinity. As a first step in this study, we focus on truncated convolutional encoders, which are the constituent elements of turbo concatenations. We present a detailed analysis of the related weight distribution functions and of their exponential growth rate. In particular, the weight distribution functions are expressed as coefficients of the generating function of error events associated with a minimal realization of the encoder. Although these expressions can be computed for relatively small truncation lengths, they become prohibitively complex to compute as truncation lengths and weights increase. Fortunately, a very accurate approximation can be derived using the Multidimensional Saddle Point method. This approximation is substantially easier to evaluate and is used to obtain an expression for the asymptotic spectral function and to prove continuity and concavity. Finally, this approach is able to guarantee that the sequence of exponential growth rate converges uniformly to the asymptotic limit and to estimate the speed of this convergence. Building upon these results, we show that for multiple concatenated coding schemes the average distance spectra can be obtained through the analysis of a dynamical system (dependent on the inner encoder) with initial condition equal to the asymptotic spectra of the outer encoder. Moreover, they are equal to 0 below a threshold distance ?m and positive beyond it. Then, minimum distances are shown to scale linearly in the code-length with probability one, and the asymptotic normalized minimum distance to be exactly provided by ?m. Under a very mild condition on the outer encoder asymptotic spectral functions form a uniformly convergent sequence of functions. Their limit is the maximum between 0 and the average spectral shape of the random linear coding ensemble. As a consequence, the threshold sequence ?m converges to the Gilbert-Varshamov distance, the best lower bound on the largest minimum distance achievable by a code. Finally, we consider another family of binary codes that can be seen both as particular systematic serial turbo codes and as structured Low-Density Parity- Check codes. Using similar techniques, we analyze minimum distances and prove coding theorems, already obtained for multiple serially concatenated codes, even in this new setting. Summarizing theoretical results, we describe some guidelines to design asymptotically good coding schemes.