Extremal absorbing sets in low-density parity-check codes

Article Contents

2023, Volume 17, Issue 2: 465-483. Doi: 10.3934/amc.2021003

This issue Previous Article The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs Next Article Classical reduction of gap SVP to LWE: A concrete security analysis

$ \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}) $

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
^* Corresponding author: Emily McMillon

Received: June 2020

Revised: November 2020

Early access: March 2021

Published: April 2023

Abstract / Introduction Full Text(HTML) Figure(4) / Table(4) Related Papers Cited by

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 $ 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.

Keywords:

Mathematics Subject Classification: Primary: 94A05; Secondary: 68P30, 68R10.

Citation:

Full Text(HTML)

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)

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

Figure 3. A minimal $ (4,2) $-absorbing set with degree $ 4 $ variable nodes that is not elementary

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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]

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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: 3.0.CO;2-M">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.