Glasnik Matematicki, Vol. 61, No. 1 (2026), 175-194. \( \)

LDPC CODES FROM DEZA DIGRAPHS

Nina Mostarac and Marina Šimac

Faculty of Mathematics, University of Rijeka, 51 000 Rijeka, Croatia
e-mail:nmavrovic@math.uniri.hr

Faculty of Mathematics, University of Rijeka, 51 000 Rijeka, Croatia
e-mail:msimac@math.uniri.hr

Abstract.   In this paper, we present a construction of LDPC codes obtained from Deza digraphs with parameters \((n,k,0,1)\). The obtained LDPC codes have no cycles of length four in the Tanner graphs corresponding to the adjacency matrices of the Deza digraphs as parity-check matrices. We describe how LDPC codes can be obtained by applying the Cartesian product of certain Deza digraphs, and the Kronecker product of an adjacency matrix of a Deza digraph with parameters \((n,k,0,1)\) or \((n,k,1,1)\) and a permutation matrix. We also use several other combinatorial objects in the construction of LDPC codes.

2020 Mathematics Subject Classification.   94B05, 05C20

Key words and phrases.   Linear code, LDPC code, Deza digraph

Full text (PDF) (access from subscribing institutions only)

https://doi.org/10.3336/gm.61.1.08

References:

  1. D. Crnković, H. Kharaghani, S. Suda and A. Švob, New constructions of Deza digraphs, Int. J. Group Theory 13 (2024), 225–240.
    MathSciNet    CrossRef

  2. D. Crnković, H. Kharaghani and A. Švob, Divisible design Cayley digraphs, Discrete Math. 343 (2020), 111784.
    MathSciNet    CrossRef

  3. D. Crnković, N. Mostarac and A. Švob, LDPC LCD codes from odd graphs, Adv. Math. Commun. 20 (2026), 68–83.
    MathSciNet    CrossRef

  4. D. Crnković, S. Rukavina and M. Šimac, LDPC codes from Deza graphs, Probl. Inf. Transm. 61 (2025), 219–234.
    MathSciNet    CrossRef

  5. R. Diestel, Graph Theory, Springer, Berlin, 2017.
    MathSciNet    CrossRef

  6. R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.
    Link

  7. M. Greferath, C. Rössing and L. Storme, Galois geometries and low-density parity-check codes, in: Current Research Topics in Galois Geometry, eds. J. De Beule and L. Storme, Nova Sci. Publ., New York, 2011, 245–270.

  8. M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, accessed on 2025-11-13.
    Link

  9. W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, 2003.
    MathSciNet    CrossRef

  10. F. Ivanov and V. Zyablov, LDPC codes based on Steiner quadruple systems and permutation matrices, in: Fourteenth International Workshop on Algebraic and Combinatorial Coding Theory, Nova Science Publishers/Novinka, New York, 2014, 175–180.

  11. J. -L. Kim, U. N. Peled, I. Perepelitsa, V. Pless and S. Friedland, Explicit construction of families of LDPC codes with no \(4\)-cycles, IEEE Trans. Inform. Theory 50 (2004), 2378–2388.
    MathSciNet    CrossRef

  12. Y. Kou, S. Lin and M. P. C. Fossorier, Low density parity-check codes based on finite geometries: a rediscovery and new results, IEEE Trans. Inform. Theory 47 (2001), 2711–2736.
    MathSciNet    CrossRef

  13. D. J. C. MacKay and R. M. Neal, Near Shannon limit performance of low density parity check codes, Electron. Lett. 32 (1997), 457–458.

  14. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
    MathSciNet

  15. E. McMillon, A. Beemer and C. A. Kelley, Extremal absorbing sets in low-density parity-check codes, Adv. Math. Commun. 17 (2023), 465–483.
    MathSciNet    CrossRef

  16. T. Richardson, Error floors of LDPC codes, in: Proc. Allerton Conference on Communications, Control, and Computing, Monticello, 2003, 1426–1435.

  17. J. Rosenthal and P. O. Vontobel, Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis, in: 38th Allerton Conference on Communication, Control and Computing, 2000, 248–257.

  18. C. Schlegel and S. Zhang, On the dynamics of the error floor behavior in (regular) LDPC codes, IEEE Trans. Inform. Theory 56 (2010), 3248–3264.
    MathSciNet    CrossRef

  19. K. Wang and Y. -Q. Feng, Deza digraphs, European J. Combin. 27 (2006), 995–1004.
    MathSciNet    CrossRef

  20. K. Wang and F. Li, Deza digraphs II, European J. Combin. 29 (2008), 369–378.
    MathSciNet    CrossRef

  21. G. Zhang and K. Wang, A directed version of Deza graphs – Deza digraphs, Australas. J. Combin. 28 (2003), 239–244.
    MathSciNet
Glasnik Matematicki Home Page