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:1510.06828 · IEEE Transactions on Communications

Construction of Near-Capacity Protograph LDPC Code Sequences With Block-Error Thresholds

Asit Kumar Pradhan, Andrew Thangaraj, Arunkumar Subramanian

Published Nov 12, 2015• 36 citations
arXivHTMLPDF

Abstract

Density evolution for protograph low-density parity-check (LDPC) codes is considered, and it is shown that the message-error rate falls double-exponentially with iterations whenever the degree-2 subgraph of the protograph is cycle-free and noise level is below threshold. Conditions for stability of protograph density evolution are established and related to the structure of the protograph. Using large-girth graphs, sequences of protograph LDPC codes with block-error threshold equal to bit-error threshold and block-error rate falling near-exponentially with blocklength are constructed deterministically. Small-sized protographs are optimized to obtain thresholds near capacity for binary erasure and binary-input Gaussian channels.

DOI
10.1109/tcomm.2015.2500234

Related papers

Deterministic Constructions for Large Girth Protograph LDPC Codes

Asit Kumar Pradhan, Arunkumar Subramanian, Andrew Thangaraj

The bit-error threshold of the standard ensemble of Low Density Parity Check (LDPC) codes is known to be close to capacity, if there is a non-zero fraction of degree-two bit nodes. However, the degree-two bit nodes preclude the possibility of a block-error threshold. Interestingly, LDPC codes constructed using protographs allow the possibility of having both degree-two bit nodes and a block-error threshold. In this paper, we analyze density evolution for protograph LDPC codes over the binary erasure channel and show that their bit-error probability decreases double exponentially with the number of iterations when the erasure probability is below the bit-error threshold and long chain of degree-two variable nodes are avoided in the protograph. We present deterministic constructions of such protograph LDPC codes with girth logarithmic in blocklength, resulting in an exponential fall in bit-error probability below the threshold. We provide optimized protographs, whose block-error thresholds are better than that of the standard ensemble with minimum bit-node degree three. These protograph LDPC codes are theoretically of great interest, and have applications, for instance, in coding with strong secrecy over wiretap channels.

arXiv:1301.6301•Jan 27, 2013•2 citations

Deterministic constructions for large girth protograph LDPC codes

Asit Kumar Pradhan, Arunkumar Subramanian, Andrew Thangaraj

For certain degree-distribution pairs with non-zero fraction of degree-two bit nodes, the bit-error threshold of the standard ensemble of Low Density Parity Check (LDPC) codes is known to be close to capacity. However, the degree-two bit nodes preclude the possibility of a block-error threshold. Interestingly, LDPC codes constructed using protographs allow the possibility of having both degree-two bit nodes and a block-error threshold. In this paper, we analyze density evolution for protograph LDPC codes over the binary erasure channel and show that their bit-error probability decreases double exponentially with the number of iterations when the erasure probability is below the bit-error threshold and long chain of degree-two variable nodes are avoided in the protograph. We present deterministic constructions of such protograph LDPC codes with girth logarithmic in blocklength, resulting in an exponential fall in bit-error probability below the threshold. We provide optimized protographs, whose block-error thresholds are better than that of the standard ensemble with minimum bit-node degree three. These protograph LDPC codes are theoretically of great interest, and have applications, for instance, in coding with strong secrecy over wiretap channels.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•17 citations

Near-capacity protograph doubly-generalized LDPC codes with block thresholds

Asit Kumar Pradhan, Andrew Thangaraj

Protograph doubly-generalized low-density parity-check (DGLDPC) codes, which allow for arbitrary component codes at the variable and check nodes of a protograph, are considered. Exact density evolution is derived over the binary erasure channel. Conditions on the protograph and component codes to ensure equality of block-error threshold and density evolution threshold for large-girth ensembles are established. Conditions for stability of density evolution are derived, and block-error threshold property is extended to binary-input symmetric channels. Optimized low-rate protographs for DGLDPC codes over the erasure channel are presented.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

Protograph LDPC Codes With Block Thresholds: Extension to Degree-One and Generalized Nodes

Asit Kumar Pradhan, Andrew Thangaraj

Protograph low-density-parity-check (LDPC) codes are considered to design near-capacity low-rate codes over the binary erasure channel and the binary additive white Gaussian noise channel. For protographs with degree-one variable nodes and doubly-generalized LDPC (DGLDPC) codes, conditions are derived to ensure the equality of bit-error threshold and block-error threshold. Using this condition, low-rate codes with block-error threshold close to capacity are designed and shown to have better error rate performance than other existing codes.

arXiv:1710.09651•IEEE Transactions on Communications•Aug 14, 2018•9 citations

Threshold upper bounds and optimized design of protograph LDPC codes for the Binary Erasure Channel

S Harikumar, Jayanth Ramesh, Manikandan Srinivasan +1 more

