Distance verification for LDPC codes

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.

• Publication year

  2016

• Venue

  International Symposium on Information Theory

• Publication date

  2016-05-09

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2016.7541755arXiv 1605.02410
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Numerical techniques for finding the distances of quantum codes

  2014cited by this paper
• Decoding Random Binary Linear Codes in 2n/20: How 1+1=0 Improves Information Set Decoding

  2012cited by this paper
• Smaller decoding exponents: ball-collision decoding

  2011cited by this paper
• A Deterministic Reduction for the Gap Minimum Distance Problem

  2009cited by this paper
• Security Bounds for the Design of Code-Based Cryptosystems

  2009cited by this paper
• Probabilistic Methods in Combinatorics

  2009cited by this paper
• Improved impulse method to evaluate the low weight profile of sparse binary linear codes

  2008cited by this paper
• On decoding of low-density parity-check codes over the binary erasure channel

  2004cited by this paper
• Low-Density Parity-Check Codes

  2004cited by this paper
• Distance distributions in ensembles of irregular low-density parity-check codes

  2003cited by this paper
• On ensembles of low-density parity-check codes: Asymptotic distance distributions

  2002influential reference
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• Efficient erasure correcting codes

  2001cited by this paper
• Design of capacity-approaching irregular low-density parity-check codes

  2001cited by this paper
• Weight distributions: how deviant can you be?

  2001cited by this paper
• Hardness of approximating the minimum distance of a linear code

  1999cited by this paper
• Complexity Issues in Coding Theory

  1997cited by this paper
• The intractability of computing the minimum distance of a code

  1997cited by this paper
• The complexity of information set decoding

  1990cited by this paper
• A method for finding codewords of small weight

  1989cited by this paper
• A probabilistic algorithm for computing minimum weights of large error-correcting codes

  1988cited by this paper
• An Observation on the Security of McEliece's Public-Key Cryptosystem

  1988cited by this paper
• A public key cryptosystem based on algebraic coding theory

  1978cited by this paper
• Probabilistic Methods in Combinatorics

  1974cited by this paper
• The use of information sets in decoding cyclic codes

  1962cited by this paper

• Modeling Spline Curves for Lightweight Cryptographic Hash Function

  2023cites this paper
• Numerical and analytical bounds on threshold error rates for hypergraph-product codes

  2018cites this paper
• Adversarially Robust Property Preserving Hash Functions

  2018cites this paper
• Low-Complexity Cryptographic Hash Functions

  2017cites this paper