Iterative decoding on graphs with a single cycle
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.
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.Files
Name | Size | Download all |
---|---|---|
md5:fcd4694f85b6b176acf37ad3c77a9306
|
128.3 kB | Preview Download |
Additional details
- Eprint ID
- 3224
- Resolver ID
- CaltechAUTHORS:AJIisit98
- Created
-
2006-05-23Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field