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

IET International Conference on Communication Technology and Application (ICCTA)

A new forced convergence decoding scheme for LDPC codes

Jianxiao Fan, Hongwen Yang

Published Oct 1, 2009• 11 citations
Publisher

Abstract

In this paper, we present a new forced convergence decoding scheme for LDPC codes. We remove the early detected variable nodes from the Tanner graph and thus the parity matrix shrinks iteration by iteration and the decoding complexity can be reduced. When the parity check matrix shrinks to zero before the maximum iteration, we get a chance to detect the wrong deletion and, for the decodable codewords, most of such failure can be recovered by restoring the original Tanner graph and resuming the decoding in the remaining iterations. Simulations results indicate that the proposed method can reduce the decoding complexity significantly while keep the error rate performance unchanged or even better.

DOI
10.1109/iccomta.2009.5349137

Related papers

Two Phases GC-LDPC Decoding Aided with Early Termination and Forced Convergece

Kun Zhu, Hongwen Yang

The fast decoding of low-density parity-check (LDPC) is crucial for its future applications. In this paper, we propose to use Early Termination (ET) and Force Convergence (FC) techniques to accelerate the decoding of two new local/global two-phases decoding algorithms to reduce the Globally Coupled (GC) LDPC codes. Specifically, ET is applied in the local decoding phase of two- phases decoding of GC-LDPC codes to skip the local decoding which is highly likely to fail and avoid the unnecessary iterations. FC is applied in global decoding phase where converged variable nodes are identified and removed from Tanner graph and the decoding can be speed up shrinking parity check matrices. Two variants are proposed for the ET operation in local decoding phase. ET-1 merely stops iteration if it meets the stopping criterion while in ET-1, the iteration number saved in local decoding is added up in global decoding to improve the decoding performance. The simulation results show that the ET-1-FC scheme can save up to 42% decoding time complexity in the low SNR region while keeping the error rate performance nearly unchanged, the ET-2-FC can improve the error rate performance by 0.18dB at bit error rate 0.001 or 0.23dB at frame error rate 0.1. In the waterfalling region of BER/FER curves, both schemes can save about 25% decoding time complexity.

•Jul 2, 2024•0 citations

A new method of detecting cycles in Tanner graph of LDPC codes

Bo Li, Gang Wang, Hongjuan Yang

To improve the performance of LDPC codes, we should detect and eliminate cycles in Tanner graph of the parity-check matrix when we make LDPC codes. We improved a logic algebraic algorithm in computing entire routes between the nodes of a communication network, and found a new method of detecting cycles in Tanner graph of LDPC codes. This method applied the logic algebraic calculation rules. First transformed the parity-check matrix and then constructed the relative matrix of the Tanner graph. Through integrating and deleting rows of relative matrix and correcting some elements, this new algorithm can detect all the cycles in a Tanner graph of LDPC codes which code length is n and information bits number is k, just needing integrating and deleting n-1 times and correcting k times. The calculation steps of the algorithm is shown detailed by an (8, 4, 2) LDPC example and its correctness have been validated.

International Conference on Wireless Communications and Signal Processing (WCSP)•Nov 1, 2009•5 citations

An Iterative Decoding Algorithm with Backtracking to Lower the Error-Floors of LDPC Codes

Jingyu Kang, Qin Huang, Shu Lin +1 more

Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.

IEEE Transactions on Communications•Oct 27, 2010•45 citations

Breaking the Trapping Sets in LDPC Codes: Check Node Removal and Collaborative Decoding

Soonyoung Kang, Jaekyun J. Moon, Jeongseok Ha +1 more

Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.

IEEE Transactions on Communications•Nov 5, 2015•17 citations

A new random construction for low-density parity-check codes

Zhonghu Huang, Shen Lianfeng, Zhihui Ye

This paper gives a new random construction for LDPC codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has low complexity and great flexible choice in LDPC code parameters including code length, code rate, least girth of the graph, and the weight of column and row in the parity-check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Simulations show that the method performs well with iterative decoding.

International Conference on Communications, Circuits and Systems•Aug 16, 2005•0 citations

Fast convergence algorithm for decoding of low density parity check codes

Jin Xie, Liuguo Yin, Ning Ge +1 more

Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1

WSEAS TRANSACTIONS on COMMUNICATIONS archive•Jul 1, 2009•1 citation
In this paper, we present a new forced convergence decoding scheme for LDPC codes. We remove the early detected variable nodes from the Tanner graph and thus the parity matrix shrinks iteration by iteration and the decoding complexity can be reduced. When the parity check matrix shrinks to zero before the maximum iteration, we get a chance to detect the wrong deletion and, for the decodable codewords, most of such failure can be recovered by restoring the original Tanner graph and resuming the decoding in the remaining iterations. Simulations results indicate that the proposed method can reduce the decoding complexity significantly while keep the error rate performance unchanged or even better.
The fast decoding of low-density parity-check (LDPC) is crucial for its future applications. In this paper, we propose to use Early Termination (ET) and Force Convergence (FC) techniques to accelerate the decoding of two new local/global two-phases decoding algorithms to reduce the Globally Coupled (GC) LDPC codes. Specifically, ET is applied in the local decoding phase of two- phases decoding of GC-LDPC codes to skip the local decoding which is highly likely to fail and avoid the unnecessary iterations. FC is applied in global decoding phase where converged variable nodes are identified and removed from Tanner graph and the decoding can be speed up shrinking parity check matrices. Two variants are proposed for the ET operation in local decoding phase. ET-1 merely stops iteration if it meets the stopping criterion while in ET-1, the iteration number saved in local decoding is added up in global decoding to improve the decoding performance. The simulation results show that the ET-1-FC scheme can save up to 42% decoding time complexity in the low SNR region while keeping the error rate performance nearly unchanged, the ET-2-FC can improve the error rate performance by 0.18dB at bit error rate 0.001 or 0.23dB at frame error rate 0.1. In the waterfalling region of BER/FER curves, both schemes can save about 25% decoding time complexity.
To improve the performance of LDPC codes, we should detect and eliminate cycles in Tanner graph of the parity-check matrix when we make LDPC codes. We improved a logic algebraic algorithm in computing entire routes between the nodes of a communication network, and found a new method of detecting cycles in Tanner graph of LDPC codes. This method applied the logic algebraic calculation rules. First transformed the parity-check matrix and then constructed the relative matrix of the Tanner graph. Through integrating and deleting rows of relative matrix and correcting some elements, this new algorithm can detect all the cycles in a Tanner graph of LDPC codes which code length is n and information bits number is k, just needing integrating and deleting n-1 times and correcting k times. The calculation steps of the algorithm is shown detailed by an (8, 4, 2) LDPC example and its correctness have been validated.
Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.
Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.
This paper gives a new random construction for LDPC codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has low complexity and great flexible choice in LDPC code parameters including code length, code rate, least girth of the graph, and the weight of column and row in the parity-check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Simulations show that the method performs well with iterative decoding.
Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1