Iterative Decoder for Quantum Turbo Codes: Performance Analysis and Enhancement.

Shiro Ikeda, Toshiyuki Tanaka, Шун-ичи Амари

Since the proposal of turbo codes in 1993, many studies have appeared on this simple and new type of codes which give a powerful and practical performance of error correction. Although experimental results strongly support the efficacy of turbo codes, further theoretical analysis is necessary, which is not straightforward. It is pointed out that the iterative decoding algorithm of turbo codes shares essentially similar ideas with low-density parity-check (LDPC) codes, with Pearl's belief propagation algorithm applied to a cyclic belief diagram, and with the Bethe approximation in statistical physics. Therefore, the analysis of the turbo decoding algorithm will reveal the mystery of those similar iterative methods. In this paper, we recapture and extend the geometrical framework initiated by Richardson to the information geometrical framework of dual affine connections, focusing on both of the turbo and LDPC decoding algorithms. The framework helps our intuitive understanding of the algorithms and opens a new prospect of further analysis. We reveal some properties of these codes in the proposed framework, including the stability and error analysis. Based on the error analysis, we finally propose a correction term for improving the approximation.

Sajed Sajed

Meina Xu

Since the invention of turbo codes, there has been an explosion of interest in iterative decoding and graphical representation of codes. This thesis examines the iterative decoding of codes defined on graphs with cycles, which appears to be an efficient means of achieving the Shannon limit. Much of this analysis is on the iterative min-sum decoding of tail-biting codes and cycle codes. We have identified the pseudocodeword as the cause of the suboptimal performance of the iterative decoder, and we have obtained a union bound for the performance of the iterative decoder on both AWGN and BSC channels. Using the union bound argument, for cycle codes, we have shown that the performance of the iterative decoder is asymptotically as good as that of the ML decoder. As for tail-biting codes, the same thing is true if the lowest weight pseudocodeword is at least the minimum weight of the code. Unfortunately, the analysis of tail-biting codes and cycle codes does not extend to turbo codes and low density parity check codes in general. Our next approach is to determine the average behavior of message passing algorithms by studying the evolution of their "message" densities. For the class of "repeat and accumulate" serially concatenated turbo-like codes, we have devised an algorithm for determining their "threshold" values. When the signal-to-noise ratio is larger than the threshold value, the error probabilities of message passing algorithms approach zero, whereas if the signal-to-noise ratio is less than the threshold value, the error probability stays bounded away from zero. Some message passing algorithms and graphical representation of codes are efficient means of devising ML or MAP decoding algorithms. We have proposed a junction tree representation for linear block codes, and we have shown that the minimum junction tree can be less complex than the minimal trellis.

Luca Menti

Gavin Bernard Horn

In the last six years, we have witnessed an explosion of interest in the coding theory community, in iterative decoding and graphical models, due primarily to the invention of turbo codes. While the structural properties of turbo codes and low density parity check codes have now been put on a firm theoretical footing, what is still lacking is a satisfactory theoretical explanation as to why iterative decoding algorithms perform as well as they do. In this thesis we make a first step by discussing the behavior of various iterative decoders for the graphs of tail-biting codes and cycle codes. By increasing our understanding of the behavior of the iterative min-sum (MSA) and sum-product (SPA) algorithms on graphs with cycles, we can design codes which achieve better performance. Much of this thesis is devoted to the analysis of the performance of the MSA and SPA on the graphs for tail-biting codes and cycle codes. We give sufficient conditions for the MSA to converge to the maximum likelihood codeword after a finite number of iterations. We also use the familiar union bound argument to characterize the performance of the MSA after many iterations. For a cycle code, we show that the performance of the MSA decoder is asymptotically as good as maximum likelihood. For tail-biting codes this will depend on our choice of trellis.

Iryna Andriyanova, Jean–Pierre Tillich