Exact density evolution of protograph Low Density Parity Check (LDPC) codes over the Binary Erasure Channel (BEC) is considered. Upper bounds on the threshold are derived and expressed as single-variable minimizations. A simplified version of the upper bound is expressed in closed form in terms of the degrees of the nodes in the protograph. By maximizing the upper bound, useful conditions are derived for optimizing protographs to get thresholds close to capacity bounds. Using these conditions, a randomized construction method for good small-sized protographs is presented.

International Workshop on Signal Design and its Applications in Communications•Sep 1, 2015•1 citation

Spatially Coupled LDPC Codes Constructed From Protographs

David G. M. Mitchell, Michael Lentmaier, Daniel J. Costello

In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.

arXiv:1407.5366•IEEE Transactions on Information Theory•Jul 8, 2015•298 citations
Density evolution for protograph low-density parity-check (LDPC) codes is considered, and it is shown that the message-error rate falls double-exponentially with iterations whenever the degree-2 subgraph of the protograph is cycle-free and noise level is below threshold. Conditions for stability of protograph density evolution are established and related to the structure of the protograph. Using large-girth graphs, sequences of protograph LDPC codes with block-error threshold equal to bit-error threshold and block-error rate falling near-exponentially with blocklength are constructed deterministically. Small-sized protographs are optimized to obtain thresholds near capacity for binary erasure and binary-input Gaussian channels.
The bit-error threshold of the standard ensemble of Low Density Parity Check (LDPC) codes is known to be close to capacity, if there is a non-zero fraction of degree-two bit nodes. However, the degree-two bit nodes preclude the possibility of a block-error threshold. Interestingly, LDPC codes constructed using protographs allow the possibility of having both degree-two bit nodes and a block-error threshold. In this paper, we analyze density evolution for protograph LDPC codes over the binary erasure channel and show that their bit-error probability decreases double exponentially with the number of iterations when the erasure probability is below the bit-error threshold and long chain of degree-two variable nodes are avoided in the protograph. We present deterministic constructions of such protograph LDPC codes with girth logarithmic in blocklength, resulting in an exponential fall in bit-error probability below the threshold. We provide optimized protographs, whose block-error thresholds are better than that of the standard ensemble with minimum bit-node degree three. These protograph LDPC codes are theoretically of great interest, and have applications, for instance, in coding with strong secrecy over wiretap channels.
For certain degree-distribution pairs with non-zero fraction of degree-two bit nodes, the bit-error threshold of the standard ensemble of Low Density Parity Check (LDPC) codes is known to be close to capacity. However, the degree-two bit nodes preclude the possibility of a block-error threshold. Interestingly, LDPC codes constructed using protographs allow the possibility of having both degree-two bit nodes and a block-error threshold. In this paper, we analyze density evolution for protograph LDPC codes over the binary erasure channel and show that their bit-error probability decreases double exponentially with the number of iterations when the erasure probability is below the bit-error threshold and long chain of degree-two variable nodes are avoided in the protograph. We present deterministic constructions of such protograph LDPC codes with girth logarithmic in blocklength, resulting in an exponential fall in bit-error probability below the threshold. We provide optimized protographs, whose block-error thresholds are better than that of the standard ensemble with minimum bit-node degree three. These protograph LDPC codes are theoretically of great interest, and have applications, for instance, in coding with strong secrecy over wiretap channels.
Protograph doubly-generalized low-density parity-check (DGLDPC) codes, which allow for arbitrary component codes at the variable and check nodes of a protograph, are considered. Exact density evolution is derived over the binary erasure channel. Conditions on the protograph and component codes to ensure equality of block-error threshold and density evolution threshold for large-girth ensembles are established. Conditions for stability of density evolution are derived, and block-error threshold property is extended to binary-input symmetric channels. Optimized low-rate protographs for DGLDPC codes over the erasure channel are presented.
Protograph low-density-parity-check (LDPC) codes are considered to design near-capacity low-rate codes over the binary erasure channel and the binary additive white Gaussian noise channel. For protographs with degree-one variable nodes and doubly-generalized LDPC (DGLDPC) codes, conditions are derived to ensure the equality of bit-error threshold and block-error threshold. Using this condition, low-rate codes with block-error threshold close to capacity are designed and shown to have better error rate performance than other existing codes.
Exact density evolution of protograph Low Density Parity Check (LDPC) codes over the Binary Erasure Channel (BEC) is considered. Upper bounds on the threshold are derived and expressed as single-variable minimizations. A simplified version of the upper bound is expressed in closed form in terms of the degrees of the nodes in the protograph. By maximizing the upper bound, useful conditions are derived for optimizing protographs to get thresholds close to capacity bounds. Using these conditions, a randomized construction method for good small-sized protographs is presented.
In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.