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

The IMA volumes in mathematics and its applications

On the Effective Weights of Pseudocodewords for Codes Defined on Graphs with Cycles

G. David Forney, R. Koetter, Frank R. Kschischang, Alex Reznik

Published Jan 1, 2001• 115 citations
Publisher
DOI
10.1007/978-1-4613-0165-3_5

Related papers

Pseudocodeword-free criterion for codes with cycle-free Tanner graph

Wittawat Kositwattanarerk

arXiv:1706.06648•Designs Codes and Cryptography•Mar 23, 2018•1 citation

Pseudocodeword-based Decoding of Quantum Color Codes

July X. Li, Joseph M. Renes, Pascal O. Vontobel

In previous work, we have shown that pseudocodewords can be used to characterize the behavior of decoders not only for classical codes but also for quantum stabilizer codes. With the insights obtained from this pseudocodewords-based analysis, we have also introduced a two-stage decoder based on pseudocodewords for quantum cycle codes that leads to improved decoding performance. In this paper, we consider quantum (stabilizer) color codes and propose a two-stage decoder that is a generalization of the pseudocodeword-based decoder for quantum cycle codes. Our decoder has local operations w.r.t. the underlying graphs, syndrome-weight-dependent computational complexity, and better decoding performance compared with previous approaches for quantum color codes.

arXiv:2010.10845•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•3 citations

On Iterative Decoding of Cycle Codes of Graphs

Gilles Zémor

The IMA volumes in mathematics and its applications•Jan 1, 2001•5 citations

Design and performance of LDPC codes extended with parity-check symbols from a larger alphabet

Elisa Mo, M.A. Armand

This paper describes a method for constructing a certain class of LDPC codes over mixed integer residue rings. These codes are essentially extended LDPC codes where the additional redundant symbols come from a larger alphabet. In particular, we address the effects that zero divisors as edge weights in the Tanner graph of LDPC codes over Z, have, from the pseudocodeword perspective. First, we show that weighting certain edges of a Tanner graph with zero divisors of Z, can reduce the number of pseudocodewords arising from its finite degree covers. Second, we prove that in adding a redundant row to a given parity-check matrix, the smaller the number of zero divisors it contains, the more effective it is in constricting the corresponding fundamental polytope. Moreover, we argue that cycles of length four are not bad provided at least one of the four corresponding edge weights is a zero divisor. The culmination of these findings is a procedure for judiciously adding redundant check nodes to the Tanner graph representation of a mixed- alphabet code such that significant performance improvements under iterative decoding may be obtained.

International Conference on Information, Communications & Signal Processing (ICICS)•Jan 1, 2007•1 citation

Codes on Graphs: A Survey for Algebraists

G. David Forney

Lecture notes in computer science•Jan 1, 1999•1 citation

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
In previous work, we have shown that pseudocodewords can be used to characterize the behavior of decoders not only for classical codes but also for quantum stabilizer codes. With the insights obtained from this pseudocodewords-based analysis, we have also introduced a two-stage decoder based on pseudocodewords for quantum cycle codes that leads to improved decoding performance. In this paper, we consider quantum (stabilizer) color codes and propose a two-stage decoder that is a generalization of the pseudocodeword-based decoder for quantum cycle codes. Our decoder has local operations w.r.t. the underlying graphs, syndrome-weight-dependent computational complexity, and better decoding performance compared with previous approaches for quantum color codes.
This paper describes a method for constructing a certain class of LDPC codes over mixed integer residue rings. These codes are essentially extended LDPC codes where the additional redundant symbols come from a larger alphabet. In particular, we address the effects that zero divisors as edge weights in the Tanner graph of LDPC codes over Z, have, from the pseudocodeword perspective. First, we show that weighting certain edges of a Tanner graph with zero divisors of Z, can reduce the number of pseudocodewords arising from its finite degree covers. Second, we prove that in adding a redundant row to a given parity-check matrix, the smaller the number of zero divisors it contains, the more effective it is in constricting the corresponding fundamental polytope. Moreover, we argue that cycles of length four are not bad provided at least one of the four corresponding edge weights is a zero divisor. The culmination of these findings is a procedure for judiciously adding redundant check nodes to the Tanner graph representation of a mixed- alphabet code such that significant performance improvements under iterative decoding may be obtained.
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.