# American Institute of Mathematical Sciences

• Previous Article
On the correlation measures of orders $3$ and $4$ of binary sequence of period $p^2$ derived from Fermat quotients
• AMC Home
• This Issue
• Next Article
Partial direct product difference sets and almost quaternary sequences
doi: 10.3934/amc.2021003
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Extremal absorbing sets in low-density parity-check codes

 1 Department of Mathematics, University of Nebraska – Lincoln, Lincoln, NE 68588, USA 2 Department of Mathematics, University of Wisconsin-Eau Claire, Eau Claire, WI 54701, USA

* Corresponding author: Emily McMillon

Received  June 2020 Revised  November 2020 Early access March 2021

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 $b$ for a given $a$ for which an $(a,b)$-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.

Citation: Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, doi: 10.3934/amc.2021003
##### References:

show all references

##### References:
(a) A $(4,5)$-absorbing set graph. (b) The even part of the absorbing set graph in (a). (c) The normal graph of the graph in (a)
(a) A graph of girth $5$ on $7$ vertices. (b) A $(7,9)$-absorbing set of girth $10$ whose normal graph is the graph in (a)
A minimal $(4,2)$-absorbing set with degree $4$ variable nodes that is not elementary
(a) A minimal $(4,4)$-absorbing set of girth $4$ that is not elementary. (b) As shown, a minimal $(6,4)$-absorbing set of girth $6$ that is not elementary. The dotted edges represent where paths could be extended to generalize to an absorbing set of arbitrary girth
Exact values for $B_{a}^{*}$ for relevant values of $a$ and practical girths are given. Our formulas and bounds for $B_{a}^{*}$ are provided in the first column for comparison. Shaded entries indicate values that are smaller than the bound given in the first column
 $B_{a}^{*}$ Girth \ a 2 3 4 5 6 7 8 9 10 11 12 $= a(a-2)$ $6$ 0 3 8 15 24 35 48 63 80 99 120 $= \left\lfloor \frac{a(a-2)}{2} \right\rfloor$ $8$ 0 1 4 7 12 17 24 31 40 49 60 $\le \left\lfloor a(\sqrt{a-1}-1) \right\rfloor$ $10$ 0 1 2 5 6 9 12 15 20 21 24 $\le \left\lfloor \frac{a}{2} (\sqrt{2a-3} - 1) \right\rfloor$ $12$ 0 1 2 3 6 7 10 11 14 15 18
 $B_{a}^{*}$ Girth \ a 2 3 4 5 6 7 8 9 10 11 12 $= a(a-2)$ $6$ 0 3 8 15 24 35 48 63 80 99 120 $= \left\lfloor \frac{a(a-2)}{2} \right\rfloor$ $8$ 0 1 4 7 12 17 24 31 40 49 60 $\le \left\lfloor a(\sqrt{a-1}-1) \right\rfloor$ $10$ 0 1 2 5 6 9 12 15 20 21 24 $\le \left\lfloor \frac{a}{2} (\sqrt{2a-3} - 1) \right\rfloor$ $12$ 0 1 2 3 6 7 10 11 14 15 18
Values of our bounds for $B_a^*$ are provided for the girth $10$ and $12$ cases and relevant values of $a$. The first row for each girth indicates the predicted value from the bound, and the second row indicates the deviation of the bound from the actual value
 $B_{a}^{*}$ Girth \ $\,\,a$ 2 3 4 5 6 7 8 9 10 11 12 $\le \left\lfloor a(\sqrt{a-1}-1) \right\rfloor$ $10$ 0 1 2 5 7 10 13 16 20 23 27 error - - - - 1 1 1 1 - 2 3 $\le \left\lfloor \frac{a}{2} (\sqrt{2a-3} - 1) \right\rfloor$ $12$ 0 1 2 4 6 8 10 12 15 18 21 error - - - 1 - 1 - 1 1 3 3
 $B_{a}^{*}$ Girth \ $\,\,a$ 2 3 4 5 6 7 8 9 10 11 12 $\le \left\lfloor a(\sqrt{a-1}-1) \right\rfloor$ $10$ 0 1 2 5 7 10 13 16 20 23 27 error - - - - 1 1 1 1 - 2 3 $\le \left\lfloor \frac{a}{2} (\sqrt{2a-3} - 1) \right\rfloor$ $12$ 0 1 2 4 6 8 10 12 15 18 21 error - - - 1 - 1 - 1 1 3 3
Known results on the sizes of cages of relatively small girth and degree [9]. Entries marked with ${}^*$ denote cases for which $n(k,\tilde{g})$ is not known; these values correspond instead to lower bounds from [8]
 $\tilde{g}$ $n(2,\tilde{g})$ $n(3,\tilde{g})$ $n(4,\tilde{g})$ $n(5,\tilde{g})$ $n(6,\tilde{g})$ $n(7,\tilde{g})$ 3 3 4 5 6 7 8 4 4 6 8 10 12 14 5 5 10 19 30 40 50 6 6 14 26 42 62 90 7 7 24 67 108${}^*$ 189${}^*$ 304${}^*$
 $\tilde{g}$ $n(2,\tilde{g})$ $n(3,\tilde{g})$ $n(4,\tilde{g})$ $n(5,\tilde{g})$ $n(6,\tilde{g})$ $n(7,\tilde{g})$ 3 3 4 5 6 7 8 4 4 6 8 10 12 14 5 5 10 19 30 40 50 6 6 14 26 42 62 90 7 7 24 67 108${}^*$ 189${}^*$ 304${}^*$
The lower bounds on $a$ from Theorem 2.3 given girth $g$ and variable node degree $j$. Unshaded values are those for which absorbing sets constructed in Proposition 1 achieve the lower bounds in Theorem 2.3, thereby demonstrating tightness
 $g$ \$\left\lceil \frac{j+1}{2} \right\rceil$ 2 3 4 5 6 7 6 3 4 5 6 7 8 8 4 6 8 10 12 14 10 5 10 17 26 37 50 12 6 14 26 42 62 86 14 7 22 53 106 189 302
 $g$ \$\left\lceil \frac{j+1}{2} \right\rceil$ 2 3 4 5 6 7 6 3 4 5 6 7 8 8 4 6 8 10 12 14 10 5 10 17 26 37 50 12 6 14 26 42 62 86 14 7 22 53 106 189 302
 [1] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [2] Thomas Westerbäck. Parity check systems of nonlinear codes over finite commutative Frobenius rings. Advances in Mathematics of Communications, 2017, 11 (3) : 409-427. doi: 10.3934/amc.2017035 [3] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [4] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [5] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [6] Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385 [7] Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83 [8] Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477 [9] Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089 [10] Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046 [11] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [12] Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005 [13] Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002 [14] Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419 [15] Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1 [16] Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49 [17] Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485 [18] Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007 [19] Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311 [20] Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031

2020 Impact Factor: 0.935

## Tools

Article outline

Figures and Tables