Sintesis dan Penyederhanaan Fungsi Logika dengan Peta Karnaugh Hadha Afrisal, 35448-TE Jurusan Teknik Elektro FT UGM, Yogyakarta
1.1
PENDAHULUAN
Telah dutunjukkan pada bab sebelumnya bahwa penyederhanaan fungsi Boolean secara aljabar cukup membosankan dan hasilnya dapat berbeda tiap-tiap orang yang menyederhanakan, tergantung kemampuan logika dan pola masing-masing orang. Hasil penyederhanaan juga belum tentu fungsi minimum, padahal yang menjadi tujuan penyederhanaan adalah memperoleh fungsi logika yang paling sederhana, sehingga implementasi di hardware juga paling sederhana. Cara lain untuk mempermudah proses penyederhanaan adalah menggunakan Karnaugh Mapping. Peta Karnaugh menggambarkan harga atau keadaan suatu fungsi logika untuk setiap kombinasi masukan yang mungkin dibentuk. Jadi sebenarnya, peta Karnaugh memetakan tabel kebenaran dalam kotak-kotak segi empat yang jumlahnya tergantung dari jumlah peubah masukan. Untuk fungsi dengan 2 buah variabel, peta Karnaugh akan terdiri dari 22 kotak, sedangkan untuk 3 buah variabel memiliki 23 kotak dan seterusnya. Dimana tiap kotak merepresentasi nilai 0 dan 1 yang menunjukkan keadaan fungsi. Namun untuk mempermudah, biasanya dibuat peta Karnaugh dengan 4 kotak, sehingga jika masukan lebih dari 2, maka akan dilakukan kombinasi masukan. Peta Karnaugh juga memudahkan menyederhanakan fungsi yang memiliki banyak output yang tidak mampu ditangani dengan penyederhanaan secara aljabar. 1.2
TERMINOLOGI
Banyaknya penelitian mengenai teknik sintesis dan penyederhanaan sistem logika, mengakibatkan banyaknya paper dan jurnal yang menggunakan istilah-istilah yang berbeda-beda, padahal hal yang dimaksud merupakan hal yang sama. Sehingga pada bab ini akan diberikan beberapa istilah dan artinya. Literal Sebuah product term terdiri dari kombinasi beberapa variabel, jumlah variabel yang menyusun sebuah product term itulah yang disebut Literal. = 3 literal = 4 literal Implicant Implicant merupakan product term yang memilki nilai logika output 1 (minterm). Sebagai contoh adalah pada Gambar 1, implicant berjumlah 11, yaitu 5 buah minterm 3 lateral, 5 buah minterm 2 lateral, dan 1 buah minterm 1 lateral. minterm 3 lateral
minterm 2 literal
minterm 1 literal Prime Implicant Prime implicant merupakan implicant yang paling sederhana, sehingga tidak bisa disederhanakan lagi menjadi implicant-implicant yang lebih kecil.
Gambar 1. Peta Karnaugh dengan metode penyederhanaan SOP untuk fungsi logika 1.
Sehingga dari peta Karnaugh Gambar 1, prime implicant adalah, Cover Merupakan representasi dari fungsi logika, yang berupa kumpulan dari implicant-implicant.
merupakan cover implementasi fungsi Gambar 1 sebelum disederhanakan.
merupakan cover yang juga valid dari fungsi Gambar 1. merupakan cover yang paling sederhana dari fungsi Gambar 1. Cost Cost merupakan jumlah dari gerbang logika yang digunakan ditambah jumlah input-input dari semua gerbang logika dari rangkaian. Seperti misalnya pada Gambar 1, dimana fungsi logika sudah disederhanakan, maka jumlah total cost-nya adalah 6, yaitu 3 buah gerbang logika (AND 1 buah, OR 1 buah, NOT 1 buah), dan 3 buah masukan.
1.3
PROSEDUR MINIMISASI FUNGSI LOGIKA
Pada perancangan rangkaian logika, salah satu hal terpenting adalah memperoleh fungsi logika yang paling sederhana, yaitu cover terdiri dari prime implicant. Namun selain itu, pada beberapa kasus, misal pada PLD (Programmable Logic Devices) beberapa implicant yang penting dan mempengaruhi proses tertentu harus disertakan, yang disebut essential implicant. Sehingga fungsi logika yang dihasilkan bukanlah yang paling sederhana, namun merupakan rangkaian paling minimum yang sudah meliputi fungsi-fungsi tertentu. Untuk nilai logika don’t care (D), nilai bisa dianggap bernilai 1 atau 0, sehingga pada proses sintesis bisa digunakan ataupun tidak. Pada bagian ini akan dijelaskan cara memasukkan essential implicant ke dalam fungsi logika. Sebagai contoh adalah Gambar 2.
Gambar 2. Peta Karnaugh dengan metode penyederhanaan SOP untuk fungsi logika 2.
Misalnya, pada sebuah perancangan, essential implicant yang ditentukan adalah sebagai berikut,
maka pada perancangan, implicant tersebut wajib disertkan. Ketiga essential implicant tersebut sudah meliputi semua minterm kecuali m7 sehingga, kita juga harus menyertakan prime implicant yang belum dianggap sebagai essential implicant ke dalam fungsi logika. , kedua prime implicant tersebut
sama-sama meliputi m7 sehingga bisa dipilih salah satu. akhirnya bisa dipilih karena memiliki bentuk yang lebih sederhana. Sehingga fungsi logika yang terbentuk adalah,
Sehingga tahapan-tahapan dalam sintesis dan penyederhanaan fungsi logika adalah, 1. Menentukan semua prime implicant dengan metode peta Karnaugh. 2. Menentukan essential implicant. 3. Jika essential implicant bisa meliputi semua minterm (yang menghasilkan f=1), maka cover dapat langsung ditentukan dengan menggunakan essential implicant. 4. Namun jika tidak, cover harus ditentukan dengan cara menambahkan prime implicant. Pemilihan prime implicant ditentukan dengan mempertimbangkan cost yang paling rendah. 1.4
SINTESIS DAN PENYEDERHANAAN FUNGSI LOGIKA DENGAN CARA PRODUCT OF SUM
Pada bab-bab sebelumnya proses sintesis dan penyederhanaan dilakukan dengan metode Sum of Product (SOP). Pada bab ini kita akan membahas mengenai sintesis dan penyederhanaan fungsi logika dengan metode POS. Dalam suatu fungsi, ada kemungkinan implementasi SOP dan POS-nya memiliki cost yang berbeda, sehingga kemungkinan engineer digital akan membandingkan 2 jenis implementasi itu. Gambar 3 merupakan peta Karnaugh yang sama dengan Gambar 1, bedanya adalah sintesis dan penyederhanaan dilakukan dengan metode POS.
Gambar 3. Peta Karnaugh dengan metode penyederhanaan POS untuk fungsi logika 1.
Fungsi logika yang disintesis adalah sebagai berikut,
Gambar 4. Peta Karnaugh dengan metode penyederhanaan POS untuk fungsi logika 2.
Fungsi logika yang disintesis adalah sebagai berikut,
Dari fungsi-fungsi yang disintesis dengan POS tersebut jika dibandingkan dengan sintesis dengan SOP akan memiliki cost yang berbeda. Fungsi pertama (pada Gambar 1/Gambar 3) memiliki cost yang lebih besar daripada jika disintesis dengan metode SOP. Namun fungsi kedua (pada Gambar 2/Gambar 4) sintesis POS menghasilkan cost yang lebih kecil daripada SOP. Selain menggunakan metode peta Karnaugh, untuk membandingkan implementasi SOP ke POS atau sebaliknya bisa dilakukan dengan menggunakan teorema DeMorgan. Untuk fungsi logika pertama,
Untuk fungsi logika kedua,
1.5
RANGKAIAN LOGIKA MULTIPLE OUTPUT
Dari bab-bab sebelumnya, rangkaian yang disintesis memiliki multiple input dengan single output, pada bab ini selanjutnya akan dibahas rangakaian logika multiple output, atau bisa juga disebut gate-sharing. Adanya gate-sharing ini memungkinkan implementasi yang lebih murah untuk rangkaian digital dengan fungsi yang berbeda. Sebagai contoh adalah 2 buah fungsi berikut, f1 dan f2.
Gambar 5. f1 (Fungsi logika 1)
Gambar 6. f2 (Fungsi logika 2)
Gambar 7. Hasil implementasi multiple output fungsi 1 dan 2
REFERENCES [1] Stephen Brown, Zvonko Vranesic, “Fundamentals of Digital Logic with Verilog Design” [2] R. Hidayat, “Paper Template in One-Column Format”, http://www.te.ugm.ac.id/~risanuri
