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

Allerton Conference on Communication, Control, and Computing

Optimized puncturing and shortening distributions for nonbinary LDPC codes over the binary erasure channel

Demijan Klinc, Jeongseok Ha, Steven W. McLaughlin

Published Sep 1, 2008• 8 citations
Publisher

Abstract

This paper investigates optimal puncturing and shortening distributions for nonbinary LDPC codes over the binary erasure channel (BEC). The analysis is done by means of density evolution and optimal distributions are found with differential evolution. We show that puncturing or shortening entire variable nodes results in bad performance; instead, for best performance, puncturing and shortening distributions have to be designed carefully, where generally, most variable nodes are punctured/shortened only partially. Our results indicate that properly designed punctured and shortened nonbinary LDPC codes can maintain a very small gap to capacity through a wide range of rates.

DOI
10.1109/allerton.2008.4797675

Related papers

Optimized puncturing distributions for irregular non-binary LDPC codes

Matteo Gorgoglione, Valentin Savin, David Declercq

In this paper we design non-uniform bit-wise puncturing distributions for irregular non-binary LDPC (NB-LDPC) codes. The puncturing distributions are optimized by minimizing the decoding threshold of the punctured LDPC code, the threshold being computed with a Monte-Carlo implementation of Density Evolution. First, we show that Density Evolution computed with Monte-Carlo simulations provides accurate (very close) and precise (small variance) estimates of NB-LDPC code ensemble thresholds. Based on the proposed method, we analyze several puncturing distributions for regular and semi-regular codes, obtained either by clustering punctured bits, or spreading them over the symbol-nodes of the Tanner graph. Finally, optimized puncturing distributions for non-binary LDPC codes with small maximum degree are presented, which exhibit a gap between 0.2 and 0.5 dB to the channel capacity, for punctured rates varying from 0.5 to 0.9.

arXiv:1004.5216•International Symposium on Information Theory and its Applications•Oct 1, 2010•19 citations

Rate-Compatible Puncturing of Finite-Length Low-Density Parity-Check Codes

Badri N. Vellambi, R. Badri, Faramarz Fekri

In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.

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

Construction of Optimal Puncturing of Low-Density Parity-Check Codes

S. Suresh Kumar, Manju Rajaram

Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.

CiiT international journal of fuzzy systems•Jan 1, 2014•0 citations

Design of LDPC codes for the q-ary partial erasure channel

Rami Cohen, Yuval Cassuto

In this paper, we discuss practical design of low-density parity-check (LDPC) codes for the q-ary partial erasure channel (QPEC). This channel is an extension of the binary erasure channel (BEC), where partial information on the output is available. We provide a linear programming (LP) optimization for the design of good degree distributions, and compare our code design results to codes obtained using an LP optimization formulated for the BEC. We show superior performance in terms of code rate and complexity, when designing an LDPC code for a desired decoding threshold.

IEEE Information Theory Workshop (ITW)•Apr 1, 2015•0 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

Randomly Punctured LDPC Codes

David G. M. Mitchell, Michael Lentmaier, Alí Emre Pusane +1 more

In this paper, we present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.

IEEE Journal on Selected Areas in Communications•Dec 11, 2015•48 citations
This paper investigates optimal puncturing and shortening distributions for nonbinary LDPC codes over the binary erasure channel (BEC). The analysis is done by means of density evolution and optimal distributions are found with differential evolution. We show that puncturing or shortening entire variable nodes results in bad performance; instead, for best performance, puncturing and shortening distributions have to be designed carefully, where generally, most variable nodes are punctured/shortened only partially. Our results indicate that properly designed punctured and shortened nonbinary LDPC codes can maintain a very small gap to capacity through a wide range of rates.
In this paper we design non-uniform bit-wise puncturing distributions for irregular non-binary LDPC (NB-LDPC) codes. The puncturing distributions are optimized by minimizing the decoding threshold of the punctured LDPC code, the threshold being computed with a Monte-Carlo implementation of Density Evolution. First, we show that Density Evolution computed with Monte-Carlo simulations provides accurate (very close) and precise (small variance) estimates of NB-LDPC code ensemble thresholds. Based on the proposed method, we analyze several puncturing distributions for regular and semi-regular codes, obtained either by clustering punctured bits, or spreading them over the symbol-nodes of the Tanner graph. Finally, optimized puncturing distributions for non-binary LDPC codes with small maximum degree are presented, which exhibit a gap between 0.2 and 0.5 dB to the channel capacity, for punctured rates varying from 0.5 to 0.9.
In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.
Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.
In this paper, we discuss practical design of low-density parity-check (LDPC) codes for the q-ary partial erasure channel (QPEC). This channel is an extension of the binary erasure channel (BEC), where partial information on the output is available. We provide a linear programming (LP) optimization for the design of good degree distributions, and compare our code design results to codes obtained using an LP optimization formulated for the BEC. We show superior performance in terms of code rate and complexity, when designing an LDPC code for a desired decoding threshold.
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 present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.