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

Information Theory and Applications Workshop (ITA)

Improved Trellis-Based Algorithm for Locating and Breaking Cycles in Bipartite Graphs with Applications to LDPC Codes

Juane Li, Shu Lin, Khaled Abdel-Ghaffar

Published Feb 1, 2018• 0 citations
Publisher

Abstract

LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.

DOI
10.1109/ita.2018.8503249

Related papers

Improved cycle elimination algorithm for construction of QC-LDPC codes

Xudong Guo

A novel construction algorithm for quasi-cyclic low-density parity-check codes is proposed,with which we can obtain the improved girth of the corresponding Tanner graph by generalizing Yang et al.'s constraint for any cycle detected in the base matrix to detect and break the cycles in the parity check matrix.Compared with the existing cycle elimination(CE) algorithm,a better error performance can be achieved and cycle-8 free.Simulation results show that the proposed algorithm for constructing the irregular LDPC code of rate 1/2 achieves the performance of codeword error rate of 2×10-6at Eb/N0=1.5dB with 80 iterations by the belief-propagation decoding algorithm.

Journal of Xidian University•Jan 1, 2010•0 citations

Performance improvement of short-length regular low-density parity-check codes with low-complexity post-processing

Raghunadh K. Bhattar, K.R. Ramakrishnan, K. S. Dasgupta

It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high Eb/N0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high Eb/N0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.

IET Communications•Oct 16, 2012•1 citation

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

A high‐performance belief propagation decoding algorithm for codes with short cycles

Ali Karimi-lenji, Monireh Houshmand, Fahimeh Zarmehi

Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.

International Journal of Communication Systems•Feb 28, 2017•2 citations

Quasi-Cyclic Low-Density Parity-Check Codes Based on Progressive Cycle Growth Algorithm

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2016•1 citation

A Method of Counting the Number of Cycles in LDPC Codes

Jun Fan, Yang Xiao

For a given block length sequences of the underlying Tanner graph (TG), the short circles of low-density parity check (LDPC) codes can have considerable variation in performance. By analyzing the shapes of the cycles of TG in parity check matrix, this paper presents a method of counting the number of 4-cycles, 6-cycles, 8-cycles and 10-cycles. Taking out a certain number of rows for different cycles, counting the number of cycles contained in these rows, then adding up all the number of cycles that contained in all possible combinations of the rows in the matrix, and we can get the number of cycles in the matrix. This method can be used effectively to evaluate the performance of LDPC codes according to their short circles distributions. Applying this method, we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes, the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although their girth performance is not as good as the quasi-cyclic LDPC codes.

•Jan 1, 2006•27 citations
LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.
A novel construction algorithm for quasi-cyclic low-density parity-check codes is proposed,with which we can obtain the improved girth of the corresponding Tanner graph by generalizing Yang et al.'s constraint for any cycle detected in the base matrix to detect and break the cycles in the parity check matrix.Compared with the existing cycle elimination(CE) algorithm,a better error performance can be achieved and cycle-8 free.Simulation results show that the proposed algorithm for constructing the irregular LDPC code of rate 1/2 achieves the performance of codeword error rate of 2×10-6at Eb/N0=1.5dB with 80 iterations by the belief-propagation decoding algorithm.
It is well known that extremely long low-density parity-check (LDPC) codes perform exceptionally well for error correction applications, short-length codes are preferable in practical applications. However, short-length LDPC codes suffer from performance degradation owing to graph-based impairments such as short cycles, trapping sets and stopping sets and so on in the bipartite graph of the LDPC matrix. In particular, performance degradation at moderate to high Eb/N0 is caused by the oscillations in bit node a posteriori probabilities induced by short cycles and trapping sets in bipartite graphs. In this study, a computationally efficient algorithm is proposed to improve the performance of short-length LDPC codes at moderate to high Eb/N0. This algorithm makes use of the information generated by the belief propagation (BP) algorithm in previous iterations before a decoding failure occurs. Using this information, a reliability-based estimation is performed on each bit node to supplement the BP algorithm. The proposed algorithm gives an appreciable coding gain as compared with BP decoding for LDPC codes of a code rate equal to or less than 1/2 rate coding. The coding gains are modest to significant in the case of optimised (for bipartite graph conditioning) regular LDPC codes, whereas the coding gains are huge in the case of unoptimised codes. Hence, this algorithm is useful for relaxing some stringent constraints on the graphical structure of the LDPC code and for developing hardware-friendly designs.
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.
Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.
For a given block length sequences of the underlying Tanner graph (TG), the short circles of low-density parity check (LDPC) codes can have considerable variation in performance. By analyzing the shapes of the cycles of TG in parity check matrix, this paper presents a method of counting the number of 4-cycles, 6-cycles, 8-cycles and 10-cycles. Taking out a certain number of rows for different cycles, counting the number of cycles contained in these rows, then adding up all the number of cycles that contained in all possible combinations of the rows in the matrix, and we can get the number of cycles in the matrix. This method can be used effectively to evaluate the performance of LDPC codes according to their short circles distributions. Applying this method, we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes, the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although their girth performance is not as good as the quasi-cyclic LDPC codes.