# 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:
 [1] B. Amiri, C.-W. Lin and L. Dolecek, Asymptotic distribution of absorbing sets and fully absorbing sets for regular sparse code ensembles, IEEE Transactions on Communications, 61 (2013), 455-464.  doi: 10.1109/TCOMM.2012.120512.110605. [2] J. Bae, A. Abotabl, H.-P. Lin, K.-B. Song and J. Lee, An overview of channel coding for 5G NR cellular communications, APSIPA Transactions on Signal and Information Processing, 8 (2019), 1-14.  doi: 10.1017/ATSIP.2019.10. [3] S.-Y. Chung, G. D. Forney, T. J. Richardson and R. Urbanke, On the design of low-density parity-check codes within 0.0045 db of the Shannon limit, IEEE Communications Letters, 5 (2001), 58-60. [4] A. Dehghan and A. H. Banihashemi, 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, IEEE Transactions on Information Theory, 65 (2019), 2062-2074.  doi: 10.1109/TIT.2018.2879823. [5] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson and R. L. Urbanke, Finite-length analysis of low-density parity-check codes on the binary erasure channel, IEEE Transactions on Information Theory, 48 (2002), 1570-1579.  doi: 10.1109/TIT.2002.1003839. [6] L. Dolecek, On absorbing sets of structured sparse graph codes, in Proceedings of the 2010 IEEE Information Theory and Applications Workshop (ITA), (2010), 1–5. doi: 10.1109/ITA.2010.5454137. [7] L. Dolecek, Z. Zhang, V. Anantharam, M. Wainwright and B. Nikolic, Analysis of absorbing sets and fully absorbing sets of array-based LDPC codes, IEEE Transactions on Information Theory, 56 (2010), 181-201.  doi: 10.1109/TIT.2009.2034781. [8] L. Eroh and A. Schwenk, Cages of girth 5 and 7, Congressus Numerantium, 138 (1999), 157-174. [9] G. Exoo and R. Jajcay, Dynamic cage survey, The Electronic Journal of Combinatorics, 15 (2008), 1-48. [10] J. Feldman, M. J. Wainwright and D. R. Karger, Using linear programming to decode binary linear codes, IEEE Transactions on Information Theory, 51 (2005), 954-972.  doi: 10.1109/TIT.2004.842696. [11] H.-L. Fu, K.-C. Huang and C. A. Rodger, Connectivity of cages, Journal of Graph Theory, 24 (1997), 187-191.  doi: 10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M. [12] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdös Centennial, Springer, 25 (2013), 169–264. doi: 10.1007/978-3-642-39286-3_7. [13] R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, 8 (1962), 21-28.  doi: 10.1109/tit.1962.1057683. [14] H. Hatami, D. G. M. Mitchell, D. J. Costello and T. E. Fuja, Performance bounds and estimates for quantized LDPC decoders, IEEE Transactions on Communications, 68 (2020), 683-696. [15] S. Hoory, The size of bipartite graphs with a given girth, Journal of Combinatorial Theory, Series B, 86 (2002), 215-220.  doi: 10.1006/jctb.2002.2123. [16] C. A. Kelley and D. Sridhara, Pseudocodewords of Tanner graphs, IEEE Transactions on Information Theory, 53 (2007), 4013-4038.  doi: 10.1109/TIT.2007.907501. [17] R. Koetter and P. O. Vontobel, Graph-covers and iterative decoding of finite length codes, in Proceedings of the 3rd International Symposium on Turbo Codes and Related Topics, (2003), 1–5. [18] W. Mantel, Problem 28 (solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff), Wiskundige Opgaven, 10 (1907), 320. [19] T. Richardson, Error floors of LDPC codes, Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 41 (2003), 1426-1435. [20] M. Schwartz and A. Vardy, On the stopping distance and the stopping redundancy of codes, IEEE Transactions on Information Theory, 52 (2006), 922-932.  doi: 10.1109/TIT.2005.864441. [21] C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423.  doi: 10.1002/j.1538-7305.1948.tb01338.x. [22] R. Tanner, A recursive approach to low complexity codes, IEEE Transactions on Information Theory, 27 (1981), 533-547.  doi: 10.1109/TIT.1981.1056404. [23] N. Wiberg, Codes and Decoding on General Graphs, PhD thesis, Linkoping University, 1996. [24] Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam and M. Wainwright, Investigation of error floors of structured low-density parity-check codes by hardware emulation, in Proceedings of IEEE Globecom 2006, (2006), 1–6. doi: 10.1109/GLOCOM.2006.160.

show all references

