Rangkaian Logika Optimal: Peta Karnaugh dan Strategi Minimisasi

Rangkaian Logika Optimal: Peta Karnaugh dan Strategi Minimisasi 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 / 42

Review Kuliah • Sebelumnya dibahas sintesis rangkaian logika dari deskripsi kebutuhan fungsinya berupa tabel kebenaran, diagram pewaktuan ◦ Implementasi dengan gerbang AND-OR (SOP) dan NAND-NAND ◦ Implementasi dengan gerbang OR-AND (POS) dan NOR-NOR ◦ Penyederhanaan ekspresi logika hasil sintesis (SOP/POS) menggunakan prinsip-prinsip aljabar • Selanjutnya adalah penyederhanaan menggunakan peta Karnaugh beserta strategi minimalisasi SOP/POS. Dikenalkan fungsi dengan don’t care dan juga rangkaian dengan keluaran rangkap

http://didik.blog.undip.ac.id/



Bahasan Peta Karnaugh Recall:Penyederhanaan Peta Karnaugh Grouping K-Map K-Map 3 Variabel Tips Grouping K-Map 4 Variabel K-Map 5 Variabel? Strategi - Terminologi Prime Implicant Minimisasi POS Minimisasi Ekspresi POS Fungsi Tidak Lengkap Fungsi Tidak Lengkap Rangkaian Multi-Keluaran Rangkaian Multi-Keluaran



Peta Karnaugh

• Recall:Penyederhanaan • Peta Karnaugh • Grouping K-Map • K-Map 3 Variabel • Tips Grouping • K-Map 4 Variabel • K-Map 5 Variabel? • Strategi - Terminologi • Prime Implicant Minimisasi POS Fungsi Tidak Lengkap

Peta Karnaugh

Rangkaian Multi-Keluaran



Recall: Menyederhanakan Ekspresi Peta Karnaugh

• Recall:Penyederhanaan • Peta Karnaugh • Grouping K-Map • K-Map 3 Variabel • Tips Grouping • K-Map 4 Variabel • K-Map 5 Variabel? • Strategi - Terminologi • Prime Implicant

•

•

Operasi penyederhanaan adalah mengurangi minterm atau maxterm di ekspresi

◦

SOP: menggunakan hukum 14a (x · y + x · y

◦

POS: menggunakan hukum 14b ((x + y) ·

= x)

x+y

= x)

Beberapa minterm atau maxterm dapat digabungkan menggunakan hukum 14a atau 14b jika berbeda hanya di satu variabel saja

Minimisasi POS

