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:0806.3243 · IEEE Transactions on Information Theory

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

Fan Zhang, Henry D. Pfister

Published Oct 1, 2011• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2011.2165813

Related papers

List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q

Fan Zhang, Henry D. Pfister

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols 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 we find 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. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. 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.

Globecom•Nov 1, 2007•25 citations

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.

•Jan 1, 2021•3 citations

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•1 citation

Verification-based decoding for packet-based LDPC codes over binary symmetric channels

Bin Benjamin Zhu

Research on low-density parity-check (LDPC) codes has traditionally been focused on small alphabets. With the development of communication networks and high-speed wireless communication systems, the operation units are normally blocks of bits organized as packets. Packet-based LDPC codes have a great potential to be used in multi-cast and content delivery networks to help achieve reliable communications. To decode packet-based LDPC codes, a verification-based decoding algorithm (VA) has been proposed by Luby and Mitzenmacher for q-ary symmetric channels (q-SC) with large q. However, as a packet-level block code, packet-based LDPC codes are most likely used as outer codes in concatenated coding schemes. Due to the fact that in a typical communication system, an interleaver is employed between the inner encoder and the outer encoder and the output from the inner decoder is normally in a hard-decision form, a binary symmetric channel (BSC) is thereby most proper to model such a scenario. We will show that in contrast to q-SC with large q, when VA is used for BSC, the probability that a packet is falsely verified plays a dominant role in determining system performance. In this dissertation, we propose an enhanced verification-based decoding algorithm (EVA) to improve the verification conditions and significantly reduce the possibility of the false verifications. In contrast to VA, EVA has much better performance over BSC with only moderate computation complexity increase. We also analyze the performance of VA and EVA over BSC. By reformulating VA (EVA) as a message-passing algorithm, a statistical model is proposed to analyze the frame error rate (FER) performance of VA (EVA). Using a recursive method to find the values of the parameters during the iterative process, the proposed model provides a good estimate of FER for the various packet sizes and channel parameters of practical interest.

•Jan 1, 2011•0 citations

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.

•Jan 1, 2019•9 citations

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•1 citation
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.
We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols 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 we find 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. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. 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.
A decoding algorithm for qqq -ary low-density parity-check codes over the qqq -ary symmetric channel is introduced. The exchanged messages are lists of symbols from Fq\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 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.
Research on low-density parity-check (LDPC) codes has traditionally been focused on small alphabets. With the development of communication networks and high-speed wireless communication systems, the operation units are normally blocks of bits organized as packets. Packet-based LDPC codes have a great potential to be used in multi-cast and content delivery networks to help achieve reliable communications. To decode packet-based LDPC codes, a verification-based decoding algorithm (VA) has been proposed by Luby and Mitzenmacher for q-ary symmetric channels (q-SC) with large q. However, as a packet-level block code, packet-based LDPC codes are most likely used as outer codes in concatenated coding schemes. Due to the fact that in a typical communication system, an interleaver is employed between the inner encoder and the outer encoder and the output from the inner decoder is normally in a hard-decision form, a binary symmetric channel (BSC) is thereby most proper to model such a scenario. We will show that in contrast to q-SC with large q, when VA is used for BSC, the probability that a packet is falsely verified plays a dominant role in determining system performance. In this dissertation, we propose an enhanced verification-based decoding algorithm (EVA) to improve the verification conditions and significantly reduce the possibility of the false verifications. In contrast to VA, EVA has much better performance over BSC with only moderate computation complexity increase. We also analyze the performance of VA and EVA over BSC. By reformulating VA (EVA) as a message-passing algorithm, a statistical model is proposed to analyze the frame error rate (FER) performance of VA (EVA). Using a recursive method to find the values of the parameters during the iterative process, the proposed model provides a good estimate of FER for the various packet sizes and channel parameters of practical interest.
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.
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.