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

International Conference on Advanced Communication Technology

Iterative Decoding for Low-Density Parity-Check Lattices

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

Published Feb 1, 2008• 12 citations
Publisher

Abstract

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.

DOI
10.1109/icact.2008.4493778

Related papers

Low-Density Parity-Check Lattices: Construction and Decoding Analysis

Mohammad‐Reza Sadeghi, Amir H. Banihashemi, Daniel Panario

Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands

IEEE Transactions on Information Theory•Sep 29, 2006•89 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

A new schedule for decoding low-density parity-check codes

Yongyi Mao, Amir H. Banihashemi

The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule". Unlike flooding, the probabilistic schedule operation is based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268, 456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.

Globecom•Nov 13, 2002•9 citations

An Introduction to LDPC Codes

Irene Márquez-Corbella, Edgar Martínez-Moro

The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.

Series on coding theory and cryptology•Feb 1, 2013•4 citations

Decoding low-density parity-check codes with probabilistic schedule

Yongyi Mao, Amir H. Banihashemi

The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule." Unlike flooding, the probabilistic schedule operates based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268,456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM)•Nov 13, 2002•13 citations

Finite tree-based decoding of low-density parity-check codes

Eric T. Psota

Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.

•Jan 1, 2010•3 citations
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.
Low-density parity-check codes (LDPC) can have an impressive performance under iterative decoding algorithms. In this paper we introduce a method to construct high coding gain lattices with low decoding complexity based on LDPC codes. To construct such lattices we apply Construction D', due to Bos, Conway, and Sloane, to a set of parity checks defining a family of nested LDPC codes. For the decoding algorithm, we generalize the application of max-sum algorithm to the Tanner graph of lattices. Bounds on the decoding complexity are derived and our analysis shows that using LDPC codes results in low decoding complexity for the proposed lattices. The progressive edge growth (PEG) algorithm is then extended to construct a class of nested regular LDPC codes which are in turn used to generate low density parity check lattices. Using this approach, a class of two-level lattices is constructed. The performance of this class improves when the dimension increases and is within 3 dB of the Shannon limit for error probabilities of about 10-6. This is while the decoding complexity is still quite manageable even for dimensions of a few thousands
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.
The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule". Unlike flooding, the probabilistic schedule operation is based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268, 456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.
The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.
The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "flooding schedule"). We propose a new message-passing schedule, called "probabilistic schedule." Unlike flooding, the probabilistic schedule operates based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268,456) code, at no cost in complexity, the probabilistic schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LDPC codes.
Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.