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 Symposium on Turbo Codes and Iterative Information Processing

Estimation of the decoding threshold of LDPC codes over the q-ary partial erasure channel

Rami Cohen, Yuval Cassuto

Published Aug 1, 2014• 2 citations
Publisher

Abstract

In this paper, we discuss bounds and approximations for the decoding threshold of LDPC codes over the q-ary partial erasure channel (QPEC), introduced in [1]. The QPEC has a q-ary input, and its output is either one symbol or a set of 2 ≤ M ≤ q possible symbols. We show how an upper bound on the decoding threshold can be derived using a single-letter recurrence relation, when M > q/2. In addition, we discuss complexity issues in the calculation of the threshold, and provide two approximation models that lead to reasonable results with a fraction of the complexity required for the exact calculation.

DOI
10.1109/istc.2014.6955113

Related papers

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

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations

Partially-regular LDPC codes with linear encoding complexity and improved thresholds

D. K. Zigangirov, Kamil Sh. Zigangirov, Daniel J. Costello

We consider an ensemble of systematic low-density parity-check (LDPC) codes of length N with linear encoding complexity, i.e., with complexity O(N). We call these codes partially-regular, since they can be considered as modifications of regular LDPC codes. Further, their iterative decoding thresholds on the binary erasure channel (BEC) are found to be significantly better than the thresholds of the corresponding regular LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•0 citations

Analysis of Verification-Based Decoding on the $q$-ary Symmetric Channel for Large $q$

Fan Zhang, Henry D. Pfister

A new verification-based message-passing decoder for low-density parity-check (LDPC) codes is introduced and analyzed for the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then one finds that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q -SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, the node-based algorithms are evaluated via analysis and simulation. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

arXiv:0806.3243•IEEE Transactions on Information Theory•Oct 1, 2011•18 citations

ML and Near-ML Decoding of LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles. Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the upper bounds on the ML decoding performance.

arXiv:1709.01455•Sep 5, 2017•1 citation

Iterative LDPC Decoder Analysis

Enrico Paolini, Gianluigi Liva, Balázs Matuz +1 more

Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.

Cambridge University Press eBooks•Feb 25, 2026•0 citations
In this paper, we discuss bounds and approximations for the decoding threshold of LDPC codes over the q-ary partial erasure channel (QPEC), introduced in [1]. The QPEC has a q-ary input, and its output is either one symbol or a set of 2 ≤ M ≤ q possible symbols. We show how an upper bound on the decoding threshold can be derived using a single-letter recurrence relation, when M > q/2. In addition, we discuss complexity issues in the calculation of the threshold, and provide two approximation models that lead to reasonable results with a fraction of the complexity required for the exact calculation.
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.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.
Analysis of Verification-Based Decoding on the qqq-ary Symmetric Channel for Large qqq
A new verification-based message-passing decoder for low-density parity-check (LDPC) codes is introduced and analyzed for the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then one finds that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q -SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, the node-based algorithms are evaluated via analysis and simulation. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles. Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the upper bounds on the ML decoding performance.
Performance analysis for iterative decoders: In Chapter 7, we discuss the behavior of LDPC codes under iterative erasure decoding. When the blocklength goes to infinity, for many LDPC codes, the symbol error probability exhibits a so-called threshold phenomenon that is, there exists a certain channel erasure probability below which error-free communication is possible, while this is not guaranteed above it. We discuss how to compute this threshold for ensembles of LDPC codes on memoryless erasure channels. In the finite-length setting, one may observe a flattening of the symbol error rate curve owing to stopping sets – specific structures in the code’s bipartite graph. Knowing their number and size allows predicting this so-called error floor. Based on our findings, we discuss how to design good LDPC for memoryless erasure channels with extension to channels with memory.