�ݺ�ߣ

Metode Minimisasi Quine McKluskey dan Rangkaian Multilevel

Eko Didik Widianto (didik@undip.ac.id)

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
Rangkaian Multilevel
Rangkaian 2-Level
Sintesis Multilevel
Teknik Faktoring
Kompleksitas Wiring
Dekomposisi Fungsional
Analisis Multilevel


• Metode Quine-McKluskey




Metode Tabular Quine-McKluskey

• Metode Quine-McKluskey Algoritma Quine McKluskey:
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

Diinginkan rangkaian:
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


Contoh Problem

Langkah 2: Susun Tabel Prime Implicant
• Disusun dari langkah 1, kolom 3


Contoh Problem: Iterasi #1

Langkah 3a: Hapus Prime Implicant Essensial

• Prime implicant esensial: x2 x4 dan x2 x4

◦ dibuang untuk penyederhanaan lebih lanjut
◦ ditambahkan di solusi akhir


Contoh Problem

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


Contoh Problem: Iterasi #2

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

Contoh Problem

Langkah 4: Solusi Akhir
• Tidak ada lagi baris yang perlu disederhanakan
• Solusi minimum akan berisi prime implicant esensial primer dan
sekunder
x3 x4 + x1 x4
• fmin = x2 x4 + x2 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 pewaktuan
Rangkaian Multilevel f (x1 , x2 , x3 , x4 ) = m(0, 2, 5, 6, 7, 8, 10, 12, 13, 14, 15)


Latihan

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



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



Implementasi Rangkaian 2-Level


• Rangkaian 2-level
• Sintesis Multilevel AND-OR dan NAND-NAND dibentuk dari persamaan SOP
• Kompleksitas Wiring OR-AND dan NOR-NOR dibentuk dari persamaan POS


Problem Fan-in


• Saat jumlah masukan bertambah, rangkaian 2-level akan menemui
• Rangkaian 2-Level kendala fan-in
• Kompleksitas Wiring ◦ 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


• Misalnya: f (x1 , ..., x7 ) = x1 x3 x6 + x1 x4 x5 x6 + x2 x3 x7 + x2 x4 x5 x7
• Sintesis Multilevel • Di CPLD, implementasi fungsi ini tidak ada masalah, karena
• Kompleksitas Wiring mempunyai cukup masukan (7 input), gerbang AND (1 per term
perkalian) dan gerbang OR (satu per keluaran AND)


Implementasi fungsi di FPGA


• 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
• Teknik Faktoring diimplementasikan
• Analisis Multilevel ◦ 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


• Untuk mengatasinya, fungsi harus dinyatakan dalam ekspresi
• Rangkaian 2-Level logika multilevel
• Kompleksitas Wiring ◦ Hanya mengandung term dengan 2 literal
• Analisis Multilevel ◦ Implikasinya: rangkaian bisa lebih dari 2 level −→multilevel

• Teknik sintesis multilevel:

◦ Faktoring
◦ Dekomposisi fungsi


Teknik Faktoring


• Memanfaatkan hukum distributif untuk menuliskan ekspresi dengan term
• Rangkaian 2-Level ber-literal lebih sedikit −→implementasi di FPGA dg LUT 2-masukan
• Dekomposisi Fungsional 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


• Diberikan:
f = x1 x2 x3 x4 x5 x6 + x1 x2 x3 x4 x5 x6
= x1 x3 x4 (x2 x5 x6 + x2 x5 x6 )


Contoh Faktoring


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


Contoh Faktoring


• Nyatakan ekspresi berikut agar hanya membutuhkan gerbang AND
• Rangkaian 2-Level dan OR 2-masukan!
• Kompleksitas Wiring • 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


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


• Rangkaian dapat didekomposisi menjadi sub-sub rangkaian
◦ Mengurangi kompleksitas rangkaian di wiring dan gerbang
• Kompleksitas Wiring logika
• Analisis Multilevel ◦ 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 ’ﬁt’ di block logika yang tersedia


Contoh Dekomposisi

Ekspresi minimum: f = x1 x2 x3 + x1 x2 x3 + x1 x2 x4 + x1 x2 x4
• Sintesis Multilevel • 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?

Analisis Rangkaian Multilevel




�ݺ�ߣ

T S K205 Kuliah#5 Metode Quine Mc Kluskey Rangkaian Multi Level

More Related Content

T S K205 Kuliah#5 Metode Quine Mc Kluskey Rangkaian Multi Level