Metode Quine McKluskey dan Program Bantu Komputer

Metode Quine McKluskey dan Program Bantu Komputer @2017,Eko Didik Widianto Metode Quine-McKluskey

Metode Quine McKluskey dan Program Bantu Komputer

Program Bantu Komputer Ringkasan Lisensi

Kuliah#6 TSK205 Sistem Digital

Eko Didik Widianto Departemen Teknik Sistem Komputer, Universitas Diponegoro

http://didik.blog.undip.ac.id/buku/sistem-digital/

@2017,Eko Didik Widianto

1


Penyederhanaan Persamaan Logika

@2017,Eko Didik Widianto Metode Quine-McKluskey Program Bantu Komputer

I

Perancangan rangkaian logika minimal memerlukan teknik penyederhanaan persamaan logika I I I

I

secara aljabar peta Karnaugh metode tabular Quine-McCluskey

Metode tabular Quine-McCluskey lebih efisien digunakan di program komputer daripada peta Karnaugh



2

Ringkasan Lisensi


Umpan Balik

@2017,Eko Didik Widianto Metode Quine-McKluskey

I

I

Sebelumnya dibahas tentang optimasi rangkaian dengan penyederhanaan ekspresi logika secara Aljabar, peta Karnaugh dan rangkaian multi-output untuk rangkaian SOP maupun POS


Dalam kuliah ini, akan dibahas tentang: I

I

I

penyederhanaan fungsi logika menggunakan metode tabular Quine-McCluskey program bantu komputer Bmin untuk melakukan sintesis rangkaian logika minimum program bantu komputer simulator rangkaian Qucs untuk analisis rangkaian



3


Kompetensi Dasar


I

Setelah mempelajari bab ini, mahasiswa akan mampu:

Program Bantu Komputer

1. [C3] merancang rangkaian logika minimal dengan menggunakan algoritma/metode tabular Quine-McCluskey 2. [C3] menggunakan perangkat lunak komputer Bmin untuk menyederhanakan rangkaian logika 3. [C5] mengevaluasi hasil rancangan rangkaian logika menggunakan simulator Qucs I

Ringkasan Lisensi

Link I

Website: http://didik.blog.undip.ac.id/2017/03/06/

tkc205-sistem-digital-2016-genap/

I

Email: [email protected]



4


Buku Acuan/Referensi


Eko Didik Widianto, Sistem Digital: Analisis, Desain dan Implementasi, Edisi Pertama, Graha Ilmu, 2014 (Bab 5: Metode Quine-McCluskey dan Program Bantu Komputer) I


Materi: I I

5.1 Metode Quine-McKluskey 5.2 Program Bantu Komputer: Bmin, Qmls, Qucs

I Website: I

http://didik.blog.undip.ac.id/ buku/sistem-digital/



5


Bahasan


Metode Quine-McKluskey Metode QM untuk SOP Metode QM untuk POS Minimal


Program Bantu Komputer Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan

Lisensi



6


Metode Quine-McKluskey (QM) I

Digunakan untuk menyederhanakan fungsi logika sehingga dihasilkan rangkaian logika minimal I

I

I

Disebut juga metode tabular, karena menggunakan tabulasi Dikembangkan oleh W.V. Quine dan Edward J. McCluskey Algoritma ini memberikan hasil yang deterministik untuk memastikan bahwa fungsi logika yang minimal telah tercapai

@2017,Eko Didik Widianto Metode Quine-McKluskey Metode QM untuk SOP Metode QM untuk POS Minimal


(Willard Quine, Wikipedia)

Fungsinya seperti peta Karnaugh, namun lebih efisien untuk digunakan di program komputer

Untuk fungsi dengan lebih dari 4 variabel Namun, jumlah variabel akan menaikan waktu eksekusi (run-time) secara eksponensial@2017,Eko Didik Widianto http://didik.blog.undip.ac.id/buku/sistem-digital/ I I

7


Algoritma Quine-McKluskey


Algoritma Quine McKluskey:

Metode QM untuk SOP

1. Bangkitkan prime implicant 2. Susun tabel prime implicant 3. Sederhanakan tabel

