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

arXiv:cs/0510009

Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal

Published Oct 3, 2005• 0 citations
arXivHTMLPDF

Abstract

We present a tree-based construction of LDPC codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a $d$-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees $d=p^s$ and $d = p^s+1$, for $p$ a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight for $p$-ary LDPC codes. Treating these codes as $p$-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite geometry LDPC codes where $p > 2$.

DOI
10.48550/arxiv.cs/0510009

Related papers

Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal

We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a$d$-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees$d=p^s$and$d = p^s+1$, for$p$a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight for$p$-ary LDPC codes. Treating these codes as$p$-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes where$p > 2$.

IEEE Transactions on Information Theory•Apr 1, 2007•18 citations

Tree-based construction of LDPC codes

Deepak Sridhara, Christine A. Kelley, Joachim Rosenthal

We present a construction of LDPC codes that have minimum pseudocodeword weight equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a d-regular tree for a fixed number of layers and employing a connection algorithm based on mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d = psand d = ps+ 1, for p a prime, one of which includes the well-known finite-geometry-based LDPC codes

arXiv:cs/0506042•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•2 citations

Iterative Construction of Regular LDPC Codes from Independent Tree-Based Minimum Distance Bounds

Eric T. Psota, Lance C. Pérez

An independent tree-based method for lower bounding the minimum distance of low-density parity-check (LDPC) codes is presented. This lower-bound is then used as the decision criterion during the iterative construction of regular LDPC codes. The new construction algorithm results in LDPC codes with greater girth and improved minimum-distance bounds when compared to regular LDPC codes constructed using the progressive edge-growth (PEG) construction and the approximate cycle extrinsic message degree (ACE)-constrained PEG construction. Simulation results of codes constructed with the new method show improved performance on the additive white Gaussian noise channel at moderate signal-to-noise ratios.

IEEE Communications Letters•Jan 21, 2011•5 citations

Pseudocodeword weights for non-binary LDPC codes

Christine Kelley, Deepak Sridhara, Joachim Rosenthal

Pseudocodewords of q-ary LDPC codes are examined and the weight of a pseudocodeword on the q-ary symmetric channel is defined. The weight definition of a pseudocodeword on the AWGN channel is also extended to two-dimensional q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on these channels

arXiv:cs/0605118•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•8 citations

Pseudocodeword weights for non-binary LDPC codes

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal

Pseudocodewords of q-ary LDPC codes are examined and the weight of a pseudocodeword on the q-ary symmetric channel is defined. The weight definition of a pseudocodeword on the AWGN channel is also extended to two-dimensional q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on these channels.

•Jan 1, 2006•15 citations

LDPC Codes From Generalized Polygons

Zhouding Liu, Dimitris A. Pados

We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation.

IEEE Transactions on Information Theory•Oct 24, 2005•41 citations
We present a tree-based construction of LDPC codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a ddd-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d=psd=p^sd=ps and d=ps+1d = p^s+1d=ps+1, for ppp a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight for ppp-ary LDPC codes. Treating these codes as ppp-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite geometry LDPC codes where p>2p > 2p>2.
We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating addd-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degreesd=psd=p^sd=psandd=ps+1d = p^s+1d=ps+1, forpppa prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes; the other codes presented are new. We also present some bounds on pseudocodeword weight forppp-ary LDPC codes. Treating these codes asppp-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes wherep>2p > 2p>2.
An independent tree-based method for lower bounding the minimum distance of low-density parity-check (LDPC) codes is presented. This lower-bound is then used as the decision criterion during the iterative construction of regular LDPC codes. The new construction algorithm results in LDPC codes with greater girth and improved minimum-distance bounds when compared to regular LDPC codes constructed using the progressive edge-growth (PEG) construction and the approximate cycle extrinsic message degree (ACE)-constrained PEG construction. Simulation results of codes constructed with the new method show improved performance on the additive white Gaussian noise channel at moderate signal-to-noise ratios.
We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation.