Aji, Srinivas M. and Horn, Gavin B. and McEliece, Robert J. (1998) Iterative decoding on graphs with a single cycle. In: Proceedings, 1998 IEEE International Symposium on Information Theory (ISIT '98), Cambridge, MA, August 16-21, 1998. IEEE , Piscataway, NJ, p. 276. ISBN 0-7803-5000-6 http://resolver.caltech.edu/CaltechAUTHORS:AJIisit98
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AJIisit98
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.
|Item Type:||Book Section|
|Additional Information:||© Copyright 1998 IEEE. Reprinted with permission This work was partially supported by NSF grant no. NCR-9505975, AFOSR grant no. 5F49620-97-1-0313, and a grant from Qualcomm, Inc. This work was partially supported by an NSERC Scholarship.|
|Subject Keywords:||block codes, convergence of numerical methods, graph theory, iterative decoding, linear codes, probability, turbo codes|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||23 May 2006|
|Last Modified:||26 Dec 2012 08:53|
Repository Staff Only: item control page