Analisis Error Correcting Code Berbasis Matriks Adjacency dari Graf Kipas
Keywords:
Error correcting code, Graf Kipas, Kode Linear Biner, Matriks Adjacency, Matriks Generator, Teori KodeAbstract
Perkembangan pesat teknologi digital memerlukan proses transmisi dan penyimpanan data yang efisien untuk menunjang berbagai aktivitas digital. Penelitian ini bertujuan untuk membentuk dan menganalisis error correcting code berbasis matriks adjacency dari graf kipas dengan serta mengkaji parameter kode yang dihasilkan berdasarkan struktur graf tersebut. Kajian ini termasuk dalam bidang teori kode yang memanfaatkan struktur graf untuk menghasilkan kode linear biner dengan minimum distance tertentu untuk menganalisis kemampuan deteksi dan koreksi kesalahan. Metode yang digunakan adalah studi pustaka berupa buku, jurnal, atau publikasi dalam situs web terkait error correcting code berbasis matriks adjacency suatu graf. Tahapan penelitian meliputi pembentukan struktur graf kipas, penyusunan matriks adjacency, penghapusan baris identik matriks adjacency, pembentukan matriks generator melalui penggabungan matriks identitas dan matriks adjacency hasil penyederhanaan, dan perhitungan parameter kode serta nilai rate untuk menganalisis efisiensi pengkodean. Analisis dilakukan dengan mengkaji pengaruh jumlah vertex graf kipas serta pengaruhnya terhadap nilai minimum distance dan rate kode. Hasil penelitian menunjukkan bahwa matriks adjacency graf kipas , , dan menghasilkan kode dengan kemampuan koreksi satu bit kesalahan, dengan nilai minimum distance masing-masing 4 dan 3 serta nilai rate 0.4285 dan 0.5. Hasil ini menunjukkan bahwa struktur graf kipas memiliki potensi sebagai dasar pembentukan error correcting code yang sederhana dan efisien serta berpeluang untuk dikembangkan lebih lanjut pada sistem komunikasi digital dengan kemampuan deteksi dan koreksi kesalahan yang lebih optimal.
Downloads
References
Agustin, P. A. N., & Utomo, P. H. (2024). Implementasi proses encoding dan decoding kode Reed–Muller menggunakan Python. Prosiding Seminar Nasional Sains dan Teknologi Seri 02, 1(2), 301-309.
Alizadeh, F., Glasby, S. P., & Praeger, C. E. (2023). Sequences of linear codes where the rate times distance grows rapidly. Journal of Algebra Combinatorics Discrete Structures and Applications, 10(2), 105–113.
Aydin, N. (2007). An Introduction to Coding Theory via Hamming Codes: A Computational Science Model. Faculty Publications, Paper 4.
Cascudo, I., Gundersen, J. S., & Ruano, D. (2019). Squares of matrix-product codes. Finite Fields and Their Applications, 62,101606.
Ganagi, A. B. and H. S. Ramane. (2016). Hamming Distance between the Strings Generated by the Adjacency Matrix of a Graph and their Sum. Algebra and Discrete Mathematics, 22(1).
Hamming, R. W. (1950). Error Detecting and Error correcting codes. Bell System Technical Journal, 29(2), 147–160.
Hidayat, A. N., Krisnawati, V. H., & Alghofari, A. R. (2024). Reversible Self-Dual Codes over Finite Field. Jurnal Matematika Murni dan Aplikasi, 9(2), 287-296.
Kopparty, S., Potukuchi, A., & Sha, H. (2024). Error-Correcting Graph Codes. Preprint, University of Toronto and York University.
Kurz, S. (2022). On the number of minimal codewords in codes generated by the adjacency matrix of a graph. Discrete Applied Mathematics, 309, 221–228.
Kurz, S. (2024). Non-projective two-weight codes. Entropy, 26(4), 289.
Mallik, S., & Yildiz, B. (2021). Graph theoretic aspects of minimum distance and equivalence of binary linear codes. Australasian Journal of Combinatorics, 79(3), 515–526.
Özkan, M. (2024). Applications of fixed minimum distance codes with generators in standard form. International Journal of Advanced Natural Sciences and Engineering Researches, 8(11), 708–715.
Paramadevan, P., & Sotheeswaran, S. (2021). Properties of adjacency matrix of a graph and its construction. Journal of Science, 12(1), 13–21.
Pless, V. (1998). Introduction to The Theory of Error-Correcting Codes (3rd ed.). John Wiley & Sons.
Ravagnani, A. (2025). Small-weight codewords of algebraic geometry codes. Bollettino dell’Unione Matematica Italiana, 18, 779–795.
Santiago, R. (2017). Packing Chromatic Number of Certain Fan and Wheel Related Graphs. AKCE International Journal of Graphs and Combinatorics, 14(1), 63–69.
Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423.
Tanna, D., Ryan, J., & Senaničová-Feňovíková, A. (2017). Edge Irregular Reflexive Labeling of Prisms and Wheels. AKCE International Journal of Graphs and Combinatorics, 69(3), 394–401.
Zaky, R. N., Triyani, & Nurshiami, S. R. (2025). Energi Ketetanggaan pada Graf Benteng. Prosiding Diskusi Panel Nasional Pendidikan Matematika, 93–102.
Zhang, G., Lin, L., Qin, C., & Li, R. (2024). Hermitian self-dual 2-quasi-abelian codes. Finite Fields and Their Applications, 94, 102357.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Ayu Dewi Gayatri, Putranto Hadi Utomo
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
