NDLI: Analysis of Verification-Based Decoding on the <formula formulatype=inline><tex Notation=TeX>$q$</tex></formula>-ary Symmetric Channel for Large <formula formulatype=inline><tex Notation=TeX>$q$</tex> </formula>

Content Provider	IEEE Xplore Digital Library
Author	Fan Zhang Pfister, H.D.
Copyright Year	1963
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.
Sponsorship	IEEE Information Theory Society
Starting Page	6754
Ending Page	6770
Page Count	17
File Size	552435
File Format	PDF
ISSN	00189448
Volume Number	57
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-10-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Decoding Algorithm design and analysis Niobium Iterative decoding Equations Simulation verification decoding False verification list decoding low density parity check codes message passing decoding $q$-ary symmetric channel
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the $q$-ary Random Deletion Channel for Large $q$

Efficient Serial Message-Passing Schedules for LDPC Decoding

Verification Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Message-Passing Algorithms and Improved LP Decoding

A Finite-Length Algorithm for LDPC Codes Without Repeated Edges on the Binary Erasure Channel

Low-density parity-check codes with 2-state trellis decoding

Iterative Decoding Threshold Analysis for LDPC Convolutional Codes

Properties of optimum binary message-passing decoders

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

Similar Documents

Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the $q$-ary Random Deletion Channel for Large $q$

Efficient Serial Message-Passing Schedules for LDPC Decoding

Verification Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Message-Passing Algorithms and Improved LP Decoding

A Finite-Length Algorithm for LDPC Codes Without Repeated Edges on the Binary Erasure Channel

Low-density parity-check codes with 2-state trellis decoding

Iterative Decoding Threshold Analysis for LDPC Convolutional Codes

Properties of optimum binary message-passing decoders

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