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

IEEE Information Theory Workshop (ITW)

Loop removal from LDPC codes

James A. McGowan, Robert Charles Williamson

Published Mar 2, 2004• 54 citations
Publisher

Abstract

It is hypothesised that small loops in the graphical representations of low-density parity-check codes are detrimental to the code's performance. We demonstrate a procedure for removing such loops from the codes. An algorithm based on the code's adjacency matrix is used to locate unwanted loops, and then certain edges within the graph are exchanged to eliminate those loops (without simultaneously creating any others). This process can be repeated until there are no loops remaining with a size less than a particular limit. A comparison of some theoretical and experimental values for this limit is given.

DOI
10.1109/itw.2003.1216737

Related papers

Analysis of LDPC's Loops

LI Shui-ping

Small loops in the graphical representations of low density parity-check codes are hypothesised to be detrimental to the code's performance.This paper analyzes the essential properties of LDPC codes, and then presents a kind of method for removing such loops from the graphs.

Journal of Information Engineering University•Jan 1, 2003•0 citations

Local Loop Removal from Irregular LDPC Codes

Chunjiang Duanmu

In low-density parity-check(LDPC) codes,the small loops between low degree nodes are more detrimental to the decoding performance than those between high degree nodes.In order to reduce small loops,we propose a method of exchanging the edges between nodes.It first removes the small loops between low degree nodes as much as possible,and then removes the small loops from whole LDPC codes under the condition of ensuring the smallest loop between low degree nodes not to be changed.Finally,the simulation result of constructing LDPC codes by the method is compared with that by only removing the small loops from whole LDPC codes.

Computer Era•Jan 1, 2011•0 citations

Low-Density Parity-Check Codes

W.E. Ryan, Shu Lin

Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.

Cambridge University Press eBooks•Sep 17, 2009•6 citations

Investigation of random-structure regular LDPC codes construction based on progressive edge-growth and algorithms for removal of short cycles

Viktor Ďurček, Michal Kuba, Milan Dado

This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break). Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent. The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes. The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes

Eastern-European Journal of Enterprise Technologies•Aug 31, 2021•1 citation

Algorithm for Removal of Short Cycles in Tanner Graphs with Minimum-Hamming-Distance Check

Viktor Ďurček, Michal Kuba, Milan Dado

Two algorithms for removal of short cycles in Tanner graphs of parity-check matrices of binary LDPC codes constructed by Progressive Edge-Growth algorithm are described. These loop-removing algorithms can be used to improve error-correcting performance of existing LDPC codes and achieved results are provided.

ELEKTRO•May 1, 2020•0 citations

An Introduction to LDPC Codes

Bane Vasic, Erozan M. Kurtas

Low-density parity-check (LDPC) codes are a class of linear block codes which provide near-capacity performance on a large collection of data transmission and storage channels while simultaneously admitting implementable decoders. LDPC codes were first proposed by Gallager in his 1960 doctoral dissertation [1] and were scarcely considered in the 35 years that followed. One notable exception is the important work of Tanner in 1981 [2] in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called Tanner graphs. The study of LDPC codes was resurrected in the mid1990s with the work of MacKay, Luby, and others [3-5] who noticed, apparently independently of the work of Gallager, the advantages of linear block codes which possess sparse (low-density) parity-check matrices.

CRC Press eBooks•Nov 9, 2004•15 citations
It is hypothesised that small loops in the graphical representations of low-density parity-check codes are detrimental to the code's performance. We demonstrate a procedure for removing such loops from the codes. An algorithm based on the code's adjacency matrix is used to locate unwanted loops, and then certain edges within the graph are exchanged to eliminate those loops (without simultaneously creating any others). This process can be repeated until there are no loops remaining with a size less than a particular limit. A comparison of some theoretical and experimental values for this limit is given.
In low-density parity-check(LDPC) codes,the small loops between low degree nodes are more detrimental to the decoding performance than those between high degree nodes.In order to reduce small loops,we propose a method of exchanging the edges between nodes.It first removes the small loops between low degree nodes as much as possible,and then removes the small loops from whole LDPC codes under the condition of ensuring the smallest loop between low degree nodes not to be changed.Finally,the simulation result of constructing LDPC codes by the method is compared with that by only removing the small loops from whole LDPC codes.
Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.
This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break). Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent. The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes. The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes
Low-density parity-check (LDPC) codes are a class of linear block codes which provide near-capacity performance on a large collection of data transmission and storage channels while simultaneously admitting implementable decoders. LDPC codes were first proposed by Gallager in his 1960 doctoral dissertation [1] and were scarcely considered in the 35 years that followed. One notable exception is the important work of Tanner in 1981 [2] in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called Tanner graphs. The study of LDPC codes was resurrected in the mid1990s with the work of MacKay, Luby, and others [3-5] who noticed, apparently independently of the work of Gallager, the advantages of linear block codes which possess sparse (low-density) parity-check matrices.