PENERAPAN LOGARITMA ZECH DALAM KONSTRUKSI BARISAN DE BRUIJN TERMODIFIKASI MELALUI METODE PENGGABUNGAN SIKLUS

Muhammad Nurcahyo Eko Saputra, Program Studi Matematika, Universitas Negeri Yogyakarta
Musthofa Musthofa, Program Studi Matematika, Universitas Negeri Yogyakarta

 10.21831/jktm.v12i2.28410

Abstract


Barisan de Bruijn merupakan barisan siklik biner yang memuat seluruh kemungkinan n-tuple tepat satu kali dalam satu periode. Pada barisan de Bruijn klasik terdapat run nol terpanjang sepanjang  yang pada beberapa aplikasi dianggap kurang ideal, sehingga dikembangkan barisan de Bruijn termodifikasi dengan menghilangkan satu nol pada run tersebut. Penelitian ini bertujuan untuk menerapkan logaritma Zech dalam konstruksi barisan de Bruijn termodifikasi melalui metode penggabungan siklus. Metode yang digunakan diawali dengan membangkitkan m-sequence menggunakan Linear Feedback Shift Register (LFSR) dengan polinomial primitif, kemudian dilakukan t-desimasi untuk memperoleh beberapa barisan periodik. Selanjutnya, Algoritma Berlekamp–Massey digunakan untuk menentukan polinomial minimal irreducible non-primitif yang menghasilkan siklus-siklus terpisah. Siklus-siklus tersebut digabung menggunakan metode penggabungan siklus melalui penukaran successor pada pasangan konjugat. Dalam proses tersebut, logaritma Zech digunakan untuk menentukan pasangan konjugat dan posisi state secara lebih sistematis dengan merepresentasikan setiap state dalam bentuk a^i . Hasil penelitian menunjukkan bahwa penggunaan logaritma Zech dapat mempermudah dan meningkatkan efisiensi proses penggabungan siklus, terutama untuk orde besar dengan jumlah siklus yang banyak. Barisan akhir yang diperoleh merupakan barisan de Bruijn termodifikasi dengan periode (2^n)-1 .

Kata kunci: barisan de Bruijn termodifikasi, LFSR, logaritma Zech, metode penggabungan siklus, -desimasi.


Full Text:

PDF

References


Chan, A. H., Games, R. A., & Key, E. L. (1982). On the complexities of de Bruijn sequences. Journal Of Combinatorial Theory, Series A, 33, 233–246. https://doi.org/10.1016/0097-3165(82)90038-3

Chang, Z., Ezerman, M. F., Fahreza, A. A., Ling, S., Szmidt, J., & Wang, H. (2021). Binary de Bruijn sequences via Zech’s logarithms. SN Computer Science, 2(4), 314. https://doi.org/10.1007/s42979-021-00683-9

Chang, Z., Ezerman, M. F., Ling, S., & Wang, H. (2019). On binary de Bruijn sequences from LFSRs with arbitrary characteristic polynomials. Designs, Codes and Cryptography, 87(5), 1137–1160. https://doi.org/10.1007/s10623-018-0509-y

de Bruijn, N. G. (1946). A combinatorial problem. Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen Te Amsterdam, 49(7), 758–764.

Fredricksen, H. (1982). A survey of full length nonlinear shift register cycle algorithms. SIAM Review, 24(2), 195–221. https://doi.org/10.1137/1024041

Golomb, S. W., & Gong, G. (2005). Signal Design for Good Correlation for Wireless Communication, Cryptography, and Radar. Cambridge University Press. https://doi.org/10.1017/CBO9780511546907

Li, M., & Lin, D. (2018). De Bruijn sequences, adjacency graphs, and cyclotomy. IEEE Transactions on Information Theory, 64(4), 2941–2952. https://doi.org/10.1109/TIT.2017.2787742

Mahanum. (2021). Tinjauan kepustakaan. ALACRITY : Journal Of Education. https://doi.org/10.52121/alacrity.v1i2.20

Musthofa, Wijayanti, I. E., Palupi, D. J. E., & Ezerman, M. F. (2022). A new approach to determine the minimal polynomials of binary modified de Bruijn sequences. Mathematics, 10(15). https://doi.org/10.3390/math10152577

Rosenfeld, V. R. (2002). Enumerating de Bruijn sequences. MATCH Communications in Mathematical and in Computer Chemistry, 71–83.

Zhu, Y., Chang, Z., Ezerman, M. F., & Wang, Q. (2021). An efficiently generated family of binary de Bruijn sequences. Discrete Mathematics, 344(6), 112368. https://doi.org/10.1016/j.disc.2021.112368




DOI: https://doi.org/10.21831/jktm.v12i2.28410

Refbacks

  • There are currently no refbacks.


 

Online ISSN (e-ISSN): 3031-1152

Creative Commons LicenseJurnal Kajian dan Terapan Matematika by https://journal.student.uny.ac.id/index.php/jktm/index is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
 
View My Stats