Construction of Binary Linear Codes from Zero Divisor Graphs
Article Sidebar
-
Incidence Matrix, Hamming Bound, Linear Codes, Zero Divisor Graphs
Abstract
Binary linear codes play an essential role in communication systems by ensuring reliable data transmission. One approach to constructing binary linear codes is through graph theory. In this paper, we study the construction of binary linear codes derived from the incidence matrices of zero divisor graphs of the rings Z(pᵅ) and Z(pᵅqᵝ), where p, q are prime numbers and α, β ≥ 1 are integers. We analyze the parameters of the resulting binary linear codes, such as their length, dimension, and minimum distance. Furthermore, we investigate some examples of the constructed codes. To justify their theoretical and practical relevance, we perform an optimality analysis comparing the constructed codes with classical bounds. All evaluated codes strictly satisfy the Hamming sphere-packing bound. This work offers a new contribution to the study of linear codes by combining ideas from algebra, graph theory, and coding theory.
References
Annamalai, N. and C. Durairajan (2021). Linear Codes from Incidence Matrices of Unit Graphs. Journal of Information and Optimization Sciences, 42(8), 1943–1950.
Annamalai, N. and C. Durairajan (2022). Codes from the Incidence Matrices of Zero-Divisor Graphs. Journal of Discrete Mathematical Sciences and Cryptography, 1–9.
Beck, I. (1988). Coloring of Commutative Rings. Journal of Algebra, 116, 208–226.
Chartrand, G., H. Jordon, V. Vatter, and P. Zhang (2024). Graphs and Digraphs. Chapman and Hall/CRC.
Dankelmann, P., J. D. Key, and B. G. Rodrigues (2011). Codes from Incidence Matrices of Graphs. Designs, Codes and Cryptography, 68, 1–21.
Diestel, R. (2024). Graph Theory. Springer.
Fish, W., J. D. Key, and E. Mwambene (2010). Binary Codes from the Line Graph of the n-Cube. Journal of Symbolic Computation, 45(7), 800–812.
Herstein, I. N. (1995). Abstract Algebra. John Wiley & Sons.
Jain, R. S., B. S. Reddy, and W. M. Shaikh (2023). Construction of Linear Codes from the Unit Graph G(Zn). Asian-European Journal of Mathematics, 2350213.
Key, J. D. and R. Seneviratne (2008). Permutation Decoding for Binary Codes from Lattice Graphs. Discrete Mathematics, 308(13), 2862–2867.
Ling, S. and C. Xing (2004). Coding Theory: A First Course. Cambridge University Press.
Magi, P., S. M. Jose, and A. Kishore (2020). Spectrum of the Zero-Divisor Graph on the Ring of Integers Modulo n. Journal of Mathematical and Computational Science, 10(4), 1285–1297.
Mukhtar, A., R. Murtaza, S. U. Rehman, S. Usman, and A. Q. Baig (2020). Computing the Size of Zero Divisor Graphs. Journal of Information and Optimization Sciences, 41(4), 855–864.
Nachmani, E., E. Marciano, L. Lugosch, W. J. Gross, D. Burshtein, and Y. Be’ery (2018). Deep Learning Methods for Improved Decoding of Linear Codes. IEEE Journal of Selected Topics in Signal Processing, 12(1), 119–131.
Ngo, X. T., S. Bhasin, J.-L. Danger, S. Guilley, and Z. Najm (2015). Linear Complementary Dual Code Improvement to Strengthen Encoded Circuit Against Hardware Trojan Horses. In 2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), 82–87.
Phillips, A., J. Rogers, K. Tolliver, and F. Worek (2004). Uncharted Territory of Zero Divisor Graphs and Their Complements. SUMSRI, Miami University.
Pi, S. J., S. H. Kim, and J. W. Lim (2019). The Zero-Divisor Graph of the Ring of Integers Modulo n. Kyungpook Mathematical Journal, 59(4), 591–601.
Reddy, B. S., R. S. Jain, and N. Laxmikanth (2020). Vertex and Edge Connectivity of the Zero Divisor Graph Γ(Zn). Communications in Mathematics and Applications, 11(2), 253–258.
Roth, R. (2006). Introduction to Coding Theory. Cambridge University Press.
Saranya, R. and C. Durairajan (2021). Codes from Incidence Matrix of Some Regular Graphs. Discrete Mathematics, Algorithms and Applications, 13(4), 2150035.
Saranya, R. and C. Durairajan (2022). Codes from Incidence Matrices of (n,1)-Arrangement Graphs and (n,2)-Arrangement Graphs. Journal of Discrete Mathematical Sciences and Cryptography, 25(2), 373–393.
Shaikh, W. M., R. S. Jain, and B. S. Reddy (2024). Construction of Linear Codes from the Unit Graph G(Zn ⊕ Zn). arXiv preprint.
Singh, P. and V. K. Bhat (2020). Zero-Divisor Graphs of Finite Commutative Rings: A Survey. Surveys in Mathematics & Its Applications, 15.
Vanstone, S. A. and P. C. Van Oorschot (2013). An Introduction to Error Correcting Codes with Applications. Springer Science & Business Media.
Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.