Metode Minimisasi Quine McKluskey dan Rangkaian Multilevel

Metode Minimisasi Quine McKluskey dan Rangkaian Multilevel Eko Didik Widianto ([email protected]) Sistem Komputer - Universitas Diponegoro

@2011 eko didik widianto (http://didik.blog.undip.ac.id)

TSK205 Sistem Digital - Siskom Undip – 1 / 27

Review Kuliah • Sebelumnya ◦ minimisasi rangkaian logika menggunakan peta Karnaugh baik untuk bentuk ekspresi SOP maupun POS ◦ Minimisasi rangkaian multi-output ◦ Rangkain SOP/POS tersebut adalah rangkaian 2 level: AND-OR, OR-AND, NAND-NAND, dan NOR-NOR (level1-level2) • Selanjutnya ◦ minimisasi rangkaian menggunakan metode Quine-McKluskey •

Minimisasi rangkaian: aljabar, K-map, Quine-McKluskey

◦ sintesis dan analisis rangkaian multilevel (lebih dari 2 level)



Bahasan Metode Quine-McKluskey Metode Quine-McKluskey Rangkaian Multilevel Rangkaian 2-Level Sintesis Multilevel Teknik Faktoring Kompleksitas Wiring Dekomposisi Fungsional Analisis Multilevel



Metode Quine-McKluskey

• Metode Quine-McKluskey Rangkaian Multilevel

Metode Quine-McKluskey



Metode Tabular Quine-McKluskey Metode Quine-McKluskey

• Metode Quine-McKluskey

Algoritma Quine McKluskey:

Rangkaian Multilevel

1. Bangkitkan prime implicant 2. Susun tabel prime implicant 3. Sederhanakan tabel (a) Buang prime implicant esensial. Note: nanti disertakan dalam fungsi akhirnya (b) Row dominance

(Willard Quine, Wikipedia)

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



Contoh Problem Metode Quine-McKluskey


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

• Baris duplikat dihapus





Langkah 2: Susun Tabel Prime Implicant

• Disusun dari langkah 1, kolom 3



Contoh Problem: Iterasi #1 Metode Quine-McKluskey


Langkah 3a: Hapus Prime Implicant Essensial


• Prime implicant esensial: x2 x4 dan x2 x4 ◦ dibuang untuk penyederhanaan lebih lanjut ◦ ditambahkan di solusi akhir





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


• Baris ke-14 dihapus karena setiap term perkalian yang mengkover 6 atau 12 akan mengcover 14 Langkah 3c: Pilih Kolom

• prime implicant x3 x4 dan x2 x3 saling mendominasi, bisa dipilih salah satu • x1 x4 dan x1 x2 saling mendominasi, bisa dipilih salah satu @2011 eko didik widianto (http://didik.blog.undip.ac.id)


Contoh Problem: Iterasi #2 Metode Quine-McKluskey


Langkah 3a: Hapus Prime Implicant Essensial Sekunder Terdapat 2 solusi

• Prime implicant esensial sekunder: x3 x4 dan x1 x4 atau x2 x3 dan x1 x2 ◦ dibuang untuk penyederhanaan lebih lanjut ◦ ditambahkan di solusi akhir @2011 eko didik widianto (http://didik.blog.undip.ac.id)




Langkah 4: Solusi Akhir

• Tidak ada lagi baris yang perlu disederhanakan • Solusi minimum akan berisi prime implicant esensial primer dan sekunder • fmin = x2 x4 + x2 x4 +


x3 x4 + x1 x4 x2 x3 + x1 x2


Contoh Problem: Simulation/Analisis Metode Quine-McKluskey


• Skematik rangkaian fmin = x2 x4 + x2 x4 + x3 x4 + x1 x4 • Simulasi dengan Qucs (Quite Universal Circuit Simulator)



Contoh Problem: Diagram Pewaktuan Metode Quine-McKluskey


• Diagram pewaktuanP f (x1 , x2 , x3 , x4 ) = m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)



Latihan Metode Quine-McKluskey


Diinginkan rangkaian: P

f (x1 , x2 , x3 , x4 ) =


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

P

d(1, 1015)


Metode Quine-McKluskey Rangkaian Multilevel

• Rangkaian 2-Level • Sintesis Multilevel • Teknik Faktoring • Kompleksitas Wiring • Dekomposisi Fungsional • Analisis Multilevel




Implementasi Rangkaian 2-Level Metode Quine-McKluskey Rangkaian Multilevel


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



Problem Fan-in Metode Quine-McKluskey Rangkaian Multilevel


• Saat jumlah masukan bertambah, rangkaian 2-level akan menemui kendala fan-in ◦ 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 -> dikonversi menjadi fungsi dengan term 2-literal

• Kendala fan-in lainnya adalah delay propagasi ◦ 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 Metode Quine-McKluskey Rangkaian Multilevel


• Misalnya: f (x1 , ..., x7 ) = x1 x3 x6 + x1 x4 x5 x6 + x2 x3 x7 + x2 x4 x5 x7 • 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 Metode Quine-McKluskey Rangkaian Multilevel


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

◦ 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 Rangkaian Multilevel


• Untuk mengatasinya, fungsi harus dinyatakan dalam ekspresi logika multilevel ◦ Hanya mengandung term dengan 2 literal ◦ Implikasinya: rangkaian bisa lebih dari 2 level −→multilevel • Teknik sintesis multilevel: ◦ Faktoring ◦ Dekomposisi fungsi



Teknik Faktoring Metode Quine-McKluskey Rangkaian Multilevel


• Memanfaatkan hukum distributif untuk menuliskan ekspresi dengan term ber-literal lebih sedikit −→implementasi di FPGA dg LUT 2-masukan f (x1 , ..., x7 )


=

x1 x3 x6 + x1 x4 x5 x6 + x2 x3 x7 + x2 x4 x5 x7

=

x1 x6 (x3 + x4 x5 ) + x2 x7 (x3 + x4 x5 )

=

(x1 x6 + x2 x7 ) (x3 + x4 x5 )


Contoh Faktoring Metode Quine-McKluskey Rangkaian Multilevel

• Diberikan:



f

= x1 x2 x3 x4 x5 x6 + x1 x2 x3 x4 x5 x6 = x1 x3 x4 (x2 x5 x6 + x2 x5 x6 )




• Nyatakan ekspresi berikut agar hanya membutuhkan gerbang AND dan OR 2-masukan! • f (x1 , ..., x7 ) = x1 x2 x4 x5 + x1 x2 x6 x7 + x3 x4 x5 + x3 x6 x7





• Nyatakan ekspresi berikut agar hanya membutuhkan gerbang AND dan OR 2-masukan! • f (x1 , ..., x7 ) = x1 x2 x4 x5 + x1 x2 x6 x7 + x3 x4 x5 + x3 x6 x7

f (x1 , ..., x7 )


= x1 x2 x4 x5 + x1 x2 x6 x7 + x3 x4 x5 + x3 x6 x7 = x1 x2 (x4 x5 + x6 x7 ) + x3 (x4 x5 + x6 x7 ) = (x1 x2 + x3 ) (x4 x5 + x6 x7 )


Kompleksitas Wiring Metode Quine-McKluskey Rangkaian Multilevel


• Space di Integrated Circuit (IC) ditempati oleh ◦ 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: ◦ ◦ ◦ ◦

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



Teknik Dekomposisi Fungsional Metode Quine-McKluskey Rangkaian Multilevel


• Rangkaian dapat didekomposisi menjadi sub-sub rangkaian ◦ 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 logika 2-level digantikan dengan dua atau lebih ekspresi ◦ Ekspresi-ekspresi tersebut dikombinasikan untuk membentuk rangkaian multilevel • CAD banyak memanfaatkan konsep dekomposisi fungsi ◦ Mengimplementasikan fungsi general dengan konstrain •

Fungsi harus ’fit’ di block logika yang tersedia



Contoh Dekomposisi Metode Quine-McKluskey

Ekspresi minimum: f = x1 x2 x3 + x1 x2 x3 + x1 x2 x4 + x1 x2 x4



• 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 = (x1 x2 + x1 x2 ) x3 + (x1 x2 + x1 x2 ) x4 • Misalkan g(x1 , x2 ) = (x1 x2 + x1 x2 ) • Perhatikan:

g

= = = =

(x1 x2 + x1 x2 ) = x1 x2 x1 x2 (x1 + x2 ) (x1 + x2 ) x1 x1 + x1 x2 + x2 x1 + x2 x2 x1 x2 + x1 x2

• Sehingga, f dapat dinyatakan: f = gx3 + gx4 • g adalah subfungsi. f (x1 , x2 , x3 , x4 ) = h [g(x1 , x2 ), x3 , x4 ] • Implementasi rangkaian? @2011 eko didik widianto (http://didik.blog.undip.ac.id)


Analisis Rangkaian Multilevel Metode Quine-McKluskey Rangkaian Multilevel




Metode Minimisasi Quine McKluskey dan Rangkaian Multilevel

Recommend Documents