f (x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

Fungsi Tidak Lengkap

m1 dan m5 berbeda di x1 , dan m4 dan m6 berbeda di x2


=

f

= =

f

x , x , x

=

x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 x1 + x1

x2 x3 + x1 (x2 + x2 )x3

x2 x3 + x1 x3

x + x + x

x + x + x

x + x + x

M0 dan M2 berbeda di x2 , dan M4 dan M7 berbeda di x1

f

= =


(x1 + x3 ) + x2 x2 (x1 + x3 )

x2 + x3

x1 x1 +

x2 + x3

x + x + x


Peta Karnaugh Peta Karnaugh


• Peta Karnaugh (K-map) menyediakan cara sistematik dan grafis untuk mencari rangkaian SOP minimum (dan POS)

◦ Mencari minterm yang berbeda di satu variabel ◦ Menggabungkan minterm sesuai hukum 14a untuk SOP dan 14b untuk POS

Minimisasi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran

• K-map juga merupakan alternatif untuk menyatakan suatu fungsi logika selain tabel kebenaran

◦ K-map disusun atas sel-sel. Satu sel, satu minterm



Grouping K-Map Peta Karnaugh


• Minterm-minterm yang berdekatan dapat dikombinasikan karena mereka hanya berbeda di satu variabel saja –> Grouping

• Grouping dilakukan dengan melingkari nilai ’1’ yang berdekatan • Melingkari dua nilai ’1’ bersama, berarti mengeliminasi satu term dan satu variabel dari ekspresi output

◦ Variabel yang dieliminasi adalah yang mempunyai perbedaan nilai di group, vertikal/horizontal


◦ Group merah: x1 dieliminasi, Grup biru: x2 dieliminasi



Contoh Grouping Fungsi 2 Variabel Peta Karnaugh


• Sederhanakan: f =

P

m(0, 3) dan f =

P

m(1, 2)







P

m(0, 3) dan f =

P

m(1, 2)


P

• f = m(0, 3) = x1 x2 + x1 x2 –> fungsi SOP tidak dapat disederhanakan

P

• f = m(1, 2) = x1 x2 + x1 x2 –> fungsi SOP tidak dapat disederhanakan @2011 eko didik widianto (http://didik.blog.undip.ac.id)





P

m(0, 1) dan f =

P

m(1, 3)







P

m(0, 1) dan f =

P

m(1, 3)


• f = • f =

P

P

m(0, 1) = x1 x2 + x1 x2 = x1 , x2 dieliminisi m(1, 3) = x1 x2 + x1 x2 = x2 , x1 dieliminasi






P

m(0, 1, 2) dan f =

P

m(1, 2, 3)







P

m(0, 1, 2) dan f =

P

m(1, 2, 3)


• f = • f =

P

P

m(0, 1, 2) = x1 x2 + x1 x2 + x1 x2 = x1 + x2 m(1, 2, 3) = x1 x2 + x1 x2 + x1 x2 = x1 + x2



K-Map 3 Variabel Peta Karnaugh

• Recall:Penyederhanaan • Peta Karnaugh • Grouping K-Map • K-Map 3 Variabel • Tips Grouping • K-Map 4 Variabel • K-Map 5 Variabel? • Strategi - Terminologi • Prime Implicant Minimisasi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran

• K-map disusun sehingga minterm yang berdekatan hanya mempunyai perbedaan 1 variabel

x1

x2

x3

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1


minterm mj

m0 m1 m2 m3 m4 m5 m6 m7

= x1 x2 x3 = x1 x2 x3 = x1 x2 x3 = x1 x2 x3 = x1 x2 x3 = x1 x2 x3 = x1 x2 x3 = x1 x2 x3


Ketentuan dan Tips Grouping Peta Karnaugh

• Recall:Penyederhanaan • Peta Karnaugh • Grouping K-Map • K-Map 3 Variabel • Tips Grouping • K-Map 4 Variabel • K-Map 5 Variabel? • Strategi - Terminologi • Prime Implicant Minimisasi POS

• Hanya dapat mengkombinasikan nilai 1 yang berdekatan • Hanya dapat menggabungkan 2n minterm (1,2,4,8,16, dst) • Bentuk group sebesar mungkin • Group yang sudah dicover oleh group lain tidak perlu digabungkan lagi

Fungsi Tidak Lengkap Rangkaian Multi-Keluaran



Contoh K-Map 3 Variabel Peta Karnaugh


• Sederhanakan f =

P

m(0, 1, 2, 5)


f


X

= m(0, 1, 2, 5) = x1 x3 + x2 x3





P

m(1, 3, 5, 7), f =

P

m(0, 2, 3, 6, 7)







P

m(1, 3, 5, 7), f =

f

P

m(0, 2, 3, 6, 7)

X

= m(1, 3, 5, 7) = x3


f


X

= m(0, 2, 3, 6, 7) = x2 + x1 x3





P

m(0, 1, 3, 4, 5, 7) dan f =

P

m(0, 1, 3, 4, 5, 6)







P

m(0, 1, 3, 4, 5, 7) dan f =

f

P

m(0, 1, 3, 4, 5, 6)

X

= m(0, 1, 3, 4, 5, 7) = x2 + x3


f


X

= m(0, 1, 3, 4, 5, 6) = x2 + x1 x3 + x1 x3


K-Map 4 Variabel Peta Karnaugh


Bentuk K-map 4 variabel:




Contoh Grouping K-Map 4 Variabel Peta Karnaugh



P

m(2, 3, 8 − 11, 13)




Contoh Grouping K-Map 4 Variabel Peta Karnaugh



P

m(2, 3, 8 − 11, 13)


f


X

= m(2, 3, 8, 9, 10, 11, 13) = x1 x2 + x2 x3 + x1 x3 x4


Latihan Grouping K-Map 4 Variabel Peta Karnaugh


Sederhanakan fungsi 4 variabel:

• f = • f = • f =

P

P

P

m(3 − 7, 9, 11, 12 − 15) m(0 − 4, 6, 9, 11, 12, 14) m(0, 2, 5, 7, 8, 10, 13, 15)




K-Map 5 Variabel? Peta Karnaugh


• K-Map 6 Variabel? Tidak berguna dari sudut pandang praktis –> butuh perangkat CAD



Strategi Minimalisasi: Terminologi Peta Karnaugh


• Literal : variabel di suatu term ◦ Contoh: x1 x2 x3 x4 (term dg 4 literal), x2 x3 (term dg 2 literal) • Implicant: sebarang term bernilai ’1’ atau grup term bernilai ’1’ yang dapat digabungkan di K-map


◦ minterm adalah implicant dasar. Untuk fungsi n-variabel, minterm adalah implicant dengan n literal

• Prime Implicant: implicant yang tidak bisa digabungkan dengan implicant lain untuk menghilangkan sebuah variabel ◦ Literal dalam prime implicant tidak dapat dihapus untuk mendapatkan implicant valid

• Cover : suatu koleksi implicant yang menghasilkan nilai fungsi ’1’ • Cost: jumlah gerbang ditambah jumlah total masukan ke semua gerbang dalam rangkaian logika @2011 eko didik widianto (http://didik.blog.undip.ac.id)


Contoh Terminologi Peta Karnaugh


• Terdapat 10 implicant valid ◦ 7 buah minterm ◦ 1 term 3-literal (grup 2 minterm) ◦ 2 term 2-literal (grup 4 minterm)

Minimisasi POS Fungsi Tidak Lengkap

• Terdapat 3 prime implicant


◦ x1 x2 , x2 x3 , x1 x3 x4 ◦ Untuk x1 x2 , jika sebuah literal dihapus menyisakan x1 atau x2 •


x1 bukan implicant valid karena {1,1,0,0} menghasilkan f = 0


Contoh Terminologi: Cover dan Cost Peta Karnaugh


• Cover untuk f =

P

m(2, 3, 8, 9, 10, 11, 13)

1. Persamaan dengan semua minterm 2. f = x1 x2 + x1 x2 x3 + x1 x3 x4 merupakan cover valid 3. f = x1 x2 + x2 x3 + x1 x3 x4 merupakan cover valid yang berisi prime implicant


• Cost untuk setiap cover: (asumsi input utama baik terinvers atau tidak mempunyai cost 0)

1. jumlah gerbang=7+1, jumlah input semua gerbang=7*4+7*1, total=8+28+7=43

2. jumlah gerbang=3+1, jumlah input semua gerbang=8+3, total=4+11=15

3. jumlah gerbang=3+1, jumlah input semua gerbang=7+3, total=4+10=14

• Cover yang berisi prime implicant cenderung menghasilkan implementasi dengan cost terendah @2011 eko didik widianto (http://didik.blog.undip.ac.id)


Prime Implicant: Esensial dan Non-Esensial Peta Karnaugh


SOP minimum hanya mengandung prime implicant (namun tidak semua prime implicant)

• Essential: diperlukan untuk membentuk SOP minimum • Nonessensial: tidak diperlukan untuk SOP minimum (dapat dihilangkan)


• Prime implicant: x1 x2 , x2 x3 , x1 x3 x4 dan x2 x3 x4 • Esensial: x1 x2 , x2 x3 , dan x2 x3 x4 • non-esensial: x1 x3 x4 • fmin = x1 x2 + x2 x3 + x2 x3 x4 , x1 x3 x4 dihilangkan



Contoh Prime Implicant Peta Karnaugh


• Prime implicant: x1 x2 , x2 x3 , x1 x2 x3 , x1 x2 x4 dan x1 x3 x4 • Esensial: x1 x2 , x2 x3 , dan x1 x2 x3 • non-esensial: x1 x2 x4 , x1 x3 x4 (harus dipilih salah satu)

• fmin =


x1 x2 + x2 x3 + x1 x2 x3 +


x1 x2 x4 x1 x3 x4


Ringkasan Peta Karnaugh


• SOP minimum berisi semua prime implicant esensial dan beberapa prime implicant non-esensial

• Langkah menemukan rangkaian dengan cost minimum: 1. Cari semua prime implicant dari f 2. Cari set prime implicant esensial 3. Jika set tersebut telah meng-cover semua valuation dimana f = 1, maka set ini adalah cover dari f yang diinginkan. Jika tidak, tentukan prime implicant non-esensial yang harus ditambahkan agar minimum

• Menentukan prime implicant non-esensial? heuristik (mencoba semua kemungkinan untuk mendapatkan cover dengan cost minimum)



Latihan di Rumah Peta Karnaugh


• Cari semua prime implicant dari f • Cari set prime implicant esensial • Cari cover dengan cost terendah dari semua kombinasi prime implicant non-esensial




Peta Karnaugh Minimisasi POS

• Minimisasi Ekspresi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran

Minimisasi POS



Minimisasi Ekspresi POS Peta Karnaugh Minimisasi POS


• Menggunakan prinsip dualitas • K-map dapat langsung dibentuk baik dari ekspresi

Q

M

P

m maupun

• Shortcut: ◦ Maxterm mempunyai valuasi fungsi ’0’ ◦ Grouping Maxterm sebesar mungkin ◦ Bentuk persamaan POS dari set Maxterm minimum •

Prinsip prime implicant esensial berlaku? bisa, dengan pengertian implicant adalah Maxterm atau group Maxterm



POS Minimal dari Peta Karnaugh Minimisasi POS

P

m atau

Q

M P

Diberikan: f =


f

= =

X


m(0, 1, 2, 5)

(x1 + x3 ) (x2 + x3 ) ; P OS

=

x1 x3 + x2 x3 ; SOP

=

Y

M (3, 4, 6, 7)

Q

Diberikan: f =

f

m(0, 1, 2, 5)

M (1, 4, 5)

=

Y

=

x2 + x1 x3 ; SOP

=

X

=

M (1, 4, 5)

(x1 + x2 ) (x2 + x3 ) ; P OS m(0, 2, 3, 6, 7)


POS 4-Variabel Minimal Peta Karnaugh Minimisasi POS


f

= =

X Y

m(2, 3, 8, 9, 10, 11, 13)

M (0, 1, 4, 5, 6, 7, 12, 14, 15)

• Prime implicant: x1 + x3 , x2 + x3 , x2 + x4 dan x1 + x2 • Esensial: x1 + x3 , x2 + x3 , dan x2 + x4 • non-esensial: x1 + x2 (biru) • fmin = (x1 + x3 ) (x2 + x3 ) (x2 + x4 )



Latihan di Rumah Peta Karnaugh Minimisasi POS

• Minimisasi Ekspresi POS

• Persamaan POS


• Cari semua prime implicant dari f • Cari set prime implicant esensial • Cari cover dengan cost terendah dari semua kombinasi prime implicant non-esensial



Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap

• Fungsi Tidak Lengkap Rangkaian Multi-Keluaran




Fungsi Tidak Lengkap Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap


• Dalam sistem digital, sering terjadi beberapa kondisi input yang tidak akan pernah terjadi • Kombinasi input seperti itu disebut kondisi don’t care • Dalam desain rangkaian, kondisi don’t care dapat diabaikan (keluaran untuk kondisi tersebut dapat diberikan 0 atau 1 di tabel kebenaran) • Fungsi yang mengandung kondisi don’t care disebut fungsi yang dispesifikasikan tidak lengkap (incompletely specified)



Contoh Don’t Care Peta Karnaugh Minimisasi POS

x1

x2

x3

f

0

0

0

1

0

0

1

1

0

1

0

d

0

1

1

d

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0




• Asumsi fungsi 3 variabel. Kombinasi masukan x1 x2 = 01 tidak pernah terjadi, P selebihnya f = m(1, 4, 5, 6)

P f = Q m(1, 4, 5, 6) + D(2, 3); atau f = M (0, 7) · D(2, 3)


Contoh Don’t Care 4 variabel Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap


P • SOP: f = m(2, 4, 5, 6, 10) + D(12, 13, 14, 15) Q

• POS: f =

M (0, 1, 3, 7, 8, 9, 11) · D(12, 13, 14, 15)

• SOP: fmin = x2 x3 + x3 x4 , POS: fmin = (x2 + x3 ) (x3 + x4 ) • Jika don’t care tidak disertakan: misalnya menganggap nilainya selalu 0 ◦ SOP: f = x1 x2 x3 + x1 x3 x4 + x2 x3 x4 ◦ POS: f = (x2 + x3 ) (x3 + x4 ) (x1 + x2 ) ◦ Cost mungkin lebih tinggi @2011 eko didik widianto (http://didik.blog.undip.ac.id)


Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran

• Rangkaian Multi-Keluaran




Rangkaian dengan Banyak Keluaran Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran


• Sebelumnya dibahas fungsi dengan keluaran tunggal berikut dengan implementasi rangkaiannya • Dalam prakteknya, beberapa fungsi tunggal tersebut merupakan bagian dari rangkaian logika yang lebih besar • Rangkaian-rangkaian dari fungsi tersebut mungkin dapat dikombinasikan ke dalam rangkaian tunggal dengan cost lebih murah dengan keluaran multiple ◦ Pemakaian bersama blok gerbang oleh beberapa rangkaian fungsi tunggal



Contoh Rangkaian Multi-Keluaran Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap Rangkaian Multi-Keluaran


• f1 = x1 x3 + x1 x3 + x2 x3 x4 , Cost=4 gerbang + 10 input(=14) • f2 = x1 x3 + x1 x3 + x2 x3 x4 , Cost=4 gerbang + 10 input (=14) • Cost total jika kedua fungsi diimplementasikan terpisah: 8 gerbang + 20 input (=28)



Contoh Rangkaian Multi-Keluaran Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap

• Mengkombinasikan (prime) implicant yang sama dari dua/lebih fungsi mungkin bisa mengurangi cost



• Rangkaian multi-keluaran:

f1 f2

= x1 x3 + x1 x3 +

x2 x3 x4 x2 x3 x4

• Cost=6 gerbang + 16 input (=22)




• Di contoh sebelumnya, terdapat prime implicant yang shared. Kalau tidak ada yang shared?



• f1 = x1 x4 + x2 x4 + x1 x2 x3 , Cost=4 gerbang + 10 input(=14) • f2 = x1 x4 + x2 x4 + x1 x2 x3 x4 , Cost=4 gerbang + 11 input (=15) • Tidak ada gerbang prime implicant yang dapat dishared, sehingga cost total dari kombinasi 2 rangkaian adalah 8 gerbang + 21 input (=29) @2011 eko didik widianto (http://didik.blog.undip.ac.id)



• Tapi ada alternatif realisasi lainnya: menggunakan implicant bersama antara 2 fungsi



• f 1 = x1 x2 x4 + x1 x2 x3 x4 + x1 x4 • f 2 = x1 x2 x4 + x1 x2 x3 x4 + x2 x4 • Rangkaian multikeluaran: f1 x1 x4 = x x x + x x x x + 1 2 4 1 2 3 4 @2011 eko didik widianto (http://didik.blog.undip.ac.id) TSK205 Digital - Siskom Undip – 41 / 42 f2 x2 xSistem 4

Latihan di Rumah Peta Karnaugh Minimisasi POS

• Cari cost terendah untuk POS dari soal sebelumnya!





Rangkaian Logika Optimal: Peta Karnaugh dan Strategi Minimisasi

Recommend Documents