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• 53 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

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

Low‐Density Parity‐Check Codes

Christian B. Schlegel, Lance C. Pérez

Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.

Wiley eBooks•Aug 29, 2015•6 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
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.
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 can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.
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.