doi: 10.3934/amc.2021003

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 Published  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. AmiriC.-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.  Google Scholar

[2]

J. BaeA. AbotablH.-P. LinK.-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.  Google Scholar

[3]

S.-Y. ChungG. D. ForneyT. 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.   Google Scholar

[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.  Google Scholar

[5]

C. DiD. ProiettiI. E. TelatarT. 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.  Google Scholar

[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.  Google Scholar

[7]

L. DolecekZ. ZhangV. AnantharamM. 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.  Google Scholar

[8]

L. Eroh and A. Schwenk, Cages of girth 5 and 7, Congressus Numerantium, 138 (1999), 157-174.   Google Scholar

[9]

G. Exoo and R. Jajcay, Dynamic cage survey, The Electronic Journal of Combinatorics, 15 (2008), 1-48.   Google Scholar

[10]

J. FeldmanM. 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.  Google Scholar

[11]

H.-L. FuK.-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.  Google Scholar

[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.  Google Scholar

[13]

R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, 8 (1962), 21-28.  doi: 10.1109/tit.1962.1057683.  Google Scholar

[14]

H. HatamiD. G. M. MitchellD. J. Costello and T. E. Fuja, Performance bounds and estimates for quantized LDPC decoders, IEEE Transactions on Communications, 68 (2020), 683-696.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[19]

T. Richardson, Error floors of LDPC codes, Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 41 (2003), 1426-1435.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

N. Wiberg, Codes and Decoding on General Graphs, PhD thesis, Linkoping University, 1996. Google Scholar

[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.  Google Scholar

show all references

References:
[1]

B. AmiriC.-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.  Google Scholar

[2]

J. BaeA. AbotablH.-P. LinK.-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.  Google Scholar

[3]

S.-Y. ChungG. D. ForneyT. 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.   Google Scholar

[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.  Google Scholar

[5]

C. DiD. ProiettiI. E. TelatarT. 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.  Google Scholar

[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.  Google Scholar

[7]

L. DolecekZ. ZhangV. AnantharamM. 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.  Google Scholar

[8]

L. Eroh and A. Schwenk, Cages of girth 5 and 7, Congressus Numerantium, 138 (1999), 157-174.   Google Scholar

[9]

G. Exoo and R. Jajcay, Dynamic cage survey, The Electronic Journal of Combinatorics, 15 (2008), 1-48.   Google Scholar

[10]

J. FeldmanM. 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.  Google Scholar

[11]

H.-L. FuK.-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.  Google Scholar

[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.  Google Scholar

[13]

R. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, 8 (1962), 21-28.  doi: 10.1109/tit.1962.1057683.  Google Scholar

[14]

H. HatamiD. G. M. MitchellD. J. Costello and T. E. Fuja, Performance bounds and estimates for quantized LDPC decoders, IEEE Transactions on Communications, 68 (2020), 683-696.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[19]

T. Richardson, Error floors of LDPC codes, Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 41 (2003), 1426-1435.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

N. Wiberg, Codes and Decoding on General Graphs, PhD thesis, Linkoping University, 1996. Google Scholar

[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.  Google Scholar

Figure 1.  (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)
Figure 2.  (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)
Figure 3.  A minimal $ (4,2) $-absorbing set with degree $ 4 $ variable nodes that is not elementary
Figure 4.  (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
Table 1.  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
Table 2.  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
Table 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$ {}^* $
Table 4.  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, 2020  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]

Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (17)
  • HTML views (35)
  • Cited by (0)

[Back to Top]