Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes With Applications to Stopping Sets

DOI10.1109/TIT.2018.2865385MaRDI QIDQ4615361zbMATH OpenOpenAlexFDO

Authors Yoones Hashemi, Amir H. Banihashemi

Publication date 28 January 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.02028

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Linear codes (general theory) (94B05)

Abstract: In this paper, we propose a characterization for non-elementary trapping sets (NETSs) of low-density parity-check (LDPC) codes. The characterization is based on viewing a NETS as a hierarchy of embedded graphs starting from an ETS. The characterization corresponds to an efficient search algorithm that under certain conditions is exhaustive. As an application of the proposed characterization/search, we obtain lower and upper bounds on the stopping distance $s_{min}$ of LDPC codes. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, $s_{min}$. Finding $s_{min}$, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.

Recommendations

• Characterization of Elementary Trapping Sets in Irregular LDPC Codes and the Corresponding Efficient Exhaustive Search Algorithms
• On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes
• New Characterization and Efficient Exhaustive Search Algorithm for Leafless Elementary Trapping Sets of Variable-Regular LDPC Codes
• Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes
• On the Construction of Structured LDPC Codes Free of Small Trapping Sets
• Asymptotic Average Multiplicity of Structures Within Different Categories of Trapping Sets, Absorbing Sets, and Stopping Sets in Random Regular and Irregular LDPC Code Ensembles
• Corrections to “On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes” [Sep 14 5188-5203]
• Hardness Results on Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes
• On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes
• From Cages to Trapping Sets and Codewords: A Technique to Derive Tight Upper Bounds on the Minimum Size of Trapping Sets and Minimum Distance of LDPC Codes

Cited in

(3)

• Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles
• Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers
• On the Construction of Structured LDPC Codes Free of Small Trapping Sets

This page was built for publication: Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes With Applications to Stopping Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615361)