Rangkaian Multilevel

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey

Metode Quine McKluskey dan Rangkaian Multilevel Kuliah#5 TSK205 Sistem Digital - TA 2011/2012

Eko Didik Widianto Teknik Sistem Komputer - Universitas Diponegoro

Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan Lisensi

Umpan Balik


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-McKluskey untuk aplikasi komputer Program bantu komputer untuk melakukan sintesis rangkaian logika minimum dan analisis rangkaian, yaitu Bmin, Qmls dan Qucs Sintesis dan analisis rangkaian multilevel (lebih dari 2 level)


Kompetensi Dasar

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto

I

Setelah mempelajari bab ini, mahasiswa akan mampu: 1. [C2] Mahasiswa akan mampu memahami algoritma/metode tabular Quine-McKluskey untuk fungsi logika sehingga dihasilkan rangkaian yang minimum 2. [C3] Mahasiswa akan mampu menggunakan perangkat lunak komputer untuk menyederhanakan rangkaian logika dan untuk menganalisis rangkaian logika minimum 3. [C5] Mahasiswa akan mampu mendesain dan menganalisis rangkaian multilevel dengan tepat jika diberikan konstrain jumlah fan-in yang terbatas di teknologi implementasi chip, misalnya di FPGA jumlah masukan maksimal gerbang adalah 3 buah masukan

I

Link I

Website: http://didik.blog.undip.ac.id/2012/02/24/

kuliah-sistem-digital-tsk-205-2011/

I

Email: [email protected]

Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan Lisensi

Bahasan


Metode Quine-McKluskey Algoritma Quine-McCluskey Simulasi dan Analisis Rangkaian Program Bantu Komputer Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan Lisensi


Metode Quine McKluskey dan Rangkaian Multilevel

Metode Quine-McKluskey (QM) I

@2012,Eko Didik Widianto

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 and Edward J. McCluskey Algoritma ini memberikan hasil yang deterministik untuk memastikan bahwa fungsi logika yang minimal telah tercapai Fungsinya seperti peta Karnaugh, namun lebih efisien untuk digunakan di program komputer I

I

Untuk fungsi dengan lebih dari 4 variabel Namun, jumlah variabel akan menaikan waktu eksekusi

Metode Quine-McKluskey Algoritma Quine-McCluskey Simulasi dan Analisis Rangkaian Program Bantu Komputer


(Willard Quine, Wikipedia)

Bahasan




Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan


Lisensi

Algoritma Quine-McKluskey


Algoritma Quine McKluskey: 1. Bangkitkan prime implicant 2. Susun tabel prime implicant 3. Sederhanakan tabel 3.1 Buang prime implicant esensial. Note: nanti disertakan dalam fungsi akhirnya 3.2 Row dominance 3.3 Column dominance

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

Algoritma Quine-McCluskey Simulasi dan Analisis Rangkaian Program Bantu Komputer


Buat Prime Implicant


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

Langkah 1: Bangkitkan Prime Implicant



I

Baris duplikat dihapus

Susun Tabel Prime Implicant


Langkah 2: Susun Tabel Prime Implicant I

Disusun dari langkah 1, kolom 3



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

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

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Algoritma Quine-McCluskey Simulasi dan Analisis Rangkaian Program Bantu Komputer

Rangkaian Multilevel Bacaan Lebih Lanjut

I

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

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

Ringkasan Lisensi

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

Solusi Akhir


Langkah 4: Solusi Akhir I 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 fmin = x 2 x 4 + x2 x4 + x2 x3 + x1 x2


Bahasan






Lisensi

Simulasi dan Analisis Rangkaian


I

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



Diagram Pewaktuan


I

Diagram pewaktuan P f (x1 , x2 , x3 , x4 ) =

m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)



Latihan


Rangkaian Multilevel

Diinginkan rangkaian: P P f (x1 , x2 , x3 , x4 ) = m(2, 3, 7, 9, 11, 13) + d(1, 10, 15)

Bacaan Lebih Lanjut Ringkasan Lisensi

I

Akan dikerjakan dengan software di slide berikutnya

Bahasan






Lisensi

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

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

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



Bmin: Visualizer of Boolean Minimization

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Algoritma Quine-McCluskey

I

Program GUI untuk meminimalkan fungsi logika

Simulasi dan Analisis Rangkaian Program Bantu Komputer

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


Menu Utama Bmin



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


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

P

d(1, 10, 15)

@2012,Eko Didik Widianto Metode Quine-McKluskey Algoritma Quine-McCluskey Simulasi dan Analisis Rangkaian Program Bantu Komputer

I

Jumlah variabel masukan maksimal 10

I

Nama variabel: karakter ascii

I

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


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)



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)



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)



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)



Qmls: Quine-McCluskey Logic Simplifier


I

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

I I

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

I I I

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/



Masukan Fungsi dari File Teks



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

