Distance verification for LDPC codes

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object , Other literature type 01 Jul 2016Embargo end date: 01 Jan 2016 United States Publisher:IEEEJournal:2016 IEEE International Symposium on Information Theory (ISIT)Funded by:NSF | Collaborative Research: S..., NSF | Collaborative Research: S...

Authors: Ilya Dumer; Alexey A. Kovalev; Leonid P. Pryadko;

doi: 10.1109/isit.2016.7541755 , 10.48550/arxiv.1605.02410

arXiv: 1605.02410

Distance verification for LDPC codes

- Summary
- Subjects
- Metrics

Abstract

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.

5 pages, 1 figure, to appear in Proceedings of ISIT 2016 - IEEE International Symposium on Information Theory, Barcelona

Country

United States

Related Organizations

University of Nebraska–Lincoln
United States
University of Nebraska System
United States
University of Nebraska-Lincoln
United States
University of California, Riverside
United States
University of California, San Francisco
United States

Keywords

FOS: Computer and information sciences, Quantum Physics, LDPC codes, Applied Mathematics, Distance verification, Computer Science - Information Theory, Information Theory (cs.IT), complexity bounds, FOS: Physical sciences, Mathematical Sciences, Theory Of Computation, covering sets, quant-ph, Information and Computing Sciences, erasure correction, cs.IT, math.IT, Quantum Physics (quant-ph)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average