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.

arXiv:1411.7554•IEEE Transactions on Information Theory•Mar 31, 2015•5 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.

•Jan 1, 2006•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

Algebraic Constructions of Girth-Eight Quasi-Cyclic Matrices with a Multitude of Redundant Rows

Guohua Zhang, Haiyang Liu, Yi Fang

The absence of small cycles in the Tanner graph and the presence of redundant rows in the parity-check matrix (PCM) are two main tactics to improve the decoding performance of a quasi-cyclic (QC) low-density parity-check (LDPC) code from the construction point of view. Existing systematic methods to yield a PCM with a multitude of redundant rows impose very severe restrictions on the circulant size and guarantee the elimination of only 4-cycles. By exploiting the greatest-common-divisor (GCD) framework, several existing methods are identified and two new methods are proposed to generate PCMs with relatively flexible circulant sizes, a considerable number of redundant rows and no 4-cycles and 6-cycles in the associated Tanner graphs. Moreover, the rank of the PCM associated with each of these methods is theoretically proved for odd circulant sizes. Simulation results show that, the proposed QC-LDPC codes can achieve better decoding performance compared with those from the progressive-edge-growth (PEG) and search-based symmetrical methods whose PCMs contain basically no redundant rows.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2026•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

Increasing the local girth of irregular low-density parity-check codes based on degree-spectrum analysis

Francis C. M. Lau, Wai M. Tam, Chi Kong Tse

A low-density parity-check (LDPC) code can be described by a Tanner graph composed of symbol nodes and check nodes. Short cycles in the Tanner graph should be avoided because such cycles will degrade the performance of the decoder and hence increase the error rate. In most of the circumstances, cycles of length 4 can be totally eliminated in the Tanner graph when the LDPC code has been designed properly. Locally, for each variable node in the Tanner graph, the girth may take the value of 6 or 8, or even higher. In this study, the authors attempt to increase the local girths of a Tanner graph with an aim to improving the error performance of the code. The authors propose and analyse the ‘degree spectrum’ of the symbol nodes connecting to each of the check nodes. Based on the analysis, the authors can determine if the local girths can be further increased. The authors also propose simple ways to construct codes with higher local girths. Finally, the authors show the characteristics and the error performance of the codes constructed with the proposed methods.

IET Communications•Jul 22, 2011•3 citations
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.
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.
The absence of small cycles in the Tanner graph and the presence of redundant rows in the parity-check matrix (PCM) are two main tactics to improve the decoding performance of a quasi-cyclic (QC) low-density parity-check (LDPC) code from the construction point of view. Existing systematic methods to yield a PCM with a multitude of redundant rows impose very severe restrictions on the circulant size and guarantee the elimination of only 4-cycles. By exploiting the greatest-common-divisor (GCD) framework, several existing methods are identified and two new methods are proposed to generate PCMs with relatively flexible circulant sizes, a considerable number of redundant rows and no 4-cycles and 6-cycles in the associated Tanner graphs. Moreover, the rank of the PCM associated with each of these methods is theoretically proved for odd circulant sizes. Simulation results show that, the proposed QC-LDPC codes can achieve better decoding performance compared with those from the progressive-edge-growth (PEG) and search-based symmetrical methods whose PCMs contain basically no redundant rows.
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.
A low-density parity-check (LDPC) code can be described by a Tanner graph composed of symbol nodes and check nodes. Short cycles in the Tanner graph should be avoided because such cycles will degrade the performance of the decoder and hence increase the error rate. In most of the circumstances, cycles of length 4 can be totally eliminated in the Tanner graph when the LDPC code has been designed properly. Locally, for each variable node in the Tanner graph, the girth may take the value of 6 or 8, or even higher. In this study, the authors attempt to increase the local girths of a Tanner graph with an aim to improving the error performance of the code. The authors propose and analyse the ‘degree spectrum’ of the symbol nodes connecting to each of the check nodes. Based on the analysis, the authors can determine if the local girths can be further increased. The authors also propose simple ways to construct codes with higher local girths. Finally, the authors show the characteristics and the error performance of the codes constructed with the proposed methods.