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

Australian Communications Theory Workshop

The effect of cycles on binary message-passing decoding of LDPC codes

Gottfried Lechner

Published Feb 1, 2010• 5 citations
Publisher

Abstract

We study the error-floor behavior of binary message-passing decoders for low-density parity-check (LDPC) codes. We find that the stability condition is independent of the quality of the channel messages (i.e. soft or hard decision). Furthermore, we identify a structure in the graph where the involved variable nodes cannot be corrected by the binary message-passing decoder. This leads to an error floor for regular LDPC codes with variable node degree smaller than four. An additional constraint on the degree distribution is derived which allows to avoid this structure, leading to optimized LDPC codes without error floors.

DOI
10.1109/ausctw.2010.5426759

Related papers

Analysis and Design of Binary Message Passing Decoders

Gottfried Lechner, Troels Pedersen, Gerhard G. Kramer

Binary message passing decoders for low-density parity-check codes are studied by using extrinsic information transfer charts. The channel delivers hard or soft decisions and the variable node decoder performs all computations in the log-likelihood ratio (L-value) domain. A hard decision results in the Gallager B algorithm and examples show that increasing the channel output alphabet to two bits gains more than 1.0 dB in signal to noise ratio when using optimized codes. Finally, it is shown that errors on cycles consisting only of degree two and three variable nodes cannot be corrected and a necessary and sufficient condition for the existence of a cycle-free subgraph is derived.

arXiv:1004.4020•IEEE Transactions on Communications•Dec 29, 2011•49 citations

Absorbing sets and cycles

Gottfried Lechner, Sarah J. Johnson

Absorbing sets have been identified as structures in the graph of a low-density parity-check code that cause error floors - in particular in combination with binary message passing decoding algorithms. In this paper it is shown that absorbing sets involving only variable nodes up to degree 3 are equivalent to cycles and a sufficient and necessary condition on the degree distribution to avoid these absorbing sets is derived. The results are extended to irregular graphs and simulation results demonstrate the improvement in the error floor region.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2012•0 citations

Studies on Lowering the Error Floors of Finite Length LDPC codes

Huanlin Li

Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial

•Jan 1, 2011•0 citations

Properties of Optimum Binary Message-Passing Decoders

Masoud Ardakani, Frank R. Kschischang

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

IEEE Transactions on Information Theory•Sep 26, 2005•14 citations

Selective Avoidance of Cycles in Irregular LDPC Code Construction

T. Tian, C.R. Jones, John D. Villasenor +1 more

This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.

IEEE Transactions on Communications•Aug 1, 2004•396 citations

Message Passing Decoder with Decoding on Zigzag Cycles for Non-binary LDPC Codes

T. Nozaki, Kenta Kasai, Kohichi Sakaniwa

In this paper, we propose a message passing decoding algorithm which lowers decoding error rates in the error floor regions for non-binary low-density parity-check (LDPC) codes transmitted over the binary erasure channel (BEC) and the memoryless binary-input output-symmetric (MBIOS) channels. In the case for the BEC, this decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding errors in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. Moreover, we extend this decoding algorithm to the MBIOS channels. Simulation results demonstrate that the decoding error rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•2 citations
We study the error-floor behavior of binary message-passing decoders for low-density parity-check (LDPC) codes. We find that the stability condition is independent of the quality of the channel messages (i.e. soft or hard decision). Furthermore, we identify a structure in the graph where the involved variable nodes cannot be corrected by the binary message-passing decoder. This leads to an error floor for regular LDPC codes with variable node degree smaller than four. An additional constraint on the degree distribution is derived which allows to avoid this structure, leading to optimized LDPC codes without error floors.
Binary message passing decoders for low-density parity-check codes are studied by using extrinsic information transfer charts. The channel delivers hard or soft decisions and the variable node decoder performs all computations in the log-likelihood ratio (L-value) domain. A hard decision results in the Gallager B algorithm and examples show that increasing the channel output alphabet to two bits gains more than 1.0 dB in signal to noise ratio when using optimized codes. Finally, it is shown that errors on cycles consisting only of degree two and three variable nodes cannot be corrected and a necessary and sufficient condition for the existence of a cycle-free subgraph is derived.
Absorbing sets have been identified as structures in the graph of a low-density parity-check code that cause error floors - in particular in combination with binary message passing decoding algorithms. In this paper it is shown that absorbing sets involving only variable nodes up to degree 3 are equivalent to cycles and a sufficient and necessary condition on the degree distribution to avoid these absorbing sets is derived. The results are extended to irregular graphs and simulation results demonstrate the improvement in the error floor region.
Low-density parity-check (LDPC) codes can approach the Shannon limit performance closely, and are becoming one of the most promising channel codes in the Error Control Coding area.The performance of an LDPC code with given length is mainly affected by the sizes of some combinatorial characteristics of its corresponding bipartite graph and the distribution of variable degrees and check node degrees.With the help of the density evolution algorithm, randomly designed LDPC codes, with carefully chosen degree distribution pairs, have been shown to achieve better Shannon capacity performance than their regular counterparts when decoded using the iterative belief propagation (BP) decoding algorithm.However, regular LDPC codes outperform their irregular counterparts in term of their error floors.Therefore, construction of LDPC codes which have both attractive error rate performance and low error floor performance has become an attractive topic.Currently, optimization of variable node degree distribution and check node degree distribution for an LDPC code with given length, which could help the code to achieve good Shannon limit performance, has been extensively studied.In this dissertation, we demonstrate some approaches of improving the error floor performance for a given LDPC code with desired degree distribution pair.The contribution mainly includes three parts.In the first part, the relationship between cycles and unfavorable combinatorial
We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.
This letter explains the effect of graph connectivity on error-floor performance of low-density parity-check (LDPC) codes under message-passing decoding. A new metric, called extrinsic message degree (EMD), measures cycle connectivity in bipartite graphs of LDPC codes. Using an easily computed estimate of EMD, we propose a Viterbi-like algorithm that selectively avoids small cycle clusters that are isolated from the rest of the graph. This algorithm is different from conventional girth conditioning by emphasizing the connectivity as well as the length of cycles. The algorithm yields codes with error floors that are orders of magnitude below those of random codes with very small degradation in capacity-approaching capability.
In this paper, we propose a message passing decoding algorithm which lowers decoding error rates in the error floor regions for non-binary low-density parity-check (LDPC) codes transmitted over the binary erasure channel (BEC) and the memoryless binary-input output-symmetric (MBIOS) channels. In the case for the BEC, this decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding errors in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. Moreover, we extend this decoding algorithm to the MBIOS channels. Simulation results demonstrate that the decoding error rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.