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 Symposium on Information Theory and its Applications

Three-edge type LDPC code ensembles with exponentially few codewords with linear small weight

Tomoharu Awano, Kenta Kasai, Tomoharu Shibuya, Kohichi Sakaniwa

Published Dec 1, 2008• 6 citations
Publisher

Abstract

Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with minimum distance linearly increasing in code length. Nakasendo et al. derived the condition that code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. In this paper, we derive the condition for three-edge type LDPC code ensembles whose edge-types does not share any variable node and does share all of the check nodes with exponentially decreasing small linear weight codewords. The condition is necessary for the existence of the average relative minimum distance of ensembles. Our method is expected to derive the condition for multi-edge type LDPC codes.

DOI
10.1109/isita.2008.4895505

Related papers

Analysis of weight distributions of two-edge type LDPC codes by Hayman approximation

Tomoharu Awano, Kenta Kasai, Tomoharu Shibuya +1 more

Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with small linear weight codewords exponentially decreasing in code length. Nakasendo et al. derived the condition in which code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. Our conclusion is the same as that of Nakasendo et al., and although Nakasendopsilas method is difficult to apply to more than three edge-types, there is a possibility that our method using Hayman approximation as Di et al. do derives the condition for multi-edge type LDPC codes ensembles.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•2 citations

Two-edge type LDPC code ensembles with exponentially few codewords with linear small weight

Tsuyoshi Nakasendo, Kenta Kasai, Tomoharu Shibuya +1 more

Multi-Edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles has better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with minimum distance linearly increasing in code length. We derive the condition corresponding to Orlitsky’s condition for two-edge type LDPC code ensembles which is simple example of Multi-Edge type LDPC code ensembles.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•2 citations

Weight distributions of multi-edge type LDPC codes

Kenta Kasai, Tomoharu Awano, David Declercq +2 more

For a (lambda(x); rho(x)) standard irregular LDPC code ensemble, the growth rate of the average weight distribution for small relative weight omega is given by log(lambda'(0)rho'(1))omega + O(omega2) in the limit of code length n. If lambda'(0)rho'(1) < 1, there exist exponentially few code words of small linear weight, as n tends to infinity. It is known that the condition coincides with the stability condition of density evolution over the erasure channels with the erasure probability 1. In this paper, we show that this is also the case with multi-edge type LDPC (MET-LDPC) codes. MET-LDPC codes are generalized structured LDPC codes introduced by Richardson and Urbanke. The parameter corresponding lambda'(0)rho'(1) appearing in the conditions for MET-LDPC codes is given by the spectral radius of the matrix defined by extended degree distributions.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•10 citations

Weight Distributions of Multi-Edge Type LDPC Codes

Kenta Kasai, Tomoharu Awano, David Declercq +2 more

The multi-edge type LDPC codes, introduced by Richardson and Urbanke, present the general class of structured LDPC codes. In this paper, we derive the average weight distributions of the multi-edge type LDPC code ensembles. Furthermore, we investigate the asymptotic exponential growth rate of the average weight distributions and investigate the connection to the stability condition of the density evolution.

arXiv:1009.1137•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2010•13 citations

MET-LDPC Code Ensembles of Low Code Rates With Exponentially Few Small Weight Codewords

Suhwang Jeong, Jeongseok Ha

