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

Allerton Conference on Communication, Control, and Computing

A universal theory of pseudocodewords

Nathan Axvig, Emily Price, Eric T. Psota, Deanna Turk, Lance C. Pérez, Judy L. Walker

Published Jan 1, 2007• 6 citations
OpenAlex

Abstract

Abstract — Three types of pseudocodewords for LDPC codes are found in the literature: graph cover pseudocodewords, linear programming pseudocodewords, and computation tree pseudocodewords. In this paper we first review these three notions and known connections between them. We then propose a new decoding rule — universal cover decoding — for LDPC codes. This new decoding rule also has a notion of pseudocodeword attached, and this fourth notion provides a framework in which we can better understand the other three. I.

Related papers

Analysis of Connections Between Pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature-linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.

IEEE Transactions on Information Theory•Aug 24, 2009•24 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

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

Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

Pascal O. Vontobel, R. Koetter

The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes.

arXiv:cs/0512078•Dec 20, 2005•224 citations

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•0 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
Abstract — Three types of pseudocodewords for LDPC codes are found in the literature: graph cover pseudocodewords, linear programming pseudocodewords, and computation tree pseudocodewords. In this paper we first review these three notions and known connections between them. We then propose a new decoding rule — universal cover decoding — for LDPC codes. This new decoding rule also has a notion of pseudocodeword attached, and this fourth notion provides a framework in which we can better understand the other three. I.
The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature-linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.
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.
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.
The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes.
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.
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.