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

International Conference on Information, Communications & Signal Processing (ICICS)

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

Elisa Mo, M.A. Armand

Published Jan 1, 2007• 1 citation
Publisher

Abstract

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.

DOI
10.1109/icics.2007.4449724

Related papers

Impact of Redundant Checks on the LP Decoding Thresholds of LDPC Codes

Louay M. J. Bazzi, Hani Audah

Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger thank. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.

IEEE Transactions on Information Theory•Mar 31, 2015•4 citations

Impact of redundant checks on the LP decoding thresholds of LDPC codes

Louay M. J. Bazzi, Hani Audah

Feldman et al.(2005) asked whether the performance of the LP decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove that for LDPC codes, even if we include all redundant checks, asymptotically there is no gain in the LP decoder threshold on the BSC under certain conditions on the base Tanner graph. First, we show that if the graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant checks in the LP does not significantly improve the threshold in the following sense: for each constant delta>0, there is a constant k>0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most delta upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies a rigidity condition, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the LLRs of the correct variables are arbitrarily small. By building on the work of Feldman et al.(2007) and Viderman(2013), we show that asymptotic strength follows from sufficiently large expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular graphs.

arXiv:1411.7554•Nov 27, 2014•0 citations

Pseudocodeword-Free Criterion for Codes with Cycle-Free Tanner Graph

Wittawat Kositwattanarerk

Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.

arXiv:1706.06648•Jun 20, 2017•0 citations

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.

•Sep 15, 2022•0 citations

Impact of redundant checks on the LP decoding thresholds of LDPC codes

Louay M. J. Bazzi, Hani Audah

Feldman et al. [1] asked whether the performance of the Linear Programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for LDPC codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the Binary Symmetric Channel (BSC) under certain conditions on the base Tanner graph. First, we show that if the base Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense: for each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [2] and its recent improvement by Viderman [3], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•0 citations

Structured LDPC Codes over Integer Residue Rings

Elisa Mo, M.A. Armand

This paper presents a new class of low-density parity-check (LDPC) codes over represented by regular, structured Tanner graphs. These graphs are constructed using Latin squares defined over a multiplicative group of a Galois ring, rather than a finite field. Our approach yields codes for a wide range of code rates and more importantly, codes whose minimum pseudocodeword weights equal their minimum Hamming distances. Simulation studies show that these structured codes, when transmitted using matched signal sets over an additive-white-Gaussian-noise channel, can outperform their random counterparts of similar length and rate.

EURASIP Journal on Wireless Communications and Networking•Jun 12, 2008•1 citation
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.
Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger thank. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
Feldman et al.(2005) asked whether the performance of the LP decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove that for LDPC codes, even if we include all redundant checks, asymptotically there is no gain in the LP decoder threshold on the BSC under certain conditions on the base Tanner graph. First, we show that if the graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant checks in the LP does not significantly improve the threshold in the following sense: for each constant delta>0, there is a constant k>0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most delta upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies a rigidity condition, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the LLRs of the correct variables are arbitrarily small. By building on the work of Feldman et al.(2007) and Viderman(2013), we show that asymptotic strength follows from sufficiently large expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular graphs.
Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.
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.
Feldman et al. [1] asked whether the performance of the Linear Programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for LDPC codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the Binary Symmetric Channel (BSC) under certain conditions on the base Tanner graph. First, we show that if the base Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense: for each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [2] and its recent improvement by Viderman [3], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
This paper presents a new class of low-density parity-check (LDPC) codes over represented by regular, structured Tanner graphs. These graphs are constructed using Latin squares defined over a multiplicative group of a Galois ring, rather than a finite field. Our approach yields codes for a wide range of code rates and more importantly, codes whose minimum pseudocodeword weights equal their minimum Hamming distances. Simulation studies show that these structured codes, when transmitted using matched signal sets over an additive-white-Gaussian-noise channel, can outperform their random counterparts of similar length and rate.