NDLI: Impact of redundant checks on the LP decoding thresholds of LDPC codes

Content Provider	IEEE Xplore Digital Library
Author	Bazzi, L. Audah, H.
Copyright Year	2015
Description	Author affiliation: Dept. of Electr. & Comput. Eng., American Univ. of Beirut, Beirut, Lebanon (Bazzi, L.; Audah, H.)
Abstract	Feldman et al. [1] asked whether the performance of the Linear Programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for LDPC codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the Binary Symmetric Channel (BSC) under certain conditions on the base Tanner graph. First, we show that if the base Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense: for each constant δ > 0, there is a constant k > 0 such that the threshold of the LP decoder containing all redundant checks of degree at most k improves by at most δ upon adding to the LP all redundant checks of degree larger than k. We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [2] and its recent improvement by Viderman [3], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs.
Starting Page	411
Ending Page	415
File Size	230188
Page Count	5
File Format	PDF
ISSN	21578117
e-ISBN	9781467377041
DOI	10.1109/ISIT.2015.7282487
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-06-14
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Iterative decoding Linear programming Maximum likelihood decoding Linear codes Probabilistic logic
Content Type	Text
Resource Type	Article

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

Improved linear programming decoding and bounds on the minimum distance of LDPC codes

Modified multistage linear programming decoding of LDPC codes

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Infeasible primal-dual interior-point algorithm for linear-programming decoding of LDPC codes

Adaptive Methods for Linear Programming Decoding

Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes

Average min-sum decoding of LDPC codes

LP decoding of LDPC codes in HARQ systems

On the joint decoding of LDPC codes and finite-state channels via linear programming

Impact of redundant checks on the LP decoding thresholds of LDPC codes

Similar Documents

Improved linear programming decoding and bounds on the minimum distance of LDPC codes

Modified multistage linear programming decoding of LDPC codes

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Infeasible primal-dual interior-point algorithm for linear-programming decoding of LDPC codes

Adaptive Methods for Linear Programming Decoding

Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes

Average min-sum decoding of LDPC codes

LP decoding of LDPC codes in HARQ systems

On the joint decoding of LDPC codes and finite-state channels via linear programming

Impact of redundant checks on the LP decoding thresholds of LDPC codes