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/0605118 · IEEE International Symposium on Information Theory (ISIT)

Pseudocodeword weights for non-binary LDPC codes

Christine Kelley, Deepak Sridhara, Joachim Rosenthal

Published Jul 1, 2006• 8 citations
arXivHTMLPDF

Abstract

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

DOI
10.1109/isit.2006.262072

Related papers

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

On Minimal Pseudocodewords of Binary Hamming Codes

Haiyang Liu, Xiaopeng Jiao, Lianrong Ma

Pseudocodewords, and in particular minimal pseudocodewords, play an important role in understanding the performance of linear programming (LP) decoding. In this paper, we investigate minimal pseudocodewords of binary Hamming codes described by full-rank parity-check matrices. We first provide some general results on minimal pseudocodewords with support size 3 of a binary parity-check matrix. We also prove a lower bound on the minimum binary symmetric channel (BSC) pseudoweight of a binary parity-check matrix. Then we prove that a full-rank parity-check matrix of a binary Hamming code has minimal pseudocodewords of certain types whose support sizes are larger than 3. Interestingly enough, the BSC pseudoweight of all these minimal pseudocodewords is 2. Using this fact as well as the above-mentioned lower bound, we further prove that a full-rank parity-check matrix of a binary Hamming code has minimum BSC pseudoweight 2. Moreover, the additive white Gaussian noise channel (AWGNC) pseudoweight of all these minimal pseudocodewords is 3. Based on numerical observations, we conjecture that a full-rank parity-check matrix of a binary Hamming code has minimum AWGNC pseudoweight 3. Finally, we provide more properties of a subset of minimal pseudocodewords of a full-rank parity-check matrix of a binary Hamming code.

IEEE Transactions on Information Theory•Jan 29, 2025•0 citations

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$.

arXiv:cs/0510009•IEEE Transactions on Information Theory•Apr 1, 2007•18 citations

New Results on the Pseudoredundancy

Zihui Liu, Jens Zumbrägel, Marcus Greferath +1 more

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

arXiv:1410.1627•Oct 7, 2014•1 citation

Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation

Ge Li, I.J. Fair, Witold A. Krzymień

This paper extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).

IEEE Transactions on Information Theory•Feb 26, 2009•82 citations

Pseudocodewords of Tanner Graphs

Christine A. Kelley, Deepak Sridhara

This paper presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value$t$that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.

arXiv:cs/0504013•IEEE Transactions on Information Theory•Nov 1, 2007•87 citations
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
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.
Pseudocodewords, and in particular minimal pseudocodewords, play an important role in understanding the performance of linear programming (LP) decoding. In this paper, we investigate minimal pseudocodewords of binary Hamming codes described by full-rank parity-check matrices. We first provide some general results on minimal pseudocodewords with support size 3 of a binary parity-check matrix. We also prove a lower bound on the minimum binary symmetric channel (BSC) pseudoweight of a binary parity-check matrix. Then we prove that a full-rank parity-check matrix of a binary Hamming code has minimal pseudocodewords of certain types whose support sizes are larger than 3. Interestingly enough, the BSC pseudoweight of all these minimal pseudocodewords is 2. Using this fact as well as the above-mentioned lower bound, we further prove that a full-rank parity-check matrix of a binary Hamming code has minimum BSC pseudoweight 2. Moreover, the additive white Gaussian noise channel (AWGNC) pseudoweight of all these minimal pseudocodewords is 3. Based on numerical observations, we conjecture that a full-rank parity-check matrix of a binary Hamming code has minimum AWGNC pseudoweight 3. Finally, we provide more properties of a subset of minimal pseudocodewords of a full-rank parity-check matrix of a binary Hamming code.
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.
The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.
This paper extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).
This paper presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite valuetttthat is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.