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
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 125Kb |
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AJIisit98
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.
| 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 |
| Record Number: | CaltechAUTHORS:AJIisit98 |
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:AJIisit98 |
| Alternative URL: | http://dx.doi.org/10.1109/ISIT.1998.708881 |
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. |
| ID Code: | 3224 |
| Collection: | CaltechAUTHORS |
| Deposited By: | Archive Administrator |
| Deposited On: | 23 May 2006 |
| Last Modified: | 26 Dec 2012 08:53 |
Repository Staff Only: item control page