Metode QM untuk POS Minimal

Program Bantu Komputer Ringkasan

3.1 Buang prime implicant esensial. Note: nanti disertakan dalam fungsi akhirnya 3.2 Menghapus row dominance (Maxterm/minterm terbanyak yang dicover oleh prime implicant) 3.3 Memilih column dominance (prime implicant yang mengcover paling banyak Maxterm/minterm)

Lisensi

4. Selesaikan tabel Tujuannya mencari prime implicant esensial (primer, sekunder, dst)



8


Bahasan



Metode QM untuk SOP Metode QM untuk POS Minimal



Lisensi

Ringkasan Lisensi



9


Buat Prime Implicant


Diinginkan rangkaian: P f (x1 , x2 , x3 , x4 ) = m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)

Metode Quine-McKluskey

Langkah 1: Bangkitkan Prime Implicant



I

Baris duplikat dihapus



10


Susun Tabel Prime Implicant


Langkah 2: Susun Tabel Prime Implicant I


Disusun dari langkah 1, kolom 3




11


Hapus Prime Implicant Esensial


Langkah 3a: Hapus Prime Implicant Essensial dari Tabel (Iterasi #1)



I

Prime implicant esensial: x 2 x 4 dan x2 x4 I I

dibuang untuk penyederhanaan lebih lanjut ditambahkan di solusi akhir



12


Hapus Baris Dominan


Langkah 3b: Hapus Baris yang Mendominasi (Dominationg Row)



I

Baris ke-14 dihapus karena setiap term perkalian yang mengkover 6 atau 12 akan mengcover 14

Lisensi

Langkah 3c: Pilih Kolom

I

prime implicant x3 x 4 dan x2 x3 saling mendominasi, bisa dipilih salah satu

I

x1 x 4 dan x1 x2 saling mendominasi, bisa dipilih salah satu



13


Kemungkinan Solusi Pemilihan Prime Implicant





14


Hapus Prime Implicant Esensial Sekunder


Langkah 3a: Hapus Prime Implicant Essensial Sekunder (Iterasi #2) Terdapat 2 solusi



I

Prime implicant esensial sekunder: x3 x 4 dan x1 x 4 atau x2 x3 dan x1 x2 I I

dibuang untuk penyederhanaan lebih lanjut ditambahkan di solusi akhir



15


Solusi Akhir


Langkah 4: Solusi Akhir I I


Tidak ada lagi baris yang perlu disederhanakan Solusi minimum akan berisi prime implicant esensial primer dan sekunder     x3 x 4 + x1 x 4     x3 x 4 + x1 x2 fmin = x 2 x 4 + x2 x4 + | {z }  x2 x3 + x1 x 4      PIE primer x2 x3 + x1 x2 | {z }


PIE sekunder



16


Bahasan






Lisensi

Ringkasan Lisensi



17


Metode QM untuk POS Minimal


I

Diinginkan rangkaian POS dari X f (x1 , x2 , x3 , x4 ) = m (0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15) Y = M (1, 3, 4, 9, 11)



I

Langkah 1: membangkitkan prime implicant



18


Susun Tabel Prime Implicant


Langkah 2: Susun Tabel Prime Implicant




19


Hapus Prime Implicant Esensial


Langkah 3a: Hapus Prime Implicant Essensial dari Tabel (Iterasi #1)



Prime implicant: x2 + x 4 dan x1 + x 2 + x3 + x4 Solusi akhir fmin = (x2 + x 4 ) (x1 + x 2 + x3 + x4 )



20


Program Bantu Komputer I


Program bantu komputer (CAD: Computer-Aided Design) dapat dimanfaatkan untuk desain dan simulasi rangkaian logika I


program desain: untuk mensintesis rangkaian logika dari suatu fungsi logika I I

I

I


Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier

menghasilkan rangkaian logika minimal Bmin - Visualizer of Boolean Minimization (http://bukka.eu/bmin/0.5.0). Program GUI Qt untuk minimalisasi fungsi logika dengan K-Map dan tabular Quine-McKluskey Qmls - Quine-McCluskey Logic Simplifier (http://sourceforge.net/projects/qmls/). Program CLI untuk minimalisasi fungsi logika dengan tabular Quine-McCluskey

Qucs: Simulator Rangkaian

Ringkasan Lisensi

program simulasi/analisis rangkain logika I

Qucs - Quite Universal Circuit Simulator (http://qucs.sourceforge.net/). Program GUI Qt untuk desain dan simulasi rangkaian elektronik, termasuk rangkaian digital



21


Bahasan





Ringkasan Lisensi

Ringkasan Lisensi



22


Bmin: Visualizer of Boolean Minimization


I

Program GUI untuk meminimalkan fungsi logika I I I I I I

Dibuat oleh Jakub Zelenka. Versi terbaru 0.5.0 Pustaka grafis: Qt Masukan: Maxterm dan minterm, don’t care Metode minimalisasi: peta Karnaugh dan Quine-McCluskey Representasi fungsi minimal: SOP dan POS Batasan: I I I

I


Peta Karnaugh untuk fungsi sampai 6 variabel Quine-McCluskey untuk fungsi sampai 10 variabel Nama variabel harus satu buah karakter ASCII

Alamat website: http://bukka.eu/bmin/0.5.0



23

Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi


Menu Utama Bmin

@2017,Eko Didik Widianto Metode Quine-McKluskey Program Bantu Komputer Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi



24

Masukan BminP Fungsi f (x1 , x2 , x3 , x4 ) =

m(2, 3, 7, 9, 11, 13) +

P


d(1, 10, 15)

@2017,Eko Didik Widianto Metode Quine-McKluskey Program Bantu Komputer

I


Jumlah variabel masukan maksimal 10

I

Nama variabel: karakter ascii

I

Nilai variabel: 0, 1, X (don’t care)


25

Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi


Hasil Desain Bmin dengan K-map


I Masukan: f (d, c, b, a) = sum m(2, 3, 7, 8, 11, 13) + sum d(0, 10, 15) I Fungsi sederhana: f (d, c, b, a) = ab + a0 c 0 + acd (output)

Metode Quine-McKluskey Program Bantu Komputer Bmin: Visualisasi Penyederhanaan Boolean Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi



26


Konversi ke POS


I Masukan: f (d, c, b, a) = prod m(1, 4, 5, 6, 9, 12, 14) ∗ prod d(0, 10, 15) I Fungsi sederhana: f (d, c, b, a) = (b + d)(a + c 0 )(a0 + b + c) (output)


Ringkasan Lisensi



27


Hasil Desain Bmin dengan QM


I Masukan: f (d, c, b, a) = sum m(2, 3, 7, 8, 11, 13) + sum d(0, 10, 15) I Fungsi sederhana: f (d, c, b, a) = ab +

a0 c 0

+ acd (output)


Ringkasan Lisensi



28


QM: Konversi ke POS


I Masukan: f (d, c, b, a) = prod m(1, 4, 5, 6, 9, 12, 14) ∗ prod d(0, 10, 15) I Fungsi sederhana: f (d, c, b, a) = (b + d)(a +

c 0 )(a0

+ b + c) (output)


Ringkasan Lisensi



29


Persamaan 10 Variabel I Nyatakan persamaan minimal fungsi f (j, i, h, g, f , e, d, c, b, a) =

P (1, 73, 75, 77, 79, 203, 205, 207, 329, 331, 335, 463, 1023) + d(201, 333, 457, 459, 461) menggunakan bmin


Ringkasan Lisensi



30


Bahasan





Ringkasan Lisensi

Ringkasan Lisensi



31


Qmls: Quine-McCluskey Logic Simplifier


I


Program CLI (command line interface) untuk meminimalkan fungsi logika I

I I

I I

Bmin: Visualisasi Penyederhanaan Boolean

Dibuat oleh Dannel Albert . Versi terbaru 0.2 CLI, masukan diberikan dari command line atau file teks Masukan: minterm, don’t care I

I


Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi

Nama variabel: string sebarang, bisa dengan indeks (misalnya: x4, a1 dan seterusnya)

Metode minimalisasi: Quine-McCluskey Representasi fungsi minimal: SOP Alamat website: http://sourceforge.net/projects/qmls/



32


Masukan Fungsi dari File Teks


Ringkasan Lisensi

I I

Dari fungsi f (x1 , x2 , x3 , x4 ) = m(2, 3, 7, 8, 11, 13) + d(0, 10, 15) Menghasilkan fungsi sederhana yang sama: f (x1 , x2 , x3 , x4 ) = x3 x4 + x20 x40 + x1 x2 x4



33


Fungsi dengan 10 Variabel (Qmls)


Ringkasan Lisensi

I Fungsi: f (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 ) =

m(1023, 73, 75, 77, 79, 203, 205, 207, 329, 331, 335, 463, 1) + d(201, 333, 457, 459, 461) I Fungsi sederhana:

f (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 ) = x1x2x3x4x5x6x7x8x9x10 + x10 x4x50 x60 x7x10 + x10 x20 x30 x40 x50 x60 x70 x80 x90 x10



34


Bahasan





Ringkasan Lisensi

Ringkasan Lisensi



35


Qucs Simulator Rangkaian


I


Qucs (Quite Universal Circuit Simulator) I

I

I I

I

Bmin: Visualisasi Penyederhanaan Boolean

untuk mensimulasikan rangkaian elektronika secara umum, termasuk rangkaian digital (logika) dikembangkan oleh Michael Margraf dan berbasis pustaka grafis Qt dapat dijalankan di Linux atau Windows masukan program adalah berupa skematik rangkaian logika yang tersusun atas gerbang logika dan interkoneksinya Alamat website: http://qucs.sourceforge.net/



36

Qmls: Quine-McCluskey Logic Simplifier Qucs: Simulator Rangkaian

Ringkasan Lisensi


Simulasi Rangkaian dengan Qucs


I

Skematik rangkaian fmin = x 2 x 4 + x2 x4 + x3 x 4 + x1 x 4


I

Simulasi digital menggunakan tabel kebenaran


Ringkasan Lisensi



37


Hasil Simulasi dengan Qucs


Ringkasan Lisensi



38


Contoh


I

Verifikasi rangkaian P logika fungsi P f (x1 , x2 , x3 , x4 ) = m(2, 3, 7, 9, 11, 13) + d(0, 10, 15)


Ringkasan Lisensi



39


Contoh: Hasil Simulasi


Ringkasan Lisensi



40


Ringkasan Kuliah


I

Yang telah kita pelajari hari ini: I

I

I


Latihan: I

I


Penyederhanaan fungsi logika menggunakan metode tabular Quine-McKluskey untuk aplikasi komputer Program bantu komputer untuk melakukan sintesis rangkaian logika minimum dan analisis rangkaian, yaitu Bmin, Qmls dan Qucs

Lihat Tugas#3

Yang akan kita pelajari di pertemuan berikutnya adalah teknologi CMOS dan chip terintegrasi TTL (transistor-transistor logic) untuk mengimplementasikan gerbang logika I

Pelajari: http://didik.blog.undip.ac.id/2017/03/06/ tkc205-sistem-digital-2016-genap/



41


Lisensi


Creative Common Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)


I Anda bebas: I

I


untuk Membagikan — untuk menyalin, mendistribusikan, dan menyebarkan karya, dan untuk Remix — untuk mengadaptasikan karya

Ringkasan Lisensi

I Di bawah persyaratan berikut: I

I

Atribusi — Anda harus memberikan atribusi karya sesuai dengan cara-cara yang diminta oleh pembuat karya tersebut atau pihak yang mengeluarkan lisensi. Atribusi yang dimaksud adalah mencantumkan alamat URL di bawah sebagai sumber. Pembagian Serupa — Jika Anda mengubah, menambah, atau membuat karya lain menggunakan karya ini, Anda hanya boleh menyebarkan karya tersebut hanya dengan lisensi yang sama, serupa, atau kompatibel.

I Lihat: Creative Commons Attribution-ShareAlike 3.0 Unported License I Alamat URL: http://didik.blog.undip.ac.id/buku/sistem-digital/



42

Metode Quine McKluskey dan Program Bantu Komputer

Recommend Documents