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

International Conference on Communications

Designing LDPC codes using bit-filling

J. Campello, Dharmendra S. Modha, S. Rajagopalan

Published Nov 13, 2002• 70 citations
Publisher

Abstract

Bipartite graphs of bit nodes and parity check nodes arise as Tanner graphs corresponding to low density parity check codes. Given graph parameters such as the number of check nodes, the maximum check-degree, the bit-degree, and the girth, we consider the problem of constructing bipartite graphs with the largest number of bit nodes, that is, the highest rate. We propose a simple-to-implement heuristic bit-filling algorithm for this problem. As a benchmark, our algorithm yields codes better or comparable to those in MacKay (1999).

DOI
10.1109/icc.2001.936272

Related papers

An Algorithm for Checking Girth of Low Density Parity Check Codes in Bipartite Graphs

Hong Zhou

The girth is an indication of the quality of Low Density Parity Check(LDPC) Codes. For any given LDPC Codes,quickly checking their girths is of some important significance. An algorithm for quickly checking the girth of LDPC Codes in bipartite graphs is presented. This algorithm can also give out the numbers of the shortest cycles passing through the given check node (or bit node). The testing result of this algorithm implemented in MATLAB shows that,even for large-scale H matrix of LDPC Codes like PEGReg504x1008,it takes only 2.876 s for the algorithm to finish checking.

Information and Electronic Engineering•Jan 1, 2009•0 citations

A random construction of LDPC codes using a sub-optimal search algorithm

Seif Shebl, Nawal Ahmed El-Fishawy, Atef Abou Elazm +1 more

In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.

National Radio Science Conference•Jan 1, 2009•1 citation

Extended PEG Algorithm for High Rate LDPC Codes

Zhiheng Zhou, Xiangxue Li, Dong Zheng +2 more

Progressive Edge-Growth(PEG) Algorithm is a good candidate to generate Tanner Graphs with a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner. In this paper, we propose an extended PEG algorithm for constructing Low-Density Parity-Check (LDPC) codes with very high rate when given a lower bound of girth. Simulation results show the bit error rates of constructed LDPC codes with very high rate or large girth.

IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)•Jan 1, 2009•5 citations

A novel algorithm of constructing LDPC codes with graph theory

Yan Cui, Xinhui Si, Yanan Shen

There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.

IEEE Conference on Cybernetics and Intelligent Systems•Sep 1, 2008•2 citations

PWG: Progressive Weight-Growth Algorithm for LDPC Codes

Xiangxue Li, Qingji Zheng, Haifeng Qian +2 more

Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•0 citations

A heuristic search for good low-density parity-check codes at short block lengths

Yongyi Mao, Amir H. Banihashemi

For a given block length and given degree sequences of the underlying Tanner graph (TG), the ensemble of short low-density parity-check (LDPC) codes can have considerable variation in performance. We present an efficient heuristic method to find good LDPC codes based on what we define as the girth distribution of the TG. This method can be used effectively to design short codes for applications where delay and complexity are of major concern.

International Conference on Communications•Nov 13, 2002•171 citations
Bipartite graphs of bit nodes and parity check nodes arise as Tanner graphs corresponding to low density parity check codes. Given graph parameters such as the number of check nodes, the maximum check-degree, the bit-degree, and the girth, we consider the problem of constructing bipartite graphs with the largest number of bit nodes, that is, the highest rate. We propose a simple-to-implement heuristic bit-filling algorithm for this problem. As a benchmark, our algorithm yields codes better or comparable to those in MacKay (1999).
The girth is an indication of the quality of Low Density Parity Check(LDPC) Codes. For any given LDPC Codes,quickly checking their girths is of some important significance. An algorithm for quickly checking the girth of LDPC Codes in bipartite graphs is presented. This algorithm can also give out the numbers of the shortest cycles passing through the given check node (or bit node). The testing result of this algorithm implemented in MATLAB shows that,even for large-scale H matrix of LDPC Codes like PEGReg504x1008,it takes only 2.876 s for the algorithm to finish checking.
In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.
There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.
Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).