Implementasi Algoritma Inverse Free Berlekamp-Massey pada Studi Kasus Permasalahan SPOJ Do You Even Lift

Jiewandana, William Budi (2019) Implementasi Algoritma Inverse Free Berlekamp-Massey pada Studi Kasus Permasalahan SPOJ Do You Even Lift. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111540000063-William_Budi-Buku_TA.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (918kB) | Request a copy

Abstract

Pembangkitan deret bilangan merupakan hal cukup penting dalam bidang informatika. Deret bilangan bisa digunakan dalam keamanan jaringan untuk membangkitkan bilangan acak maupun dalam proses simulasi untuk mencari fungsi pembangkitan yang cocok untuk menggambarkan suatu kejadian yang berulang. Berlekamp-Massey adalah algoritma yang digunakan untuk mencari linear feedback shift register(LFSR)terpendek dari suatu deret biner(GF(2)). Algoritma ini juga dapat menemukan minimal polynomial atau shortest recurrence relation pada deret dengan field sembarang. Awalnya, algoritma ini dikembangkan oleh Elwyn Berlekamp dan digunakan pada bidang kriptografi untuk mendekode kode Bose–Chaudhuri– Hocquenghem (BCH). Kemudian James Massey menyadari penggunaan algortima ini pada LFSR dan menyedarhanakannya. Pada Tugas Akhir ini, penulis akan merancang penyelesaian permasalahan shortest linear recurrence relation pada studi kasus permasalahan SPOJ Do You Even Lift (DYEL)dengan mengimplementasikan algoritma Berlekamp-Massey menggunakan bahasa Python. Pada bab 2, penulis juga akan menyertakan analisis algoritma lain yang mungkin bisa menyelesaikan permasalahan ini. Hasil Tugas Akhir ini berhasil menyelesaikan permasalahan diatas dengan waktu 0.77 detik dan penggunaan memori 28 MB.
================================================================================================
Sequences generation is an important aspect in information technology. Number sequences can be used to generate pseudo random number in network security and also can be used to find generating function for recurrent events in simulation process. Berlekamp-Massey is an algorithm that will find shortest linear feedback shift register (LFSR) for a given binary output sequence (GF(2)). The algorithm will also find minimal polynomial or shortest recurrence relation of a sequence in arbitrary field. At first, Elwyn Berlekamp created this algorithm to be used in cryptography for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes. Later, James Massey recognized its application in LFSR and simplified the algorithm. In this thesis, the author will design a solution to the problem of shortest linear recurrence for problem SPOJ Do You Even Lift (DYEL)by implementing the Berlekamp-Massey algorithm. In section2, the author will also provide analysis of another algorithm which may solve this problem. The result of this thesis can solve the above problem with fastest time of 0.77 seconds and memory usage of 28 MB.

Item Type:	Thesis (Undergraduate)
Additional Information:	RSIf 006.746 Jie i-1 2019
Uncontrolled Keywords:	Aljabar Linier, Recurrence Relation, Berlekamp-Massey
Subjects:	Q Science > QA Mathematics > QA184 Algebra, Linear Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA76.9.D33 Data compression (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	William Budi Jiewandana
Date Deposited:	27 Sep 2021 06:24
Last Modified:	27 Sep 2021 06:24
URI:	http://repository.its.ac.id/id/eprint/60787

Actions (login required)

View Item