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]

Mario Pulvirenti, Sergio Simonella. On the cardinality of collisional clusters for hard spheres at low density. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3903-3914. doi: 10.3934/dcds.2021021

[2]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[3]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074

[4]

Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006

[5]

Charles Amorim, Miguel Loayza, Marko A. Rojas-Medar. The nonstationary flows of micropolar fluids with thermal convection: An iterative approach. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2509-2535. doi: 10.3934/dcdsb.2020193

[6]

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161

[7]

Jesús A. Álvarez López, Ramón Barral Lijó, John Hunton, Hiraku Nozawa, John R. Parker. Chaotic Delone sets. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3781-3796. doi: 10.3934/dcds.2021016

[8]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365

[9]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003

[10]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063

[11]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[12]

Nguyen Minh Tung, Mai Van Duy. Painlevé-Kuratowski convergences of the solution sets for vector optimization problems with free disposal sets. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021066

[13]

F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605

[14]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006

[15]

Jan Rychtář, Dewey T. Taylor. Moran process and Wright-Fisher process favor low variability. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3491-3504. doi: 10.3934/dcdsb.2020242

[16]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[17]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

[18]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073

[19]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[20]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2677-2698. doi: 10.3934/dcds.2020381

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]