This work studies the design of MET-LDPC code ensembles at low code rates with good threshold performances and exponentially few small weight codewords. There was a notable study on the condition, so called the ` t-value condition', for exponentially few small weight codewords. Meanwhile, it was shown that by introducing degree-one variable nodes, the threshold performances of MET-LDPC code ensembles of low rates can be significantly improved. However, the degree-one variable nodes may result in small weight codewords and thus must be carefully introduced to MET-LDPC code ensembles. Despite the importance, the existing t-value condition was developed only for MET-LDPC code ensembles without degree-one variable nodes. This work extends the t-value condition to MET-LDPC code ensembles with degree-one variable nodes, which includes the existing work as a special case. The extended t-value condition provides useful insights into the contributions of degree-one variable nodes to the distribution of small weight codewords. Thus, the results of this work allow us to design MET-LDPC code ensembles of low rates with both good threshold performances and exponentially few small weight codewords. In addition, it will be demonstrated that MET-LDPC codes at finite lengths based on the designed code ensembles have good error-rate performances both in the waterfall and low-error-rate regions.

IEEE Transactions on Communications•Mar 2, 2021•4 citations

Ensemble Weight Enumerators for Protograph LDPC Codes

D. Divsalar

Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•67 citations
Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with minimum distance linearly increasing in code length. Nakasendo et al. derived the condition that code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. In this paper, we derive the condition for three-edge type LDPC code ensembles whose edge-types does not share any variable node and does share all of the check nodes with exponentially decreasing small linear weight codewords. The condition is necessary for the existence of the average relative minimum distance of ensembles. Our method is expected to derive the condition for multi-edge type LDPC codes.
Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with small linear weight codewords exponentially decreasing in code length. Nakasendo et al. derived the condition in which code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. Our conclusion is the same as that of Nakasendo et al., and although Nakasendopsilas method is difficult to apply to more than three edge-types, there is a possibility that our method using Hayman approximation as Di et al. do derives the condition for multi-edge type LDPC codes ensembles.
For a (lambda(x); rho(x)) standard irregular LDPC code ensemble, the growth rate of the average weight distribution for small relative weight omega is given by log(lambda'(0)rho'(1))omega + O(omega2) in the limit of code length n. If lambda'(0)rho'(1) < 1, there exist exponentially few code words of small linear weight, as n tends to infinity. It is known that the condition coincides with the stability condition of density evolution over the erasure channels with the erasure probability 1. In this paper, we show that this is also the case with multi-edge type LDPC (MET-LDPC) codes. MET-LDPC codes are generalized structured LDPC codes introduced by Richardson and Urbanke. The parameter corresponding lambda'(0)rho'(1) appearing in the conditions for MET-LDPC codes is given by the spectral radius of the matrix defined by extended degree distributions.
This work studies the design of MET-LDPC code ensembles at low code rates with good threshold performances and exponentially few small weight codewords. There was a notable study on the condition, so called the ` t-value condition', for exponentially few small weight codewords. Meanwhile, it was shown that by introducing degree-one variable nodes, the threshold performances of MET-LDPC code ensembles of low rates can be significantly improved. However, the degree-one variable nodes may result in small weight codewords and thus must be carefully introduced to MET-LDPC code ensembles. Despite the importance, the existing t-value condition was developed only for MET-LDPC code ensembles without degree-one variable nodes. This work extends the t-value condition to MET-LDPC code ensembles with degree-one variable nodes, which includes the existing work as a special case. The extended t-value condition provides useful insights into the contributions of degree-one variable nodes to the distribution of small weight codewords. Thus, the results of this work allow us to design MET-LDPC code ensembles of low rates with both good threshold performances and exponentially few small weight codewords. In addition, it will be demonstrated that MET-LDPC codes at finite lengths based on the designed code ensembles have good error-rate performances both in the waterfall and low-error-rate regions.
Recently, LDPC codes with projected graph, or protograph structures have been proposed. In this paper, finite length ensemble weight enumerators for LDPC codes with protograph structures are obtained. Asymptotic results are derived as the block size goes to infinity. In particular, we are interested in obtaining ensemble average weight enumerators for protograph LDPC codes which have typical minimum distance that grows linearly with block size. As with irregular ensembles, linear minimum distance property is sensitive to the proportion of degree-2 variable nodes. In this paper, the derived results on ensemble weight enumerators show that linear minimum distance condition on degree distribution of unstructured irregular LDPC codes is a sufficient but not a necessary condition for protograph LDPC codes