Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

Call Number T-0034
Collection Type Tesis
Title Modifikasi algoritma quine-McCluskey
Author Haris Sriwindono;
Publisher Depok: Pasca Sarjana Fak. Ilmu Komputer UI, 1994
Subject Algoritma McCluskey
Location FASILKOM-UI;
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
T-0034 94/7010 TERSEDIA
Tidak ada review pada koleksi ini: 8217
Pada tulisan ini disusun suatu algoritma sebagai pengembangan dari algoritma yang sudah ada yaitu algoritma Quine-McCluskey untuk membantu minimalkan fungsi Boole dalam bentuk sum of product. Algoritma ini berguna dalam perancangan rangkaian logika kombinasi terutama PLA (Programmable Logic Array) sehingga diperoleh rangkaian berbiaya rendah. Dalam rangkaian logika kombinasi, fungsinya secara eksplisit dinyatakan dalam fungsi Boole. Untuk meminimalkan fungsi Boole ini sudah dikenal beberapa metode antara lain metode Peta Karnaugh, metode tabulasi [ HILL81], metode Mini [Are78] dan metode ESPRESSO [BRAY84]. Pada metode tabulasi diperlukan tiga tahap untuk meminimalkan fungsi Boole, yaitu pencarian PI (Prime Implicant), pencarian EPI (Essential Prime Impicant) dan pemilihan NON-EPI. Algoritma quine McCluskey hanya melaksanakan tahap pertama yaitu pencarian Prime Implicant. Dengan menelusuri ide dasar penyusunan algoritma Quine-McCluskey, yaitu teori kubus, dan dengan menentuan suatu relasi partial ordering > di himpunan c=(0,1,x) yang menjadikan (c,2) sebuah lattice, maka dengan menggunakan sifat lattice tersebut dapat disusun aturan-aturan tertentu sehingga dapat dibuat algoritma yang lebih sederhana dari pada algoritma quine-McCluskey. Disamping itu, algoritma ini melaksanakan tahap pertama dan tahap kedua dari metode tabulasi sehingga selain menghasilkan Prime Implicant sekaligus juga menghasilkan essential Prime Implicant, meskipun algoritma modifikasi ini memiliki kompleksitas waktu dan space yang sama dengan algoritma Quine-McCluskey yaitu 0(n3) dan 0(n).