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

IOP Conference Series Materials Science and Engineering

Cut-Node Tree and Loops of LDPCs

Huanming Zhang

Published Jan 1, 2020• 0 citations
Publisher

Abstract

Abstract Bipartite graph is used to illustrate Low-density parity-check (LDPC) code by Tanner [1]. In this thesis, we introduce a new algorithm to depict LDPC codes. Cut-node tree(CNT), although appearing to be a tree defined in graph theory, can figure out all cycles of an LDPC. And this method can apply to decoding, help to prevent superfluous iteration in belief propagation (BP).

DOI
10.1088/1757-899x/719/1/012058

Related papers

Tree Matrix Algorithm of LDPC Codes

Huanming Zhang

LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth. An LDPC code is defined by a sparse parity-check matrix and can be described by a bipartite graph called Tanner graph. Loops in Tanner graph prevent the sum-product algorithm from converging. Further, loops, especially short loops, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper, by graph theory, deduces cut-node tree graph of LDPC code, and depicts it with matrix. On the basis of tree matrix algorithm, whole depictions of loops can be figured out, providing of foundation for further research of relations between loops and LDPC codes’ performance.

Journal of Signal and Information Processing•Jan 1, 2014•0 citations

MESSAGE PASSINGAND LOOPS SOLUTION ALGORITHM BASED ON CUT-NODE TREE

Huanming Zhang

Low-density parity-check (LDPC) codes are forward error-correction and linear block codes. An LDPC code can be described by a bipartite graph called Tanner graph(1). Loops, especially short loops in tanner graph, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. In this paper, based on graph theory and Tanner graph, the loop structure in LDPC codes are studied carefully, a new notion, cut-node tree, is proposed to describe LDPC codes. Cut-node tree has full information of Tanner graph. So all loop features in LDPCs can be calculated relatively easy by a computer. Traditional message passing in graph is improved to avoid repeated iteration of information, a new decoding schemes for LDPC codes is proposed and can suppress repeated iteration of information in SPA. The results help to further research on related field.

International Journal of Geomate•Jan 1, 2016•0 citations

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

Juane Li, Shu Lin, Khaled Abdel-Ghaffar

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.

Information Theory and Applications Workshop (ITA)•Feb 1, 2018•0 citations

Low-Density Parity-Check Codes

Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.

Kluwer Academic Publishers eBooks•Dec 21, 2005•8 citations

An improved decoding algorithm of low-density parity-check codes

Yongqiang Deng, Guangxi Zhu, Liu Wenming +1 more

In this paper, the decoding algorithm of low-density parity-check (LDPC) codes is analyzed, and a new decoding algorithm based on the belief propagation (BP) algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm, the cycles of factor graph sends message back to its source, and this decreases the decoding performance. The new algorithm records each cycle's path and length of each node, and cuts off the path by which message is propagated when the message comes back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.

International Conference on Wireless Communications, Networking and Mobile Computing•Dec 10, 2005•0 citations

A Study on Low Complexity Decoding Algorithm of LDPC Codes

Yong Deng

In this paper,the decoding algorithm of low-density parity-check(LDPC)codes is analyzed,and a new decoding algorithm based on the belief propagation(BP)algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm,the cycles of factor graph will send message back to its source,and this will decrease the decoding performance. The new algorithm records each cycle’s path and length of each node,and cuts off the path by which message is propagated when the message will come back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.

•Jan 1, 2006•0 citations
Abstract Bipartite graph is used to illustrate Low-density parity-check (LDPC) code by Tanner [1]. In this thesis, we introduce a new algorithm to depict LDPC codes. Cut-node tree(CNT), although appearing to be a tree defined in graph theory, can figure out all cycles of an LDPC. And this method can apply to decoding, help to prevent superfluous iteration in belief propagation (BP).
LDPC codes are finding increasing use in applications requiring reliable and highly efficient information transfer over bandwidth. An LDPC code is defined by a sparse parity-check matrix and can be described by a bipartite graph called Tanner graph. Loops in Tanner graph prevent the sum-product algorithm from converging. Further, loops, especially short loops, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. This paper, by graph theory, deduces cut-node tree graph of LDPC code, and depicts it with matrix. On the basis of tree matrix algorithm, whole depictions of loops can be figured out, providing of foundation for further research of relations between loops and LDPC codes’ performance.
Low-density parity-check (LDPC) codes are forward error-correction and linear block codes. An LDPC code can be described by a bipartite graph called Tanner graph(1). Loops, especially short loops in tanner graph, degrade the performance of LDPC decoder, because they affect the independence of the extrinsic information exchanged in the iterative decoding. In this paper, based on graph theory and Tanner graph, the loop structure in LDPC codes are studied carefully, a new notion, cut-node tree, is proposed to describe LDPC codes. Cut-node tree has full information of Tanner graph. So all loop features in LDPCs can be calculated relatively easy by a computer. Traditional message passing in graph is improved to avoid repeated iteration of information, a new decoding schemes for LDPC codes is proposed and can suppress repeated iteration of information in SPA. The results help to further research on related field.
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.
Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.
In this paper, the decoding algorithm of low-density parity-check (LDPC) codes is analyzed, and a new decoding algorithm based on the belief propagation (BP) algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm, the cycles of factor graph sends message back to its source, and this decreases the decoding performance. The new algorithm records each cycle's path and length of each node, and cuts off the path by which message is propagated when the message comes back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.
In this paper,the decoding algorithm of low-density parity-check(LDPC)codes is analyzed,and a new decoding algorithm based on the belief propagation(BP)algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm,the cycles of factor graph will send message back to its source,and this will decrease the decoding performance. The new algorithm records each cycle’s path and length of each node,and cuts off the path by which message is propagated when the message will come back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.