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

Pseudocodewords of LDPC Codes from the permanent and Bethe permanent and intended for the Department of Mathematics and Statistics

Sarah Elghraoui

Published Aug 6, 2013• 0 citations
OpenAlex

Abstract

This work is focused on the structure and nature of the decoding failures of low-density parity-check (LDPC) codes, namely, pseudocodewords. These (pseudocodewords) may come from either linear programming (LP) decoding or message-passing iterative decoding (MPID) algorithms for LDPC codes. Since the former decoding algorithm is more amenable to analysis, our focus is on pseudocodewords associated with it. There is no loss of generality because it can be shown that the two algorithms are equivalent. We state the theorem and proof showing that the perm-vector associated to a code where the components are the permanents of sub-matrices of a parity-check matrix is in fact a pseudocodeword. The calculation of the permanent of a matrix is known to be in the complexity class #P, that is, the set of the counting problems associated with the decision problems in the class NP, hence the interest in the Bethe permanent as introduced by Vontobel. Smarandache proves that: 1) vectors whose components are the Bethe-permanent of certain sub-matrices and 1) degree-M Bethe perm-vectors are both pseudocodewords. This work seeks to be a self-contained introduction to the subject, from the precise definition of pseudocodewords to examples involving their creation from permanent and Bethe perm-vectors. Future work would require precisely identifying how these pseudocodewords may contribute as a bound for the fundamental cone.

Related papers

Pseudocodewords of quantum, quasi-cyclic, and spatially-coupled LDPC codes: a fundamental cone perspective

Wittawat Kositwattanarerk, Gretchen L. Matthews, Emily McMillon +1 more

While low-density parity-check (LDPC) codes are near capacity-achieving when paired with iterative decoders, these decoders may not output a codeword due to the existence of pseudocodewords. Thus, pseudocodewords have been studied to give insight into the performance of modern decoders including iterative and linear programming decoders. These pseudocodewords are found to be dependent on the parity-check matrix of the code and the particular decoding algorithm used. In this paper, we consider LP decoding, which has been linked to graph cover decoding, providing functions which capture these pseudocodewords. In particular, we analyze the underlying structure of pseudocodewords from quantum stabilizer codes that arise from LP decoding, quasi-cyclic LDPC codes, and spatially-coupled LDPC codes.

arXiv:2512.02941•Dec 2, 2025•1 citation

Pseudocodewords of Parity-Check Codes Over Fields of Prime Cardinality

Wittawat Kositwattanarerk, Gretchen L. Matthews

This paper considers pseudocodewords of lowdensity parity-check codes over alphabets with prime cardinality p for use over the p-ary symmetric channel. Pseudocodewords are decoding algorithm outputs that may not be legitimate codewords. Here, we consider pseudocodewords arising from graph cover decoding and linear programming decoding. For codes over the binary alphabet, such pseudocodewords correspond to rational points of the fundamental polytope. They can be characterized via the fundamental cone, which is the conic hull of the fundamental polytope; the pseudocodewords are precisely those integer vectors within the fundamental cone that reduce modulo 2 to a codeword. In this paper, we determine a set of conditions that pseudocodewords of codes over Fp, the finite field of prime cardinality p, must satisfy. To do so, we introduce a class of critical multisets and a mapping, which associates a real number to each pseudocodeword over Fp. The real numbers associated with pseudocodewords are subject to lower bounds imposed by the critical multisets. The inequalities are given in terms of the parity-check matrix entries and critical multisets. This gives a necessary and sufficient condition for pseudocodewords of codes over F2and F3and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F3are found as a Hilbert basis for the lifted fundamental cone.

IEEE Transactions on Information Theory•Jun 23, 2014•0 citations

Pseudocodewords, Expander Graphs, and the Algebraic Construction of Low-density Parity-check Codes

Christine A. Kelley

In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.

•Jan 1, 2006•0 citations

A Universal Theory of Decoding and Pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)

•Jan 1, 2008•2 citations

Pseudocodewords of Parity-Check Codes

Wittawat Kositwattanarerk

The success of modern algorithms for the decoding problem such as message-passing iterative decoding and linear programming decoding lies in their local nature. This feature allows the algorithms to be extremely fast and capable of correcting more errors than guaranteed by the classical minimum distance of the code. Nonetheless, the performance of these decoders depends crucially on the Tanner graph representation of the code. In order to understand this choice of representation, we need to analyze the pseudocodewords of the Tanner graph of a code. These pseudocodewords are outputs of local decoding algorithms which may not be legitimate codewords. In this dissertation, we introduce a lifted fundamental cone and show that there is a one-to-one correspondence between graph cover pseudocodewords of a binary code and integer points in the lifted fundamental cone. We use this fact to prove the rationality of the generating function of the pseudocodewords for a general binary parity-check code. Our approach also yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Understanding irreducible pseudocodewords is crucial to determining the best representation of a code. Moreover, combining these techniques with the recent characterization of fundamental cone over F_3, we can analyze ternary parity-check codes. Finally, we make progress in the study of more general nonbinary codes by determining constraints satisfied by all pseudocodewords of a code over F_p where p is prime.

