Skip to main content

Analysis of verification-based decoding on the q-ary symmetric channel for large q

Publication ,  Journal Article
Zhang, F; Pfister, HD
Published in: IEEE Transactions on Information Theory
October 1, 2011

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. © 2011 IEEE.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

October 1, 2011

Volume

57

Issue

10

Start / End Page

6754 / 6770

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Zhang, F., & Pfister, H. D. (2011). Analysis of verification-based decoding on the q-ary symmetric channel for large q. IEEE Transactions on Information Theory, 57(10), 6754–6770. https://doi.org/10.1109/TIT.2011.2165813
Zhang, F., and H. D. Pfister. “Analysis of verification-based decoding on the q-ary symmetric channel for large q.” IEEE Transactions on Information Theory 57, no. 10 (October 1, 2011): 6754–70. https://doi.org/10.1109/TIT.2011.2165813.
Zhang F, Pfister HD. Analysis of verification-based decoding on the q-ary symmetric channel for large q. IEEE Transactions on Information Theory. 2011 Oct 1;57(10):6754–70.
Zhang, F., and H. D. Pfister. “Analysis of verification-based decoding on the q-ary symmetric channel for large q.” IEEE Transactions on Information Theory, vol. 57, no. 10, Oct. 2011, pp. 6754–70. Scopus, doi:10.1109/TIT.2011.2165813.
Zhang F, Pfister HD. Analysis of verification-based decoding on the q-ary symmetric channel for large q. IEEE Transactions on Information Theory. 2011 Oct 1;57(10):6754–6770.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

October 1, 2011

Volume

57

Issue

10

Start / End Page

6754 / 6770

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing