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

AEIT International Annual Conference

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

Emna Ben Yacoub, Francisco Lázaro, Alexandre Graell i Amat, Gianluigi Liva

Published Sep 1, 2019• 1 citation
Publisher

Abstract

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.

DOI
10.23919/aeit.2019.8893373

Related papers

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

Francisco Lázaro, Alexandre Graell i Amat, Gianluigi Liva +1 more

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.

arXiv:1906.02537•Globecom•Dec 1, 2019•9 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

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

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

On Bit-Level Decoding of Nonbinary LDPC Codes

Mu Zhang, Kui Cai, Qin Huang +1 more

This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.

IEEE Transactions on Communications•Apr 17, 2018•15 citations

Efficient Analysis, Design and Decoding of Low-Density Parity-Check Codes

Masoud Ardakani

This dissertation presents new methods for the analysis, design and decoding of low-density parity-check (LDPC) codes. We start by studying the simplest class of decoders: the binary message-passing (BMP) decoders. We show that the optimum BMP decoder must satisfy certain symmetry and isotropy conditions, and prove that Gallager's Algorithm B is the optimum BMP algorithm. We use a generalization of extrinsic information transfer (EXIT) charts to formulate a linear program that leads to the design of highly efficient irregular LDPC codes for the BMP decoder. We extend this approach to the design of irregular LDPC codes for the additive white Gaussian noise channel. We introduce a "semi-Gaussian" approximation that very accurately predicts the behaviour of the decoder and permits code design over a wider range of rates and code parameters than in previous approaches. We then study the EXIT chart properties of the highest rate LDPC code which guarantees a certain convergence behaviour. We also introduce and analyze gear-shift decoding in which the decoder is permitted to select the decoding rule from among a predefined set. We show that this flexibility can give rise to significant reductions in decoding complexity. Finally, we show that binary LDPC codes can be combined with quadrature amplitude modulation to achieve near-capacity performance in a multitone system over frequency selective Gaussian channels.

•Jan 1, 2004•14 citations
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.
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 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 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 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.
This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes.
This dissertation presents new methods for the analysis, design and decoding of low-density parity-check (LDPC) codes. We start by studying the simplest class of decoders: the binary message-passing (BMP) decoders. We show that the optimum BMP decoder must satisfy certain symmetry and isotropy conditions, and prove that Gallager's Algorithm B is the optimum BMP algorithm. We use a generalization of extrinsic information transfer (EXIT) charts to formulate a linear program that leads to the design of highly efficient irregular LDPC codes for the BMP decoder. We extend this approach to the design of irregular LDPC codes for the additive white Gaussian noise channel. We introduce a "semi-Gaussian" approximation that very accurately predicts the behaviour of the decoder and permits code design over a wider range of rates and code parameters than in previous approaches. We then study the EXIT chart properties of the highest rate LDPC code which guarantees a certain convergence behaviour. We also introduce and analyze gear-shift decoding in which the decoder is permitted to select the decoding rule from among a predefined set. We show that this flexibility can give rise to significant reductions in decoding complexity. Finally, we show that binary LDPC codes can be combined with quadrature amplitude modulation to achieve near-capacity performance in a multitone system over frequency selective Gaussian channels.