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:1906.02537 · Globecom

Symbol Message Passing Decoding of Nonbinary Low-Density Parity-Check Codes

Francisco Lázaro, Alexandre Graell i Amat, Gianluigi Liva, Balázs Matuz

Published Dec 1, 2019• 9 citations
arXivHTMLPDF

Abstract

We present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.

DOI
10.1109/globecom38437.2019.9013601

Related papers

Symbol Message Passing Decoding of Nonbinary Spatially-Coupled Low-Density Parity-Check Codes

Emna Ben Yacoub, Francisco Lázaro, Alexandre Graell i Amat +1 more

The performance of a decoding algorithm, called symbol message passing (SMP), is analyzed for nonbinary spatially coupled low-density parity-check (LDPC) codes. The SMP algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary LDPC codes. The analysis is performed via density evolution over the q-ary symmetric channel, with q being the field order used for the code construction.

AEIT International Annual Conference•Sep 1, 2019•1 citation

List Message Passing Decoding of Non-binary Low-Density Parity-Check Codes

Emna Ben Yacoub

A decoding algorithm for$q$-ary low-density parity-check codes over the$q$-ary symmetric channel is introduced. The exchanged messages are lists of symbols from$\mathbb{F}_{q}$. A density evolution analysis for maximum list sizes 1 and 2 is developed. Thresholds for selected regular low-density parity-check code ensembles are computed showing gains with respect to a similar algorithm in the literature. Finite-length simulation results confirm the asymptotic analysis.

arXiv:2104.06328•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•3 citations

Symbol Message Passing Decoding of LDPC Codes for Orthogonal Modulations

Emna Ben Yacoub, Balázs Matuz

A simple decoder for q-ary low-density parity-check codes is studied, termed symbol message passing. The decoder passes hard decisions from a q-ary alphabet. For orthogonal modulations over the additive white Gaussian channel for which the modulation order and the field order q are equal, it is shown that the extrinsic messages can be modelled as observations of a q-ary symmetric channel, allowing to work out density evolution equations. A stability analysis is provided which emphasizes the influence of degree-3 variable nodes. Simulation results show performance gains for increasing q w.r.t. binary low-density parity-check codes with bit-interleaved coded modulation, and potential savings in decoding complexity.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 30, 2021•1 citation

Analysis of Symbol Message Passing LDPC Decoder for the Poisson PPM Channel

Emna Ben Yacoub, Balázs Matuz

A simple decoding algorithm, dubbed symbol message passing decoder, is studied for q-ary low-density parity-check codes over the q-ary Poisson pulse-position modulation channel. The messages in the decoder are symbols from the finite field ${\mathbb{F}_q}$. To improve performance, a second decoder with an extended message set $\left\{ {{\text{E}} \cup {\mathbb{F}_q}} \right\}$ is also investigated, where E denotes an erasure. Thresholds within 1.3 dB from the Shannon limit are obtained for low field orders.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Decoding LDPC Codes With Locally Maximum-Likelihood Binary Messages

Chris Winstead, Emmanuel Boutillon

A new low-complexity message passing algorithm is described for decoding low-density parity-check (LDPC) codes by exchanging binary messages. The algorithm computes the local maximum-likelihood binary message (LMLBM) at each symbol node, given the combination of local channel information and partial syndrome components from adjacent parity check nodes. When channel information is quantized, the locally ML messages are pre-computed and stored in a dynamic global lookup table. The proposed algorithm uses memoryless extrinsic messages so that density evolution thresholds can be directly computed. Thresholds are obtained for regular ensembles, predicting good performance on quantized binary-input additive white Gaussian noise (biAWGN) channels.

IEEE Communications Letters•Oct 30, 2014•2 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
We present a novel decoding algorithm for q-ary low-density parity- check codes, termed symbol message passing. The proposed algorithm can be seen as a generalization of Gallager B and the binary message passing algorithm by Lechner et al. to q-ary codes. We derive density evolution equations for the q-ary symmetric channel, compute thresholds for a number of regular low-density parity-check code ensembles, and verify those by Monte Carlo simulations of long channel codes. The proposed algorithm shows performance advantages with respect to an algorithm of comparable complexity from the literature.
A decoding algorithm forqqq-ary low-density parity-check codes over theqqq-ary symmetric channel is introduced. The exchanged messages are lists of symbols fromFq\mathbb{F}_{q}Fq​. A density evolution analysis for maximum list sizes 1 and 2 is developed. Thresholds for selected regular low-density parity-check code ensembles are computed showing gains with respect to a similar algorithm in the literature. Finite-length simulation results confirm the asymptotic analysis.
A simple decoder for q-ary low-density parity-check codes is studied, termed symbol message passing. The decoder passes hard decisions from a q-ary alphabet. For orthogonal modulations over the additive white Gaussian channel for which the modulation order and the field order q are equal, it is shown that the extrinsic messages can be modelled as observations of a q-ary symmetric channel, allowing to work out density evolution equations. A stability analysis is provided which emphasizes the influence of degree-3 variable nodes. Simulation results show performance gains for increasing q w.r.t. binary low-density parity-check codes with bit-interleaved coded modulation, and potential savings in decoding complexity.
A simple decoding algorithm, dubbed symbol message passing decoder, is studied for q-ary low-density parity-check codes over the q-ary Poisson pulse-position modulation channel. The messages in the decoder are symbols from the finite field Fq{\mathbb{F}_q}Fq​. To improve performance, a second decoder with an extended message set {E∪Fq}\left\{ {{\text{E}} \cup {\mathbb{F}_q}} \right\}{E∪Fq​} is also investigated, where E denotes an erasure. Thresholds within 1.3 dB from the Shannon limit are obtained for low field orders.
A new low-complexity message passing algorithm is described for decoding low-density parity-check (LDPC) codes by exchanging binary messages. The algorithm computes the local maximum-likelihood binary message (LMLBM) at each symbol node, given the combination of local channel information and partial syndrome components from adjacent parity check nodes. When channel information is quantized, the locally ML messages are pre-computed and stored in a dynamic global lookup table. The proposed algorithm uses memoryless extrinsic messages so that density evolution thresholds can be directly computed. Thresholds are obtained for regular ensembles, predicting good performance on quantized binary-input additive white Gaussian noise (biAWGN) channels.
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.