Fungsi dengan 10 Variabel (Bmin) I Masukan: f ((j, i, h, g, f , e, d, c, b, a) =

sum m(1, 73, 75, 77, 79, 203, 205, 207, 329, 331, 335, 463, 1023) + sum d(201, 333, 457, 459, 461) I Fungsi sederhana: f (j, i, h, g, f , e, d, c, b, a) = ab0 c 0 d 0 e0 f 0 g 0 h0 i 0 j 0 + ade0 f 0 gj 0 + abcdefghij (output)



Fungsi dengan 10 Variabel (Qmls)



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

Qucs: Quite Universal Circuit Simulator


I

Program GUI untuk mensimulasikan rangkaian elektronika, termasuk rangkaian digital I

I I I

Dibuat oleh Michael Margraf. Versi yang digunakan 0.0.15 (2009, uBuntu Lucid) Pustaka grafis: Qt Masukan: skematik rangkaian digital Alamat website: http://qucs.sourceforge.net/


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



Hasil Simulasi dengan Qucs



Implementasi Rangkaian 2-Level


I

Rangkaian 2-level AND-OR dan NAND-NAND dibentuk dari persamaan SOP OR-AND dan NOR-NOR dibentuk dari persamaan POS


Problem Fan-in


I

Saat jumlah masukan bertambah, rangkaian 2-level akan menemui kendala fan-in I

I

I

I

Fan-in: jumlah input ke suatu gerbang atau komponen rangkaian tertentu Tergantung teknologi yang digunakan untuk mengimplementasikan rangkaian Di CPLD, fungsi SOP 2-level dengan tiap term lebih dari 2 literal dapat langsung diimplementasikan Di FPGA dengan LUT 2-masukan, fungsi tersebut tidak dapat langsung diimplementasikan I

I

Perlu dikonversi menjadi fungsi dengan term 2-literal

Kendala fan-in lainnya adalah delay propagasi I

I

propagasi delay: waktu yang dibutuhkan untuk mempropagasikan nilai masukan sampai ke keluaran gerbang Jumlah masukan semakin banyak, delay propagasi akan bertambah


Implementasi fungsi di CPLD


I

Misalnya: f (x1 , ..., x7 ) = x1 x3 x 6 + x1 x4 x5 x 6 + x2 x3 x7 + x2 x4 x5 x7

I

Di CPLD, implementasi fungsi ini tidak ada masalah, karena mempunyai cukup masukan (7 input), gerbang AND (1 per term perkalian) dan gerbang OR (satu per keluaran AND)


Implementasi fungsi di FPGA


I I

Misalnya: f (x1 , ..., x7 ) = x1 x3 x 6 + x1 x4 x5 x 6 + x2 x3 x7 + x2 x4 x5 x7 Di FPGA dengan LUT 2-masukan, fungsi tidak dapat langsung diimplementasikan I

I

I

Fungsi f mempunyai term dengan 3 dan 4 literal, memerlukan gerbang AND 3-masukan dan 4-masukan Terdapat 4 term perkalian yang harus di-OR-kan, memerlukan gerbang OR 4-masukan

Fan-in yang diperlukan untuk mengimplementasikan fungsi ini terlalu banyak untuk FPGA


Sintesis Multilevel

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut

I

Untuk mengatasinya, fungsi harus dinyatakan dalam ekspresi logika multilevel I I

I

Hanya mengandung term dengan 2 literal Implikasinya: rangkaian bisa lebih dari 2 level −→multilevel

Teknik sintesis multilevel: I I

Faktoring Dekomposisi fungsi

Ringkasan Lisensi


Teknik Faktoring I

Memanfaatkan hukum distributif untuk menuliskan ekspresi dengan term ber-literal lebih sedikit −→implementasi di FPGA dg LUT 2-masukan

@2012,Eko Didik Widianto Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut

f (x1 , ..., x7 )

=

x1 x3 x 6 + x1 x4 x5 x 6 + x2 x3 x7 + x2 x4 x5 x7

Ringkasan

=

x1 x 6 (x3 + x4 x5 ) + x2 x7 (x3 + x4 x5 )

Lisensi

=

(x1 x 6 + x2 x7 ) (x3 + x4 x5 )

Contoh Faktoring


I

Diberikan:

Metode Quine-McKluskey

f

= =

x1 x 2 x3 x 4 x5 x6 + x1 x2 x3 x 4 x 5 x 6 x1 x3 x 4 (x 2 x5 x6 + x2 x 5 x 6 )


Contoh Faktoring


I

I

Nyatakan ekspresi berikut agar hanya membutuhkan gerbang AND dan OR 2-masukan! f (x1 , ..., x7 ) = x1 x 2 x 4 x5 + x1 x 2 x6 x 7 + x 3 x 4 x5 + x 3 x6 x 7

f (x1 , ..., x7 )

=

x1 x 2 x 4 x5 + x1 x 2 x6 x 7 + x 3 x 4 x5 + x 3 x6 x 7

=

x1 x 2 (x 4 x5 + x6 x 7 ) + x 3 (x 4 x5 + x6 x 7 )

=

(x1 x 2 + x 3 ) (x 4 x5 + x6 x 7 )

Ringkasan Lisensi

Contoh Faktoring


I

I

Nyatakan ekspresi berikut agar hanya membutuhkan gerbang AND dan OR 2-masukan! f (x1 , ..., x7 ) = x1 x 2 x 4 x5 + x1 x 2 x6 x 7 + x 3 x 4 x5 + x 3 x6 x 7

f (x1 , ..., x7 )

=

x1 x 2 x 4 x5 + x1 x 2 x6 x 7 + x 3 x 4 x5 + x 3 x6 x 7

=

x1 x 2 (x 4 x5 + x6 x 7 ) + x 3 (x 4 x5 + x6 x 7 )

=

(x1 x 2 + x 3 ) (x 4 x5 + x6 x 7 )

Ringkasan Lisensi

Kompleksitas Wiring


I

Space di Integrated Circuit (IC) ditempati oleh I I

I I I

Gerbang-gerbang penyusun rangkaian Wire yang dibutuhkan untuk menghubungkan gerbang

Tiap literal dari suatu ekspresi logika diimplementasikan dengan 1 wire yang membawa sinyal logik yang diinginkan Faktoring mengurangi jumlah literal, sehingga dapat digunakan untuk mengurangi kompleksitas dalam rangkaian logika Parameter dalam sintesis: I I I I

cost rangkaian (jumlah gerbang) fan-in kecepatan rangkaian yang dihasilkan kompleksitas wire


Teknik Dekomposisi Fungsional


I

Rangkaian dapat didekomposisi menjadi sub-sub rangkaian I

I

I

Ekspresi logika 2-level digantikan dengan dua atau lebih ekspresi I

I

Mengurangi kompleksitas rangkaian di wiring dan gerbang logika Satu atau beberapa sub-rangkaian mengimplementasikan fungsi yang digunakan di beberapa bagian untuk membentuk rangkaian lengkapnya

Ekspresi-ekspresi tersebut dikombinasikan untuk membentuk rangkaian multilevel

CAD banyak memanfaatkan konsep dekomposisi fungsi I

Mengimplementasikan fungsi general dengan konstrain I

Fungsi harus ’fit’ di block logika yang tersedia


Contoh Dekomposisi Ekspresi minimum: f = x 1 x2 x3 + x1 x 2 x3 + x1 x2 x4 + x 1 x 2 x4 I

I I I I

Rangkaian diimplementasikan dengan 4 gerbang AND, 1 gerbang OR, dan 2 gerbang NOT dan 18 masukan ke semua gerbang Fan-in=3 untuk gerbang AND dan 4 untuk gerbang OR Faktoring: f = (x 1 x2 + x1 x 2 ) x3 + (x1 x2 + x 1 x 2 ) x4 Misalkan g(x1 , x2 ) = (x 1 x2 + x1 x 2 ) Perhatikan: g = (x 1 x2 + x1 x 2 ) = x 1 x2 x1 x 2 =

(x1 + x 2 ) (x 1 + x2 )

= x1 x 1 + x1 x2 + x 2 x 1 + x 2 x2 = x1 x2 + x 1 x 2 I I I

Sehingga, f dapat dinyatakan: f = gx3 + gx4 g adalah subfungsi. f (x1 , x2 , x3 , x4 ) = h [g(x1 , x2 ), x3 , x4 ] Implementasi rangkaian?

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan Lisensi

Analisis Rangkaian Multilevel

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan Lisensi

Bacaan Lebih Lanjut

Metode Quine McKluskey dan Rangkaian Multilevel @2012,Eko Didik Widianto Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut Ringkasan

1. Website project bmin: http://bukka.eu/bmin/0.5.0 2. Website project qmls: http://qmls.sourceforge.net/ 3. Qucs: Getting Started with Digital Circuit Simulation. Download: http://qucs.sourceforge.net/docs/digital.pdf

Lisensi

Ringkasan Kuliah


I

Yang telah kita pelajari hari ini: I

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 Sintesis dan analisis rangkaian multilevel (lebih dari 2 level)

Lihat Tugas#3

Yang akan kita pelajari di pertemuan berikutnya adalah teknologi CMOS untuk mengimplementasikan gerbang logika I

Pelajari: http://didik.blog.undip.ac.id/files/2011/ 03/TSK205-Kuliah6-CMOS_TinjauanPraktikal.pdf



Lisensi

@2012,Eko Didik Widianto

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

Anda bebas:

Metode Quine-McKluskey Rangkaian Multilevel Bacaan Lebih Lanjut

I

I

I

Di bawah persyaratan berikut: I

I

I

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

Atribusi — Anda harus memberikan atribusi karya sesuai dengan cara-cara yang diminta oleh pembuat karya tersebut atau pihak yang mengeluarkan lisensi. 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.

Lihat: Creative Commons Attribution-ShareAlike 3.0 Unported License

Ringkasan Lisensi

Rangkaian Multilevel

Recommend Documents