Title :
Iterative decoding on graphs with a single cycle
Author :
Aji, Srinivas M. ; Horn, Gavin B. ; Mceliece, Robert J.
Author_Institution :
Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA, USA
Abstract :
It is now understood that the turbo decoding algorithm is an instance of a probability propagation algorithm (PPA) on a graph with many cycles. In this paper we investigate the behavior of an PPA in graphs with a single cycle such as the graph of a tail-biting code. First, we show that for strictly positive local kernels, the iterations of the PPA converge to a unique fixed point, (which was also observed by Anderson and Hladik (1998) and Weiss (1997)). Secondly, we shall generalize a result of McEliece and Rodemich (1995), by showing that if the hidden variables in the cycle are binary-valued, the PPA will always make an optimal decision. (This was also observed independently by Weiss). When the hidden variables can assume 3 or more values, the behavior of the PPA is much harder to characterize
Keywords :
block codes; convergence of numerical methods; graph theory; iterative decoding; linear codes; probability; turbo codes; binary-valued hidden variables; convergence; iterative decoding; linear block code; optimal decision; positive local kernels; probability propagation algorithm; single cycle graphs; tail-biting code; turbo decoding algorithm; Block codes; Convergence; Eigenvalues and eigenfunctions; Iterative algorithms; Iterative decoding; Kernel; Message passing; Scholarships;
Conference_Titel :
Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-7803-5000-6
DOI :
10.1109/ISIT.1998.708881
