Stopping sets of codes from complete bipartite graph

Document Type : Full Length Article

Authors

1 Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Iran

2 Department of Mathematics, Science and Research Branch, Islamic Azad university, Tehran, Iran.

Abstract

Let C be a code with parity-check matrix H. A stopping set S of size ln for H is an l-columns submatrix of Hs of H which does not contain a row with weight one. In this paper we consider the code which parity-check is incidence matrix of complete bipartite graph Km,n. These codes are LDPC codes and we obtain the stopping sets for these codes.

Graphical Abstract

Stopping sets of codes from complete bipartite graph

Keywords

Main Subjects


[1] P. Dankelmann, J. D. Key, B. G. Rodrigues, Codes from Incidence Matrices of Graphs, Univ. KwaZulu-Natal, Durban, 2011.
[2] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, R. L. Urbanke, Finite-length analysis of low-density parity-check codes on the binary erasure channel, IEEE Trans. Inf. Theory 48 (2002) 1570–1579.
[3] M. Esmaeili, A. Zaghian, On the combinatorial structure of a class of [(m,2),(m−1,2), 3] shortened Hamming codes and their dual codes, Discrete Appl. Math. 157 (2009) 356–363.
[4] R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.
[5] M. Nazari, H. R. Maimani, Stopping sets of codes from complete graph, J. Discrete Math. Sci. Cryptogr. 25 (2022) 1–10.
[6] P. Solé, T. Zaslavsky, The covering radius of the cycle code of a graph, Discrete Appl. Math. 45 (1993) 63–70. 
[7] R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27 (1981) 533–547. 
[8] A. Tucker, Applied Combinatorics, 4th ed., John Wiley & Sons, New York, 2002.
[9] A. Velasquez, K. Subramani, P. Wojciechowski, On the complexity of and solutions to the minimum stopping and trapping set problems, Theoretical Computer Science 915 (2022) 26–44.
Volume 11, Issue 2
June 2026
Pages 87-97
  • Receive Date: 23 February 2025
  • Revise Date: 11 May 2025
  • Accept Date: 26 May 2025
  • First Publish Date: 01 June 2026
  • Publish Date: 01 June 2026