1. Extremal absorbing sets in low-density parity-check codes
- Author
-
Emily McMillon, Allison Beemer, and Christine A. Kelley
- Subjects
Discrete mathematics ,Class (set theory) ,Algebra and Number Theory ,Computer Networks and Communications ,Applied Mathematics ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Microbiology ,Range (mathematics) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Absorbing set ,Low-density parity-check code ,Focus (optics) ,Tanner graph ,Decoding methods ,Mathematics - Abstract
Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of \begin{document}$ b $\end{document} for a given \begin{document}$ a $\end{document} for which an \begin{document}$ (a,b) $\end{document} -absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.
- Published
- 2023