Computing the Free Distance of Turbo Codes and Serially Concatenated Codes with Interleavers: Algorithms and Applications

We present a new algorithm for computing the free distance dfree of parallel and serially concatenated codes with interleavers, the parameter that dominates the code performance at very high signal-to-noise ratios (SNRs). The knowledge of dfree allows one to analytically estimate the error floor, which may prevent the use of concatenated codes in applications requiring very low error rates. The algorithm is based on the new notion of constrained subcodes, and permits the computation of large distances for large interleavers without a constraint on the input sequence weight (e.g., up to dfree=40 for a rate-1/3 turbo code with interleaver length N=3568). Applications to practical cases of relevant interest, i.e., (1) the new Consultative Committee for Space Data Systems (CCSDS) standard for deep-space telemetry and (2) the new UMTS/3GPP standard for third-generation personal communications, are presented for the first time. Other related aspects, like a study on the free distance distribution of turbo codes with small/medium interleaver length, and a comparison between parallel and serial concatenation behavior, are also discussed