t s k205 kuliah#5 metode quine mc kluskey rangkaian multi level

@2011 eko didik widianto (http://didik.blog.undip.ac.id) TSK205 Sistem Digital - Siskom Undip – 1 / 27

Metode Minimisasi Quine McKluskey dan Rangkaian Multilevel

Eko Didik Widianto ([email protected])

Sistem Komputer - Universitas Diponegoro

Review Kuliah


• Sebelumnya

◦ minimisasi rangkaian logika menggunakan peta Karnaugh baik untukbentuk 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-McKluskeyMetode Quine-McKluskey

Rangkaian MultilevelRangkaian 2-LevelSintesis MultilevelTeknik FaktoringKompleksitas WiringDekomposisi FungsionalAnalisis Multilevel

Metode Quine-McKluskey


• Metode Quine-McKluskey

Rangkaian Multilevel


Metode Tabular 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 dalamfungsi akhirnya

(b) Row dominance

(c) Column dominance

4. Selesaikan tabel

Tujuannya mencari prime implicantesensial (primer, sekunder, dst)

(Willard Quine, Wikipedia)

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: x2x4 dan x2x4

◦ 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 6atau 12 akan mengcover 14

Langkah 3c: Pilih Kolom

• prime implicant x3x4 dan x2x3 saling mendominasi, bisa dipilihsalah satu

• x1x4 dan x1x2 saling mendominasi, bisa dipilih salah satu

Contoh Problem: Iterasi #2





Langkah 3a: Hapus Prime Implicant Essensial SekunderTerdapat 2 solusi

• Prime implicant esensial sekunder: x3x4 dan x1x4 atau x2x3

dan x1x2

◦ 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 dansekunder

• fmin = x2x4 + x2x4 +

{

x3x4 + x1x4

x2x3 + x1x2

}

Contoh Problem: Simulation/Analisis





• Skematik rangkaian fmin = x2x4 + x2x4 + x3x4 + x1x4

• Simulasi dengan Qucs (Quite Universal Circuit Simulator)

Contoh Problem: Diagram Pewaktuan





• Diagram pewaktuanf(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

AND-OR dan NAND-NAND dibentuk dari persamaan SOP

OR-AND dan NOR-NOR dibentuk dari persamaan POS

Problem Fan-in










• Saat jumlah masukan bertambah, rangkaian 2-level akan menemuikendala fan-in

◦ Fan-in: jumlah input ke suatu gerbang atau komponen rangkaiantertentu

◦ Tergantung teknologi yang digunakan untuk mengimplementasikanrangkaian

◦ Di CPLD, fungsi SOP 2-level dengan tiap term lebih dari 2 literaldapat langsung diimplementasikan

◦ Di FPGA dengan LUT 2-masukan, fungsi tersebut tidak dapatlangsung diimplementasikan -> dikonversi menjadi fungsi denganterm 2-literal

• Kendala fan-in lainnya adalah delay propagasi

◦ propagasi delay: waktu yang dibutuhkan untuk mempropagasikannilai masukan sampai ke keluaran gerbang

◦ Jumlah masukan semakin banyak, delay propagasi akan bertambah

Implementasi fungsi di CPLD










• Misalnya: f(x1, ..., x7) = x1x3x6 + x1x4x5x6 + x2x3x7 + x2x4x5x7

• Di CPLD, implementasi fungsi ini tidak ada masalah, karenamempunyai cukup masukan (7 input), gerbang AND (1 per termperkalian) dan gerbang OR (satu per keluaran AND)

Implementasi fungsi di FPGA










• Misalnya: f(x1, ..., x7) = x1x3x6 + x1x4x5x6 + x2x3x7 + x2x4x5x7

• Di FPGA dengan LUT 2-masukan, fungsi tidak dapat langsungdiimplementasikan

◦ Fungsi f mempunyai term dengan 3 dan 4 literal, memerlukangerbang AND 3-masukan dan 4-masukan

◦ Terdapat 4 term perkalian yang harus di-OR-kan, memerlukangerbang OR 4-masukan

• Fan-in yang diperlukan untuk

mengimplementasikan fungsi ini

terlalu banyak untuk FPGA

Sintesis Multilevel










• Untuk mengatasinya, fungsi harus dinyatakan dalam ekspresilogika multilevel

◦ Hanya mengandung term dengan 2 literal

◦ Implikasinya: rangkaian bisa lebih dari 2 level −→multilevel

• Teknik sintesis multilevel:

◦ Faktoring

◦ Dekomposisi fungsi

Teknik Faktoring










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

f(x1, ..., x7) = x1x3x6 + x1x4x5x6 + x2x3x7 + x2x4x5x7

= x1x6 (x3 + x4x5) + x2x7 (x3 + x4x5)

= (x1x6 + x2x7) (x3 + x4x5)

Contoh Faktoring










• Diberikan:

f = x1x2x3x4x5x6 + x1x2x3x4x5x6

= x1x3x4 (x2x5x6 + x2x5x6)

Contoh Faktoring










• Nyatakan ekspresi berikut agar hanya membutuhkan gerbang ANDdan OR 2-masukan!

• f(x1, ..., x7) = x1x2x4x5 + x1x2x6x7 + x3x4x5 + x3x6x7

Contoh Faktoring










• Nyatakan ekspresi berikut agar hanya membutuhkan gerbang ANDdan OR 2-masukan!

• f(x1, ..., x7) = x1x2x4x5 + x1x2x6x7 + x3x4x5 + x3x6x7

f(x1, ..., x7) = x1x2x4x5 + x1x2x6x7 + x3x4x5 + x3x6x7

= x1x2 (x4x5 + x6x7) + x3 (x4x5 + x6x7)

= (x1x2 + x3) (x4x5 + x6x7)

Kompleksitas Wiring










• 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 yangmembawa sinyal logik yang diinginkan

• Faktoring mengurangi jumlah literal, sehingga dapat digunakan untukmengurangi 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 gerbanglogika

◦ Satu atau beberapa sub-rangkaian mengimplementasikanfungsi yang digunakan di beberapa bagian untuk membentukrangkaian lengkapnya

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

◦ Ekspresi-ekspresi tersebut dikombinasikan untuk membentukrangkaian multilevel

• CAD banyak memanfaatkan konsep dekomposisi fungsi

◦ Mengimplementasikan fungsi general dengan konstrain

• Fungsi harus ’fit’ di block logika yang tersedia

Contoh Dekomposisi










Ekspresi minimum: f = x1x2x3 + x1x2x3 + x1x2x4 + x1x2x4

• Rangkaian diimplementasikan dengan 4 gerbang AND, 1 gerbangOR, dan 2 gerbang NOT dan 18 masukan ke semua gerbang

• Fan-in=3 untuk gerbang AND dan 4 untuk gerbang OR

• Faktoring: f = (x1x2 + x1x2)x3 + (x1x2 + x1x2) x4

• Misalkan g(x1, x2) = (x1x2 + x1x2)

• Perhatikan:

g = (x1x2 + x1x2) =(

x1x2

) (

x1x2

)

= (x1 + x2) (x1 + x2)

= x1x1 + x1x2 + x2x1 + x2x2

= x1x2 + x1x2

• 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

Documents