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 Transactions on Communications

Several Properties of Short LDPC Codes

Published Apr 1, 2004• 0 citations
Publisher

Abstract

We present several properties on minimum distance $(d_min)$ and girth $(G_min)$ in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large $G_min$ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.

DOI
10.1109/tcomm.2004.826340

Related papers

Several Properties of Short LDPC Codes

Lei Wei

In this paper, we present several properties on minimum distance(d/sub min/) and girth(G/sub min/) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large G/sub min/ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.

IEEE Transactions on Communications•May 1, 2004•23 citations

LDPC Codes of Arbitrary Girth

Tsvetan Asamov, Nuh Aydın

For regular, degree two LDPC (low density parity-check) codes, there is a strong relationship between high girth and performance. This article presents a greedy algorithm, called successive level growth (SLG), for the construction of LDPC codes with arbitrarily specified girth. The simulation results show that our codes exhibit significant coding gains over randomly constructed LDPC codes and in some cases outperform PEG codes in the additive white Gaussian noise channel.

Canadian Workshop on Information Theory (CWIT)•Jun 1, 2007•9 citations

A Combinatorial Family of Near Regular LDPC Codes

Karunakaran Murali Krishnan, Rajdeep Singh, L. Sunil Chandran +1 more

An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

arXiv:cs/0609146•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•5 citations

Finding Small Stopping Sets in the Tanner Graphs of LDPC Codes

Gerd Richter

The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1

•Apr 3, 2006•27 citations

Quasi-Cyclic Low Density Parity Check Codes

M.P.C. Fossorier

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

•Jan 1, 2003•0 citations

Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes

Shu‐Tao Xia, Fang‐Wei Fu

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

arXiv:cs/0606051•IEEE Transactions on Information Theory•Jan 1, 2008•25 citations
We present several properties on minimum distance (dmin)(d_min)(dm​in) and girth (Gmin)(G_min)(Gm​in) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large GminG_minGm​in could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.
In this paper, we present several properties on minimum distance(d/sub min/) and girth(G/sub min/) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large G/sub min/ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.
An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.
The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1
In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.
In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.