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:1410.1627

New Results on the Pseudoredundancy

Zihui Liu, Jens Zumbrägel, Marcus Greferath, Xin-Wen Wu

Published Oct 7, 2014• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1410.1627

Related papers

Notes on the pseudoredundancy

Zihui Liu, Jens Zumbrägel, Marcus Greferath +1 more

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 some upper bounds on the pseudoredundancies of certain codes with repeated coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•1 citation

On the Pseudocodeword Redundancy of Binary Linear Codes

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

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

arXiv:1103.3641•IEEE Transactions on Information Theory•Apr 5, 2012•21 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•0 citations

On the pseudocodeword redundancy

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

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

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

Exploration of AWGNC and BSC Pseudocodeword Redundancy

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

The AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code is defined as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. This paper provides new results on the AWGNC, BSC, and max-fractional pseudocodeword redundancies of codes. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Also, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

arXiv:1005.3486•May 19, 2010•0 citations

On the pseudocodeword weight and parity-check matrix redundancy of linear codes

Christine A. Kelley, Deepak Sridhara

The minimum pseudocodeword weightwminof a linear graph-based code is more influential in determining decoding performance when decoded via iterative and linear programming decoding algorithms than the classical minimum distancedminunder standard maximum-likelihood decoding Moreover, unlike the minimum distance which is unique to the code regardless of representation, the set of pseudocodewords, and therefore also the minimum pseudocodeword weight, depends on the graph representation used in decoding as well as on the communication channel. This means that a judicious choice of parity-check matrix is crucial for realizing the best potential of any graph-based code. In this paper, we introduce the notion ofpseudoweightredundancyfor the memoryless binary symmetric channel (BSC). Analogous to the stopping redundancy in the literature, this parameter gives the smallest number of rows needed for a parity-check matrix to havedmin=wmin. We provide some upper bounds on the BSC-pseudoweight redundancy and illustrate the concept with some results for Hamming codes, tree-based and finite geometry LDPC codes, Reed-Muller codes and Hadamard codes.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•12 citations
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.
For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.
The AWGNC, BSC, and max-fractional pseudocodeword redundancy of a code is defined as the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. This paper provides new results on the AWGNC, BSC, and max-fractional pseudocodeword redundancies of codes. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Also, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.
The minimum pseudocodeword weightwminof a linear graph-based code is more influential in determining decoding performance when decoded via iterative and linear programming decoding algorithms than the classical minimum distancedminunder standard maximum-likelihood decoding Moreover, unlike the minimum distance which is unique to the code regardless of representation, the set of pseudocodewords, and therefore also the minimum pseudocodeword weight, depends on the graph representation used in decoding as well as on the communication channel. This means that a judicious choice of parity-check matrix is crucial for realizing the best potential of any graph-based code. In this paper, we introduce the notion ofpseudoweightredundancyfor the memoryless binary symmetric channel (BSC). Analogous to the stopping redundancy in the literature, this parameter gives the smallest number of rows needed for a parity-check matrix to havedmin=wmin. We provide some upper bounds on the BSC-pseudoweight redundancy and illustrate the concept with some results for Hamming codes, tree-based and finite geometry LDPC codes, Reed-Muller codes and Hadamard codes.