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:1004.5216 · International Symposium on Information Theory and its Applications

Optimized puncturing distributions for irregular non-binary LDPC codes

Matteo Gorgoglione, Valentin Savin, David Declercq

Published Oct 1, 2010• 19 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isita.2010.5649264

Related papers

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

Statistical-Based Density Evolution Algorithm for Nonbinary Low-Density Parity-Check Codes

Jie Wu, Minjian Zhao, Jie Zhong +2 more

A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.

IEEE Vehicular Technology Conference•Sep 1, 2011•1 citation

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

Demijan Klinc, Jeongseok Ha, Steven W. McLaughlin

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.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2008•8 citations

Design and Analysis of NB QC-LDPC Codes Over Small Alphabets

Irina E. Bocharova, Boris D. Kudryashov, Evgenii P. Ovsyannikov +2 more

We propose a novel approach to optimization of irregular nonbinary (NB) quasi-cyclic (QC)-LDPC codes over small alphabets. In this approach, first, the base parity-check matrices are constructed by a simulated annealing method, and then these matrices are labeled by the field elements while maximizing the so- called generalized girth of the Tanner graph. In order to analyze the performance of the constructed irregular NB LDPC codes, a new ensemble of irregular NB LDPC codes over the extensions of the binary Galois field is introduced. A finite-length random coding bound on the error probability of the maximum-likelihood (ML) decoding over the binary phase shift keying (BPSK) input AWGN channel for the new code ensemble is derived. The frame error rate (FER) performance of the sum-product belief-propagation (BP) decoding of the constructed NB QC-LDPC block codes is compared to that of both the optimized binary QC-LDPC block codes in the 5G standard and the best known NB QC-LDPC codes as well as to the derived random coding bound on the ML decoding error probability. It is shown that the obtained bound predicts the behavior of BP decoding performance of practical NB QC-LDPC codes more accurately than the BP decoding thresholds do.

IEEE Transactions on Communications•Mar 16, 2022•16 citations

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

Hossein Pishro-Nik, Faramarz Fekri

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels

IEEE Transactions on Information Theory•Jan 23, 2007•100 citations

Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation

Ge Li, I.J. Fair, Witold A. Krzymień

This paper extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).

IEEE Transactions on Information Theory•Feb 26, 2009•80 citations
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.
A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.
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.
We propose a novel approach to optimization of irregular nonbinary (NB) quasi-cyclic (QC)-LDPC codes over small alphabets. In this approach, first, the base parity-check matrices are constructed by a simulated annealing method, and then these matrices are labeled by the field elements while maximizing the so- called generalized girth of the Tanner graph. In order to analyze the performance of the constructed irregular NB LDPC codes, a new ensemble of irregular NB LDPC codes over the extensions of the binary Galois field is introduced. A finite-length random coding bound on the error probability of the maximum-likelihood (ML) decoding over the binary phase shift keying (BPSK) input AWGN channel for the new code ensemble is derived. The frame error rate (FER) performance of the sum-product belief-propagation (BP) decoding of the constructed NB QC-LDPC block codes is compared to that of both the optimized binary QC-LDPC block codes in the 5G standard and the best known NB QC-LDPC codes as well as to the derived random coding bound on the ML decoding error probability. It is shown that the obtained bound predicts the behavior of BP decoding performance of practical NB QC-LDPC codes more accurately than the BP decoding thresholds do.
This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels
This paper extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).