•Jan 1, 2011•0 citations

Pseudocodewords from Bethe Permanents

Roxana Smarandache

It was recently conjectured that a vector with components equal to the Bethe permanent of certain submatrices of a parity-check matrix is a pseudocodeword. In this paper we prove a stronger version of this conjecture for some important cases and investigate the families of pseudocodewords obtained by using the Bethe permanent. We also highlight some interesting properties of the permanent of block matrices and their effects on pseudocodewords.

arXiv:1112.4625•Dec 20, 2011•4 citations
This work is focused on the structure and nature of the decoding failures of low-density parity-check (LDPC) codes, namely, pseudocodewords. These (pseudocodewords) may come from either linear programming (LP) decoding or message-passing iterative decoding (MPID) algorithms for LDPC codes. Since the former decoding algorithm is more amenable to analysis, our focus is on pseudocodewords associated with it. There is no loss of generality because it can be shown that the two algorithms are equivalent. We state the theorem and proof showing that the perm-vector associated to a code where the components are the permanents of sub-matrices of a parity-check matrix is in fact a pseudocodeword. The calculation of the permanent of a matrix is known to be in the complexity class #P, that is, the set of the counting problems associated with the decision problems in the class NP, hence the interest in the Bethe permanent as introduced by Vontobel. Smarandache proves that: 1) vectors whose components are the Bethe-permanent of certain sub-matrices and 1) degree-M Bethe perm-vectors are both pseudocodewords. This work seeks to be a self-contained introduction to the subject, from the precise definition of pseudocodewords to examples involving their creation from permanent and Bethe perm-vectors. Future work would require precisely identifying how these pseudocodewords may contribute as a bound for the fundamental cone.
While low-density parity-check (LDPC) codes are near capacity-achieving when paired with iterative decoders, these decoders may not output a codeword due to the existence of pseudocodewords. Thus, pseudocodewords have been studied to give insight into the performance of modern decoders including iterative and linear programming decoders. These pseudocodewords are found to be dependent on the parity-check matrix of the code and the particular decoding algorithm used. In this paper, we consider LP decoding, which has been linked to graph cover decoding, providing functions which capture these pseudocodewords. In particular, we analyze the underlying structure of pseudocodewords from quantum stabilizer codes that arise from LP decoding, quasi-cyclic LDPC codes, and spatially-coupled LDPC codes.
This paper considers pseudocodewords of lowdensity parity-check codes over alphabets with prime cardinality p for use over the p-ary symmetric channel. Pseudocodewords are decoding algorithm outputs that may not be legitimate codewords. Here, we consider pseudocodewords arising from graph cover decoding and linear programming decoding. For codes over the binary alphabet, such pseudocodewords correspond to rational points of the fundamental polytope. They can be characterized via the fundamental cone, which is the conic hull of the fundamental polytope; the pseudocodewords are precisely those integer vectors within the fundamental cone that reduce modulo 2 to a codeword. In this paper, we determine a set of conditions that pseudocodewords of codes over Fp, the finite field of prime cardinality p, must satisfy. To do so, we introduce a class of critical multisets and a mapping, which associates a real number to each pseudocodeword over Fp. The real numbers associated with pseudocodewords are subject to lower bounds imposed by the critical multisets. The inequalities are given in terms of the parity-check matrix entries and critical multisets. This gives a necessary and sufficient condition for pseudocodewords of codes over F2and F3and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F3are found as a Hilbert basis for the lifted fundamental cone.
In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.
The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)
The success of modern algorithms for the decoding problem such as message-passing iterative decoding and linear programming decoding lies in their local nature. This feature allows the algorithms to be extremely fast and capable of correcting more errors than guaranteed by the classical minimum distance of the code. Nonetheless, the performance of these decoders depends crucially on the Tanner graph representation of the code. In order to understand this choice of representation, we need to analyze the pseudocodewords of the Tanner graph of a code. These pseudocodewords are outputs of local decoding algorithms which may not be legitimate codewords. In this dissertation, we introduce a lifted fundamental cone and show that there is a one-to-one correspondence between graph cover pseudocodewords of a binary code and integer points in the lifted fundamental cone. We use this fact to prove the rationality of the generating function of the pseudocodewords for a general binary parity-check code. Our approach also yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Understanding irreducible pseudocodewords is crucial to determining the best representation of a code. Moreover, combining these techniques with the recent characterization of fundamental cone over F_3, we can analyze ternary parity-check codes. Finally, we make progress in the study of more general nonbinary codes by determining constraints satisfied by all pseudocodewords of a code over F_p where p is prime.