A Caltech Library Service

Iterative decoding on graphs with a single cycle

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.

See Usage Policy.


Use this Persistent URL to link to this item:


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
Related URLs:
URLURL TypeDescription
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
Record Number:CaltechAUTHORS:AJIisit98
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3224
Deposited By: Archive Administrator
Deposited On:23 May 2006
Last Modified:02 Oct 2019 23:01

Repository Staff Only: item control page