Abstract
In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes which lead to errors in decoding once a message is received. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. In the journal version of this paper, we prove that two of these trapping set problem variants are NP-hard for the first time. The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896, 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP yields very efficient solutions and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Richardson, T.: Error floors of LDPC codes. In: Proceedings of the Annual Allerton Conference on Communication Control and Computing, vol. 41, pp. 1426–1435. The University; 1998 (2003)
Xiao, H., Banihashemi, A.H.: Estimation of bit and frame error rates of finite-length low-density parity-check codes on binary symmetric channels. IEEE Trans. Commun. 55(12), 2234–2239 (2007)
Di, C., Proietti, D., Telatar, I.E., Richardson, T.J., Urbanke, R.L.: Finite-length analysis of low-density parity-check codes on the binary erasure channel. IEEE Trans. Inf. Theory 48(6), 1570–1579 (2002)
Krishnan, K.M., Shankar, P.: On the complexity of finding stopping set size in tanner graphs. In: 40th Annual Conference on Information Sciences and Systems, pp. 157–158 (2006)
Hu, X.-Y., Eleftheriou, E.: A probabilistic subspace approach to the minimal stopping set problem. In: 2006 4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding (TURBOCODING), pp. 1–6. VDE (2006)
Hirotomo, M., Konishi, Y., Morii, M.: On the probabilistic computation algorithm for the minimum-size stopping sets of LDPC codes. In: IEEE International Symposium on Information Theory, ISIT 2008, pp. 295–299. IEEE (2008)
Rosnes, E., Ytrehus, Ø.: An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices. IEEE Trans. Inf. Theory 55(9), 4167–4178 (2009)
Kyung, G.B., Wang, C.-C.: Exhaustive search for small fully absorbing sets and the corresponding low error-floor decoder. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 739–743. IEEE (2010)
Rosenthal, J., Vontobel, P.O.: Construction of LDPC codes based on Ramanujan graphs and ideas from Margulis. In: Proceedings of 38th Annual Allerton Conference on Communication, Computing and Control, pp. 248–257 (2000)
McGregor, A., Milenkovic, O.: On the hardness of approximating stopping and trapping sets. IEEE Trans. Inf. Theory 56(4), 1640–1650 (2010)
Karimi, M., Banihashemi, A.H.: On characterization of elementary trapping sets of variable-regular LDPC codes. IEEE Trans. Inf. Theory 60(9), 5188–5203 (2014)
Hashemi, Y., Banihashemi, A.H.: Lower bounds on the size of smallest elementary and non-elementary trapping sets in variable-regular LDPC codes. In: IEEE Communications Letters (2017)
MacKay, D.J.C.: Encyclopedia of sparse graph codes (2005)
Krishnan, K.M., Chandran, L.S.: Hardness of approximation results for the problem of finding the stopping distance in tanner graphs. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 69–80. Springer, Heidelberg (2006). https://doi.org/10.1007/11944836_9
Crowston, R., Gutin, G., Jones, M.: Note on max lin-2 above average. Inf. Process. Lett. 110(11), 451–454 (2010)
Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1–2), 123–134 (2000)
Wang, C.-C., Kulkarni, S.R., Poor, H.V.: Upper bounding the performance of arbitrary finite LDPC codes on binary erasure channels. In: 2006 IEEE International Symposium on Information Theory, pp. 411–415. IEEE (2006)
Wang, C.-C., Kulkarni, S.R., Poor, H.V.: Exhausting error-prone patterns in LDPC codes. arXiv preprint arXiv:cs/0609046 (2006)
Wang, C.-C.: On the exhaustion and elimination of trapping sets: algorithms & the suppressing effect. In: IEEE International Symposium on Information Theory, ISIT 2007, pp. 2271–2275. IEEE (2007)
Karimi, M., Banihashemi, A.H.: An efficient algorithm for finding dominant trapping sets of irregular LDPC codes. In: 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1091–1095. IEEE (2011)
Koetter, R., Vontobel, P.O.: Graph-covers and iterative decoding of finite length codes. In: Proceedings of 3rd International Symposium on Turbo Codes and Related Topics, pp. 1–5 (2003)
Gurobi Optimization. Inc.: Gurobi optimizer reference manual (2014). http://www.gurobi.com
Acknowledgements
Alvaro Velasquez acknowledges support from the National Science Foundation Graduate Research Fellowship Program (GRFP) and the Air Force Research Laboratory. Any opinions, findings, and conclusions expressed in this material are those of the author(s) and do not necessarily reflect the views of these institutions. Approved for public release: distribution unlimited, case 88ABW-2018-1178. Cleared March 9, 2018.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Velasquez, A., Subramani, K., Drager, S.L. (2018). Finding Minimum Stopping and Trapping Sets: An Integer Linear Programming Approach. In: Lee, J., Rinaldi, G., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2018. Lecture Notes in Computer Science(), vol 10856. Springer, Cham. https://doi.org/10.1007/978-3-319-96151-4_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-96151-4_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-96150-7
Online ISBN: 978-3-319-96151-4
eBook Packages: Computer ScienceComputer Science (R0)