Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 5/2022

13-10-2020 | Original Paper

LDPC codes constructed from cubic symmetric graphs

Authors: Dean Crnković, Sanja Rukavina, Marina Šimac

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 5/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Low-density parity-check (LDPC) codes have been the subject of much interest due to the fact that they can perform near the Shannon limit. In this paper we present a construction of LDPC codes from cubic symmetric graphs. The codes constructed are (3, 3)-regular and the vast majority of the corresponding Tanner graphs have girth greater than four. We analyse properties of the codes obtained and present bounds for the code parameters, the dimension and the minimum distance. Furthermore, we give an expression for the variance of the syndrome weight of the codes constructed. Information on the LDPC codes constructed from bipartite cubic symmetric graphs with less than 200 vertices is presented as well. Some of the codes constructed are optimal, and some have an additional property of being self-orthogonal or linear codes with complementary dual (LCD codes).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Footnotes
1
It has been proved in [22] that the lower bound for the second largest eigenvalue of the adjacency matrix of a k regular graph in which there are two edges of distance at least \(2l+2\) is \(2\sqrt{k-1}-\frac{2\sqrt{k-1}-1}{l+1}\).
 
Literature
1.
go back to reference Balakrishnan, R., Ranganathan, K.: A Textbook of Graph Theory. Springer, New York (2012)CrossRef Balakrishnan, R., Ranganathan, K.: A Textbook of Graph Theory. Springer, New York (2012)CrossRef
2.
go back to reference Carlet, C., Guilley, S.: Complementary dual codes for counter-measures to side-channel attacks. In: Pinto, R., Rocha Malonek, P., Vettori, P. (eds.) Coding Theory and Applications. CIM Series in Mathematical Sciences, vol. 3, pp. 97–105. Springer, Cham (2015)CrossRef Carlet, C., Guilley, S.: Complementary dual codes for counter-measures to side-channel attacks. In: Pinto, R., Rocha Malonek, P., Vettori, P. (eds.) Coding Theory and Applications. CIM Series in Mathematical Sciences, vol. 3, pp. 97–105. Springer, Cham (2015)CrossRef
3.
4.
go back to reference Chilappagari, S. K., Nguyen, D. V., Vasić, B. V., Marcellin, M. W.: Girth of the Tanner graph and error correction capability of LDPC codes. In: 46th Annual Allerton Conference on Communication, Control and Computing, pp. 1238–1245 (2008) Chilappagari, S. K., Nguyen, D. V., Vasić, B. V., Marcellin, M. W.: Girth of the Tanner graph and error correction capability of LDPC codes. In: 46th Annual Allerton Conference on Communication, Control and Computing, pp. 1238–1245 (2008)
5.
7.
go back to reference Crnković, D., Rukavina, S., Šimac, M.: LDPC codes from \(\mu \)-geodetic graphs obtained from block designs. Graphs Combin. 35, 451–469 (2019)MathSciNetCrossRef Crnković, D., Rukavina, S., Šimac, M.: LDPC codes from \(\mu \)-geodetic graphs obtained from block designs. Graphs Combin. 35, 451–469 (2019)MathSciNetCrossRef
8.
9.
go back to reference Foster, R.M.: Geometrical circuits of electrical networks. Trans. Am. Inst. Electr. Eng. 51, 309–317 (1932)CrossRef Foster, R.M.: Geometrical circuits of electrical networks. Trans. Am. Inst. Electr. Eng. 51, 309–317 (1932)CrossRef
10.
go back to reference Gallager, R.G.: Low-Density Parity-Check Codes. MIT Press, Cambridge, MA (1963)CrossRef Gallager, R.G.: Low-Density Parity-Check Codes. MIT Press, Cambridge, MA (1963)CrossRef
11.
go back to reference Greferath, M., Roßing, C., Storme, L.: Galois geometries and low-density parity-check codes. In: Storme, L., De Boeule, J. (eds.) Current Research Topics in Galois Geometry, pp. 245–275. Nova Science Publishers, New York (2012)MATH Greferath, M., Roßing, C., Storme, L.: Galois geometries and low-density parity-check codes. In: Storme, L., De Boeule, J. (eds.) Current Research Topics in Galois Geometry, pp. 245–275. Nova Science Publishers, New York (2012)MATH
12.
go back to reference Hashemi, Y., Banihashemi, A.H.: Lower bounds on the size of smallest elementary and non-elementary trapping sets in variable-regular LDPC codes. IEEE Commun. Lett. 21, 1905–1908 (2017)CrossRef Hashemi, Y., Banihashemi, A.H.: Lower bounds on the size of smallest elementary and non-elementary trapping sets in variable-regular LDPC codes. IEEE Commun. Lett. 21, 1905–1908 (2017)CrossRef
14.
go back to reference Kutnar, K., Marušič, D.: A complete classification of cubic symmetric graphs of girth 6. J. Combin. Theory Ser. B 99, 162–184 (2009)MathSciNetCrossRef Kutnar, K., Marušič, D.: A complete classification of cubic symmetric graphs of girth 6. J. Combin. Theory Ser. B 99, 162–184 (2009)MathSciNetCrossRef
15.
go back to reference Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003)CrossRef Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003)CrossRef
16.
go back to reference Key, J.D., Rodrigues, B.G.: LCD codes from adjacency matrices of graphs. Appl. Algebr. Eng. Comm. 29, 227–244 (2018)MathSciNetCrossRef Key, J.D., Rodrigues, B.G.: LCD codes from adjacency matrices of graphs. Appl. Algebr. Eng. Comm. 29, 227–244 (2018)MathSciNetCrossRef
17.
go back to reference Kim, J.-L., Peled, U.N., Perepelitsa, I., Pless, V.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inform. Theory 50, 2378–2388 (2004)MathSciNetCrossRef Kim, J.-L., Peled, U.N., Perepelitsa, I., Pless, V.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inform. Theory 50, 2378–2388 (2004)MathSciNetCrossRef
18.
go back to reference Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with arbitrary large girth and of large size. Discrete Appl. Math. 60, 275–284 (1995)MathSciNetCrossRef Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with arbitrary large girth and of large size. Discrete Appl. Math. 60, 275–284 (1995)MathSciNetCrossRef
19.
go back to reference MacKay, D.J.C., Neal, R.M.: Near shannon limit performance of low density parity check codes. Electron. Lett. 32, 457–458 (1997)CrossRef MacKay, D.J.C., Neal, R.M.: Near shannon limit performance of low density parity check codes. Electron. Lett. 32, 457–458 (1997)CrossRef
20.
go back to reference MacKay, D.J.C., Neal, R.M.: Good error-correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory 45, 399–431 (1999)MathSciNetCrossRef MacKay, D.J.C., Neal, R.M.: Good error-correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory 45, 399–431 (1999)MathSciNetCrossRef
23.
go back to reference Lechner, G., Pacher, C.: Estimating channel parameters from the syndrome of a linear code. IEEE Commun. Lett. 17, 2148–2151 (2013)CrossRef Lechner, G., Pacher, C.: Estimating channel parameters from the syndrome of a linear code. IEEE Commun. Lett. 17, 2148–2151 (2013)CrossRef
24.
go back to reference Potočnik, P., Spiga, P., Verret, G.: On the nullspace of arc-transitive graphs over finite fields. J. Algebr. Comb. 36, 389–401 (2012)MathSciNetCrossRef Potočnik, P., Spiga, P., Verret, G.: On the nullspace of arc-transitive graphs over finite fields. J. Algebr. Comb. 36, 389–401 (2012)MathSciNetCrossRef
25.
go back to reference Ryan, W.E., Lin, S.: Channel Codes: Classical and Modern. Cambridge University Press, Cambridge (2009)CrossRef Ryan, W.E., Lin, S.: Channel Codes: Classical and Modern. Cambridge University Press, Cambridge (2009)CrossRef
26.
go back to reference Pacher, C., Grabenweger, P., Simos, D.E., Simos, D.E.: Weight distribution of the syndrome of linear codes and connections to combinatorial designs. In: IEEE International Symposium on Information Theory (ISIT), pp. 3038–3042 (2016) Pacher, C., Grabenweger, P., Simos, D.E., Simos, D.E.: Weight distribution of the syndrome of linear codes and connections to combinatorial designs. In: IEEE International Symposium on Information Theory (ISIT), pp. 3038–3042 (2016)
28.
go back to reference Rosenthal, J., Vontobel, P.O.: Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis. In: 38th Allerton Conference on Communication, Control and Computing, pp. 248–257 (2000) Rosenthal, J., Vontobel, P.O.: Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis. In: 38th Allerton Conference on Communication, Control and Computing, pp. 248–257 (2000)
29.
go back to reference Shibuya, T., Onikubo, M., Sakaniwa, K.: On Tanner’s lower bound for the minimum distance of regular LDPC codes based on combinatorial designs. IEICE Trans. Fundam. 5, 2428–2434 (2003) Shibuya, T., Onikubo, M., Sakaniwa, K.: On Tanner’s lower bound for the minimum distance of regular LDPC codes based on combinatorial designs. IEICE Trans. Fundam. 5, 2428–2434 (2003)
30.
go back to reference Singh, J., Gupta, M., Bhullar, J.S.: Construction of girth-8 \((3, L)\)-QC-LDPC codes of smallest CPM size using column multipliers. Des. Codes Cryptogr. 88, 41–49 (2020)MathSciNetCrossRef Singh, J., Gupta, M., Bhullar, J.S.: Construction of girth-8 \((3, L)\)-QC-LDPC codes of smallest CPM size using column multipliers. Des. Codes Cryptogr. 88, 41–49 (2020)MathSciNetCrossRef
31.
32.
go back to reference Toto-Zarasoa, V., Roumy, A., Guillemot, C.: Maximum Likelihood BSC Parameter Estimation for the Slepian-Wolf Problem. IEEE Commun. Lett. 15, 232–234 (2011)CrossRef Toto-Zarasoa, V., Roumy, A., Guillemot, C.: Maximum Likelihood BSC Parameter Estimation for the Slepian-Wolf Problem. IEEE Commun. Lett. 15, 232–234 (2011)CrossRef
33.
go back to reference Xu, H., Bai, B., Feng, D., Sun, C.: On the girth of Tanner (3,11) quasi-cyclic LDPC codes. Finite Fields Appl. 46, 65–89 (2017)MathSciNetCrossRef Xu, H., Bai, B., Feng, D., Sun, C.: On the girth of Tanner (3,11) quasi-cyclic LDPC codes. Finite Fields Appl. 46, 65–89 (2017)MathSciNetCrossRef
Metadata
Title
LDPC codes constructed from cubic symmetric graphs
Authors
Dean Crnković
Sanja Rukavina
Marina Šimac
Publication date
13-10-2020
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 5/2022
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00468-2

Other articles of this Issue 5/2022

Applicable Algebra in Engineering, Communication and Computing 5/2022 Go to the issue

Premium Partner