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

Pseudocodewords from Bethe permanents

Roxana Smarandache

Published Jul 1, 2013• 4 citations
Publisher

Abstract

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 analyze some important cases for which the conjecture is true and investigate the obtained families of pseudocodewords.
DOI
10.1109/isit.2013.6620588

Related papers

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

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

Sarah Elghraoui

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.

•Aug 6, 2013•0 citations

On the Pseudocodeword Redundancy

Jens Zumbrägel, Mark F. Flanagan, Vitaly Skachek

We define the AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance. We show that most codes do not have a finite pseudocodeword redundancy. We also provide bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs.

arXiv:1001.1705•Jan 11, 2010•1 citation

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

Pseudoredundancy for the Bit-Flipping Algorithm

Jens Zumbrägel

The analysis of the decoding failure rate of the bit-flipping algorithm has received increasing attention. For a binary linear code we consider the minimum number of rows in a parity-check matrix such that the bit-flipping algorithm is able to correct errors up to the minimum distance without any decoding failures. We initiate a study of this bit-flipping redundancy, which is akin to the stopping set, trapping set or pseudocodeword redundancy of binary linear codes, and focus in particular on codes based on finite geometries.

arXiv:2402.01403•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•2 citations

Characterizations of pseudo-codewords of (low-density) parity-check codes

R. Koetter, Wen-Ching W. Li, Pascal O. Vontobel +1 more

arXiv:cs/0508049•Advances in Mathematics•Jan 9, 2007•68 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.
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.
The analysis of the decoding failure rate of the bit-flipping algorithm has received increasing attention. For a binary linear code we consider the minimum number of rows in a parity-check matrix such that the bit-flipping algorithm is able to correct errors up to the minimum distance without any decoding failures. We initiate a study of this bit-flipping redundancy, which is akin to the stopping set, trapping set or pseudocodeword redundancy of binary linear codes, and focus in particular on codes based on finite geometries.