##### References:
 [1] B. Amiri, C.-W. Lin and L. Dolecek, Asymptotic distribution of absorbing sets and fully absorbing sets for regular sparse code ensembles, IEEE Transactions on Communications, 61 (2013), 455-464.  doi: 10.1109/TCOMM.2012.120512.110605. [2] J. Bae, A. Abotabl, H.-P. Lin, K.-B. Song and J. Lee, An overview of channel coding for 5G NR cellular communications, APSIPA Transactions on Signal and Information Processing, 8 (2019), 1-14.  doi: 10.1017/ATSIP.2019.10. [3] S.-Y. Chung, G. D. Forney, T. J. Richardson and R. Urbanke, On the design of low-density parity-check codes within 0.0045 db of the Shannon limit, IEEE Communications Letters, 5 (2001), 58-60. [4] A. Dehghan and A. H. Banihashemi, 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, IEEE Transactions on Information Theory, 65 (2019), 2062-2074.  doi: 10.1109/TIT.2018.2879823. [5] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson and R. L. Urbanke, Finite-length analysis of low-density parity-check codes on the binary erasure channel, IEEE Transactions on Information Theory, 48 (2002), 1570-1579.  doi: 10.1109/TIT.2002.1003839. [6] L. Dolecek, On absorbing sets of structured sparse graph codes, in Proceedings of the 2010 IEEE Information Theory and Applications Workshop (ITA), (2010), 1–5. doi: 10.1109/ITA.2010.5454137. [7] L. Dolecek, Z. Zhang, V. Anantharam, M. Wainwright and B. Nikolic, Analysis of absorbing sets and fully absorbing sets of array-based LDPC codes, IEEE Transactions on Information Theory, 56 (2010), 181-201.  doi: 10.1109/TIT.2009.2034781. [8] L. Eroh and A. Schwenk, Cages of girth 5 and 7, Congressus Numerantium, 138 (1999), 157-174. [9] G. Exoo and R. Jajcay, Dynamic cage survey, The Electronic Journal of Combinatorics, 15 (2008), 1-48. [10] J. Feldman, M. J. Wainwright and D. R. Karger, Using linear programming to decode binary linear codes, IEEE Transactions on Information Theory, 51 (2005), 954-972.  doi: 10.1109/TIT.2004.842696. [11] H.-L. Fu, K.-C. Huang and C. A. Rodger, Connectivity of cages, Journal of Graph Theory, 24 (1997), 187-191.  doi: 10.1002/(SICI)1097-0118(199702)24:2<187::AID-JGT6>3.0.CO;2-M. [12] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdös Centennial, Springer, 25 (2013), 169–264. doi: 10.1007/978-3-642-39286-3_7. [13] R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, 8 (1962), 21-28.  doi: 10.1109/tit.1962.1057683. [14] H. Hatami, D. G. M. Mitchell, D. J. Costello and T. E. Fuja, Performance bounds and estimates for quantized LDPC decoders, IEEE Transactions on Communications, 68 (2020), 683-696. [15] S. Hoory, The size of bipartite graphs with a given girth, Journal of Combinatorial Theory, Series B, 86 (2002), 215-220.  doi: 10.1006/jctb.2002.2123. [16] C. A. Kelley and D. Sridhara, Pseudocodewords of Tanner graphs, IEEE Transactions on Information Theory, 53 (2007), 4013-4038.  doi: 10.1109/TIT.2007.907501. [17] R. Koetter and P. O. Vontobel, Graph-covers and iterative decoding of finite length codes, in Proceedings of the 3rd International Symposium on Turbo Codes and Related Topics, (2003), 1–5. [18] W. Mantel, Problem 28 (solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff), Wiskundige Opgaven, 10 (1907), 320. [19] T. Richardson, Error floors of LDPC codes, Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 41 (2003), 1426-1435. [20] M. Schwartz and A. Vardy, On the stopping distance and the stopping redundancy of codes, IEEE Transactions on Information Theory, 52 (2006), 922-932.  doi: 10.1109/TIT.2005.864441. [21] C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379-423.  doi: 10.1002/j.1538-7305.1948.tb01338.x. [22] R. Tanner, A recursive approach to low complexity codes, IEEE Transactions on Information Theory, 27 (1981), 533-547.  doi: 10.1109/TIT.1981.1056404. [23] N. Wiberg, Codes and Decoding on General Graphs, PhD thesis, Linkoping University, 1996. [24] Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam and M. Wainwright, Investigation of error floors of structured low-density parity-check codes by hardware emulation, in Proceedings of IEEE Globecom 2006, (2006), 1–6. doi: 10.1109/GLOCOM.2006.160.
(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] Nabin Kumar Pokhrel, Pankaj Kumar Das. Low-density and high-density asymmetric CT-burst correcting integer codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022030 [2] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [3] 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 [4] 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 [5] 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 [6] 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 [7] Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022029 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] 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

2020 Impact Factor: 0.935