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

Verification-Based Decoding with MAP Erasure Recovery

Balázs Matuz, Gianluigi Liva, Enrico Paolini, Marco Chiani

Published Feb 25, 2013• 6 citations
OpenAlex

Abstract

Verification-based decoding (VBD) is a simple yet powerful iterative (IT) decoding technique for codes operating on packets (vector-symbols) and channels that introduce packetwise errors. An example is given by the q-ary symmetric channel (qSC) for which a simple improvement of the VBD algorithm is proposed. It consists of performing a Gaussian elimination (GE)-based erasure decoding stage whenever VBD fails, i.e., whenever beta > 0 packets remain unverified. The modified decoder may recover the beta unverified packets with a complexity of O(beta(exp 3)) by making use of the inherent code structure. Numerical results on low-density parity-check (LDPC) codes and analytical expressions for the block error probability of linear random block codes show the benefit of the proposed algorithm.

Related papers

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

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

Performance Analysis of Verification-Based Decoding for Packet-Based LDPC Codes over Binary Symmetric Channel

Biaokai Zhu, Defeng David Huang, Sven Erik Nordholm

In this paper, we propose a statistical model to analyze the performance of verification-based algorithm (VA) for packet-based low-density parity-check (LDPC) codes over binary symmetric channel (BSC). In contrast to the analysis of VA in the literature, we propose to take the false verification into consideration. For a given ensemble of LDPC codes and channel parameters, the proposed analysis model gives an efficient way to find the average performance of packet-based LDPC codes with verification-based decoding. Through numerical results, we find that the proposed method can provide a close estimation of frame error rate (FER) for packet-based LDPC codes with verification- based decoding over BSC for all crossover probabilities of practical interests.

International Conference on Communications•Jun 1, 2009•1 citation

Enhanced Verification-Based Decoding for Packet-Based LDPC Codes

Bin Zhu, Defeng David Huang, Sven Erik Nordholm

In this letter, an enhanced verification-based decoding algorithm (EVA) for packet level low-density parity-check (LDPC) codes is proposed. Compared with the verification algorithm (VA) in the literature, the proposed algorithm reduces the likelihood of false verification by enhancing the verification condition to achieve a better decoding performance. For example, simulation results in this letter show that EVA reduces frame error rate (FER) by two orders when comparing the VA over binary symmetric channel (BSC), while the increase of the computational load is less than 90%.

IEEE Communications Letters•Feb 1, 2008•6 citations

Erasure correction by low-density codes

Victor Zyablov, Pavel S. Rybin

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Problems of Information Transmission•Sep 1, 2009•6 citations

Enhanced Verification-Based Decoding for Packet-Based LDPC Codes over Wireless Channels

Bin B. Zhu, Defeng David Huang, Sven Erik Nordholm

In this paper, we apply the enhanced verification-based decoding algorithm (EVA) for packet-based LDPC codes over wireless channels. Compared with the verification algorithm (VA) in the literature, the EVA algorithm enhances the verification condition thereby reducing the likelihood of false verification. The wireless channels in simulations are modeled by binary symmetric channel (BSC) and Gilbert-Elliott (GE) channel. The numerical results indicate the proposed algorithm gives a superior performance but with only moderate computation increase compared with VA. For example, when the bit error probability is less than 10-3in bad state of GE channel, the EVA reduces the frame error rate (FER) by one order with less than 35% complexity increase compared with VA.

Globecom•Jan 1, 2008•0 citations
Verification-based decoding (VBD) is a simple yet powerful iterative (IT) decoding technique for codes operating on packets (vector-symbols) and channels that introduce packetwise errors. An example is given by the q-ary symmetric channel (qSC) for which a simple improvement of the VBD algorithm is proposed. It consists of performing a Gaussian elimination (GE)-based erasure decoding stage whenever VBD fails, i.e., whenever beta > 0 packets remain unverified. The modified decoder may recover the beta unverified packets with a complexity of O(beta(exp 3)) by making use of the inherent code structure. Numerical results on low-density parity-check (LDPC) codes and analytical expressions for the block error probability of linear random block codes show the benefit of the proposed algorithm.
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.
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.
In this paper, we propose a statistical model to analyze the performance of verification-based algorithm (VA) for packet-based low-density parity-check (LDPC) codes over binary symmetric channel (BSC). In contrast to the analysis of VA in the literature, we propose to take the false verification into consideration. For a given ensemble of LDPC codes and channel parameters, the proposed analysis model gives an efficient way to find the average performance of packet-based LDPC codes with verification-based decoding. Through numerical results, we find that the proposed method can provide a close estimation of frame error rate (FER) for packet-based LDPC codes with verification- based decoding over BSC for all crossover probabilities of practical interests.
In this letter, an enhanced verification-based decoding algorithm (EVA) for packet level low-density parity-check (LDPC) codes is proposed. Compared with the verification algorithm (VA) in the literature, the proposed algorithm reduces the likelihood of false verification by enhancing the verification condition to achieve a better decoding performance. For example, simulation results in this letter show that EVA reduces frame error rate (FER) by two orders when comparing the VA over binary symmetric channel (BSC), while the increase of the computational load is less than 90%.
We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.
In this paper, we apply the enhanced verification-based decoding algorithm (EVA) for packet-based LDPC codes over wireless channels. Compared with the verification algorithm (VA) in the literature, the EVA algorithm enhances the verification condition thereby reducing the likelihood of false verification. The wireless channels in simulations are modeled by binary symmetric channel (BSC) and Gilbert-Elliott (GE) channel. The numerical results indicate the proposed algorithm gives a superior performance but with only moderate computation increase compared with VA. For example, when the bit error probability is less than 10-3in bad state of GE channel, the EVA reduces the frame error rate (FER) by one order with less than 35% complexity increase compared with VA.