Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Globecom

An efficient decoding algorithm for cycle-free convolutional codes and its applications

Jing Li, Krishna R. Narayanan, C.N. Georghlades

Published Nov 13, 2002• 11 citations
Publisher

Abstract

This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D/sup n/) code, whose Tanner (1981) graph is cycle-free. A rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with a lower complexity magnitude. The paper presents an explicit example which confirms the claim that the sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble low density parity check (LDPC) decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.

DOI
10.1109/glocom.2001.965634

Related papers

Sum-product decoding of convolutional codes

Toshiyuki Shohon, Yuuichi Ogawa, Haruo Ogiwara

This article proposes two methods to improve the sum-product soft-in/soft-out decoding performance of convolutional codes. The first method is to transform a parity check equation in such a way as to remove cycles of length four in a Tanner graph of a convolutional code, and performs sum-product algorithm (SPA) with the transformed parity check equation. This method improves the performance of (7,5)8convolutional code (CC1). However, for (45,73)8convolutional code (CC2), the method does not effect. The second proposed method is to use a higher order parity check equation in comparison with a normal parity check equation for SPA decoding. This method improves the performance for both convolutional codes (CC1, CC2). The performance is close to that by BCJR algorithm and it is less complex than BCJR algorithm.

International Workshop on Signal Design and its Applications in Communications•Oct 1, 2009•5 citations

A subp-optimal log-domain decoding algorithm for non-binary LDPC codes

Chirag Dadlani, Ranjan Bose

Low-Density Parity-Check (LDPC) codes have gained significant popularity recently and have been recommended for various wireless standards of the future. Non-binary LDPC codes provide all the well-known advantages of binary LDPC codes but allow for much shorter block lengths. The sum-product decoding algorithm for non-binary LDPC codes is too complex for efficient implementation. Hence, we have represented the sum-product algorithm in a novel log-domain form in terms of operators defined earlier in literature. This form greatly simplifies the key step in the check-node processing and allows us to replace a max* operation in the decoder by a max operation. This leads to a sub-optimal decoding algorithm which we propose in this paper.

•Mar 23, 2010•1 citation

Iterative Decoding for Low-Density Parity-Check Lattices

Young-Seob Choi, Ihn-Jung Baik, Sae-Young Chung

Low-density parity-check (LDPC) lattices are introduced by Sadeghi et al. (2006). The construction method of such lattices and the decoding algorithm based on the min-sum algorithm are also proposed in [1]. In this paper we apply two iterative message passing algorithms, the sum-product algorithm and the max-product algorithm, to the Tanner graph representation of LDPC lattices. We evaluate the performance of two iterative message passing algorithms.

International Conference on Advanced Communication Technology•Feb 1, 2008•13 citations

Efficient implementations of the sum-product algorithm for decoding LDPC codes

Xiao-Yu Hu, Evangelos S. Eleftheriou, D.-M. Arnold +1 more

Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.

Globecom•Nov 13, 2002•375 citations

Graph-Based Message-Passing Schedules for Decoding LDPC Codes

H. Xiao, Amir H. Banihashemi

We study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.

IEEE Transactions on Communications•Dec 1, 2004•61 citations

On the relevance of graph covers and zeta functions for the analysis of SPA decoding of cycle codes

Henry D. Pfister, Pascal O. Vontobel

For an arbitrary binary cycle code, we show that sum-product algorithm (SPA) decoding after infinitely many iterations equals symbolwise graph-cover decoding. We do this by characterizing the Bethe free energy function of the underlying normal factor graph (NFG) and by stating a global convergence proof of the SPA. We also show that the set of log-likelihood ratio vectors for which the SPA converges to the all-zero codeword is given by the region of convergence of the edge zeta function associated with the underlying NFG. The results in this paper justify the use of graph-cover pseudo-codewords and edge zeta functions to characterize the behavior of SPA decoding of cycle codes. These results have also implications for the analysis of attenuated sum-product and max-product algorithm decoding of low-density parity-check (LDPC) codes beyond cycle codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•7 citations
This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D/sup n/) code, whose Tanner (1981) graph is cycle-free. A rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with a lower complexity magnitude. The paper presents an explicit example which confirms the claim that the sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble low density parity check (LDPC) decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.
This article proposes two methods to improve the sum-product soft-in/soft-out decoding performance of convolutional codes. The first method is to transform a parity check equation in such a way as to remove cycles of length four in a Tanner graph of a convolutional code, and performs sum-product algorithm (SPA) with the transformed parity check equation. This method improves the performance of (7,5)8convolutional code (CC1). However, for (45,73)8convolutional code (CC2), the method does not effect. The second proposed method is to use a higher order parity check equation in comparison with a normal parity check equation for SPA decoding. This method improves the performance for both convolutional codes (CC1, CC2). The performance is close to that by BCJR algorithm and it is less complex than BCJR algorithm.
Low-Density Parity-Check (LDPC) codes have gained significant popularity recently and have been recommended for various wireless standards of the future. Non-binary LDPC codes provide all the well-known advantages of binary LDPC codes but allow for much shorter block lengths. The sum-product decoding algorithm for non-binary LDPC codes is too complex for efficient implementation. Hence, we have represented the sum-product algorithm in a novel log-domain form in terms of operators defined earlier in literature. This form greatly simplifies the key step in the check-node processing and allows us to replace a max* operation in the decoder by a max operation. This leads to a sub-optimal decoding algorithm which we propose in this paper.
Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.
We study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.
For an arbitrary binary cycle code, we show that sum-product algorithm (SPA) decoding after infinitely many iterations equals symbolwise graph-cover decoding. We do this by characterizing the Bethe free energy function of the underlying normal factor graph (NFG) and by stating a global convergence proof of the SPA. We also show that the set of log-likelihood ratio vectors for which the SPA converges to the all-zero codeword is given by the region of convergence of the edge zeta function associated with the underlying NFG. The results in this paper justify the use of graph-cover pseudo-codewords and edge zeta functions to characterize the behavior of SPA decoding of cycle codes. These results have also implications for the analysis of attenuated sum-product and max-product algorithm decoding of low-density parity-check (LDPC) codes beyond cycle codes.