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

Absdet-pseudo-codewords and perm-pseudo-codewords: Definitions and properties

Roxana Smarandache, Pascal O. Vontobel

Published Jun 1, 2009• 17 citations
arXivHTMLPDF

Abstract

The linear-programming decoding performance of a binary linear code crucially depends on the structure of the fundamental cone of the parity-check matrix that describes the code. Towards a better understanding of fundamental cones and the vectors therein, we introduce the notion of absdet-pseudo-codewords and perm-pseudo-codewords: we give the definitions, we discuss some simple examples, and we list some of their properties.

DOI
10.1109/isit.2009.5205910

Related papers

On minimal pseudo-codewords

Roxana Smarandache

The performance of linear-programming decoding of a binary linear code described by a parity-check matrix depends on the set of pseudo-codewords associated to this matrix and in particular, on the set of minimal pseudo-codewords. This paper attempts to provide an algebraic characterization of the minimal pseudo-codewords. It also provides a connection between the fundamental cone of a Tanner graph and the fundamental cone of its Forney-style factor graph.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•2 citations

Characterizations of Pseudo-Codewords of LDPC Codes

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

An important property of high-performance, low complexity codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message passing algorithms and decoding based on linear programming, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so called fundamental cone in Euclidean space which is a function of a given parity check matrix of a code, rather than of the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental polytope as the Newton polytope of the Hashimoto edge zeta function of the underlying graph.

arXiv:cs/0508049•Aug 9, 2005•22 citations

Characterization of Graph-cover Pseudocodewords of Codes over $F_3$

Vitaly Skachek

Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becom is more involved. In this work, a characterization of the fundamental cone for codes over $F_3$ is discussed.

arXiv:1007.3808•Jul 22, 2010•5 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

Characterization of graph-cover pseudocodewords of codes over F3

Vitaly Skachek

Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becomes more involved. In this work, a characterization of the fundamental cone for codes over F3is discussed.

IEEE Information Theory Workshop (ITW)•Aug 1, 2010•8 citations

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
The linear-programming decoding performance of a binary linear code crucially depends on the structure of the fundamental cone of the parity-check matrix that describes the code. Towards a better understanding of fundamental cones and the vectors therein, we introduce the notion of absdet-pseudo-codewords and perm-pseudo-codewords: we give the definitions, we discuss some simple examples, and we list some of their properties.
An important property of high-performance, low complexity codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message passing algorithms and decoding based on linear programming, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so called fundamental cone in Euclidean space which is a function of a given parity check matrix of a code, rather than of the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental polytope as the Newton polytope of the Hashimoto edge zeta function of the underlying graph.
Characterization of Graph-cover Pseudocodewords of Codes over F3F_3F3​
Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becom is more involved. In this work, a characterization of the fundamental cone for codes over F3F_3F3​ is discussed.
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.
Linear-programming pseudocodewords play a pivotal role in our understanding of the linear-programming decoding algorithms. These pseudocodewords are known to be equivalent to the graph-cover pseudocodewords. The latter pseudocodewords, when viewed as points in the multidimensional Euclidean space, lie inside a fundamental cone. This fundamental cone depends on the choice of a parity-check matrix of a code, rather than on the choice of the code itself. The cone does not depend on the channel, over which the code is employed. The knowledge of the boundaries of the fundamental cone could help in studying various properties of the pseudocodewords, such as their minimum pseudoweight, pseudoredundancy of the codes, etc. For the binary codes, the full characterization of the fundamental cone was derived by Koetter et al. However, if the underlying alphabet is large, such characterization becomes more involved. In this work, a characterization of the fundamental cone for codes over F3is discussed.
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.