Review Kuliah. Peta Karnaugh. Recall:Penyederhanaan. Peta Karnaugh

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

Rangkaian Logika Optimal: Peta Karnaugh dan Strategi Minimisasi

◦ Implementasi dengan gerbang OR-AND (POS) dan NOR-NOR Eko Didik Widianto ([email protected])

◦ Penyederhanaan ekspresi logika hasil sintesis (SOP/POS) menggunakan prinsip-prinsip aljabar

Sistem Komputer - Universitas Diponegoro

• 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/

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

TSK205 Sistem Digital - Siskom Undip – 1 / 42



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

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

Minimisasi POS Minimisasi Ekspresi POS Fungsi Tidak Lengkap Fungsi Tidak Lengkap Rangkaian Multi-Keluaran 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

•

•

Peta Karnaugh Peta Karnaugh

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

Minimisasi POS

Fungsi Tidak Lengkap

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




=

f

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

!

=

x1 + x1

!

x , x , x

! =

x + x + x

= =

!

x + x + x

!

(x1 + x3 ) + x2 x2

(x1 + x3 )

!

!

x2 + x3


• 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

◦ Menggabungkan minterm sesuai hukum 14a untuk SOP dan 14b untuk POS

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

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

!

x + x + x

x1 x1 +

!

x2 + x3

!

x + x + x



Grouping K-Map Peta Karnaugh

◦ Mencari minterm yang berbeda di satu variabel

x2 x3 + x1 (x2 + x2 )x3

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

f

mencari rangkaian SOP minimum (dan POS)

x2 x3 + x1 x3

=

f

• Peta Karnaugh (K-map) menyediakan cara sistematik dan grafis untuk


Contoh Grouping Fungsi 2 Variabel

• 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

Peta Karnaugh


• Sederhanakan: f =

P

m(0, 3) dan f =

P

m(1, 2)

Minimisasi POS Fungsi Tidak Lengkap

group, vertikal/horizontal



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





Contoh Grouping Fungsi 2 Variabel Peta Karnaugh



P


m(0, 3) dan f =

P

m(1, 2)

Peta Karnaugh


Minimisasi POS

Minimisasi POS






P

m(0, 1) dan f =

P

m(1, 3)

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)

Peta Karnaugh


Minimisasi POS

Minimisasi POS





• f = • f =

P P



P

m(0, 1, 2) dan f =

P

m(1, 2, 3)

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 =

K-Map 3 Variabel P

m(1, 2, 3)

Peta Karnaugh


Minimisasi POS

Minimisasi POS





• 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



• 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

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

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


Contoh K-Map 3 Variabel

• Hanya dapat mengkombinasikan nilai 1 yang berdekatan n

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

Peta Karnaugh


• Sederhanakan f =




f


m(0, 1, 2, 5)

Minimisasi POS



P


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


Contoh K-Map 3 Variabel Peta Karnaugh



P


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

P

Peta Karnaugh

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


Minimisasi POS

Minimisasi POS






P

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

f

f




Contoh K-Map 3 Variabel Peta Karnaugh



P

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

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

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



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

P

Peta Karnaugh

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


Minimisasi POS

Minimisasi POS






P




P

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

P

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

f

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


Contoh Grouping K-Map 4 Variabel

Bentuk K-map 4 variabel:

Peta Karnaugh


Minimisasi POS

Minimisasi POS









P

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

Peta Karnaugh







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


Latihan Grouping K-Map 4 Variabel

Minimisasi POS

f

P


Contoh Grouping K-Map 4 Variabel Peta Karnaugh


Sederhanakan fungsi 4 variabel:

• f = • f = • f =

P

m(3 − 7, 9, 11, 12 − 15)

P

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

P

m(0 − 4, 6, 9, 11, 12, 14)

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




K-Map 5 Variabel?

Strategi Minimalisasi: Terminologi

Peta Karnaugh

Peta Karnaugh



Minimisasi POS

Minimisasi POS





• 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

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

• Cover : suatu koleksi implicant yang menghasilkan nilai fungsi ’1’ • Cost: jumlah gerbang ditambah jumlah total masukan ke semua gerbang dalam rangkaian logika




Contoh Terminologi

Contoh Terminologi: Cover dan Cost

Peta Karnaugh

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


• 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

Minimisasi POS

• Terdapat 3 prime implicant


Fungsi Tidak Lengkap Rangkaian Multi-Keluaran

◦ x1 x2 , x2 x3 , x 1 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

• 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+8*1, total=8+28+8=44

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)

Contoh Prime Implicant Peta Karnaugh


Minimisasi POS

Minimisasi POS



• Prime implicant: x1 x2 , x2 x3 , x1 x3 x4 dan x2 x3 x4


• 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 x 3 +

x1 x2 x4 x1 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




Ringkasan 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


Latihan di Rumah

• 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

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


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





Minimisasi Ekspresi POS Peta Karnaugh

Peta Karnaugh

Minimisasi POS

Minimisasi POS

• Minimisasi Ekspresi POS






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

Q

M

P

m maupun

• Shortcut: ◦ Maxterm mempunyai valuasi fungsi ’0’

Minimisasi POS

◦ Grouping Maxterm sebesar mungkin ◦ Bentuk persamaan POS dari set Maxterm minimum •


POS Minimal dari Peta Karnaugh Minimisasi POS


P

m atau

Q


POS 4-Variabel Minimal P

Diberikan: f =


f

=

X

f

m(0, 1, 2, 5)

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

=

x1 x3 + x2 x3 ; SOP

=

Y

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

M (3, 4, 6, 7)

• Esensial: x1 + x3 , x2 + x3 , dan x2 + x4

Q

M (1, 4, 5)

=

Y

=

x2 + x1 x3 ; SOP

=

X

=

Peta Karnaugh


m(0, 1, 2, 5)

=

Diberikan: f =



M



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

• non-esensial: x1 + x2 (biru) • fmin = (x1 + x3 ) (x2 + x3 ) (x2 + x4 )

M (1, 4, 5)

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




Latihan di Rumah Peta Karnaugh

Peta Karnaugh

Minimisasi POS

Minimisasi POS


• Persamaan POS



• Fungsi Tidak Lengkap

• Cari semua prime implicant dari f



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





Fungsi Tidak Lengkap Peta Karnaugh Minimisasi POS Fungsi Tidak Lengkap

• Fungsi Tidak Lengkap Rangkaian Multi-Keluaran


Contoh Don’t Care

• Dalam sistem digital, sering terjadi beberapa kondisi input yang tidak akan pernah terjadi

Peta Karnaugh Minimisasi POS

x1

x2

x3

f

0

0

0

1

0

0

1

1

• Dalam desain rangkaian, kondisi don’t care dapat diabaikan (keluaran untuk kondisi tersebut dapat diberikan 0 atau 1 di tabel kebenaran)

0

1

0

d

0

1

1

d

1

0

0

1

• Fungsi yang mengandung kondisi don’t care disebut fungsi yang dispesifikasikan tidak lengkap (incompletely specified)

1

0

1

1

1

1

0

0

1

1

1

0

• Kombinasi input seperti itu disebut kondisi don’t care




• Fungsi Tidak Lengkap Rangkaian Multi-Keluaran


• 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

Peta Karnaugh

Minimisasi POS

Minimisasi POS



• Fungsi Tidak Lengkap



• Rangkaian Multi-Keluaran

Rangkaian Multi-Keluaran • SOP: f = • POS: f =

P m(2, 4, 5, 6, 10) + D(12, 13, 14, 15) Q

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)



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


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


• 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 • f1 = x1 x3 + x1 x3 + x2 x3 x4 , Cost=4 gerbang + 10 input(=14) • f1 = 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

Peta Karnaugh

• Mengkombinasikan (prime) implicant yang sama dari dua/lebih fungsi

Minimisasi POS

mungkin bisa mengurangi cost



Contoh Rangkaian Multi-Keluaran

• Rangkaian multi-keluaran:

f1 f2


= x1 x 3 + x 1 x 3 +

x2 x3 x4 x 2 x 3 x4

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



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

• f1 = x1 x4 + x2 x4 + x1 x2 x3 , Cost=4 gerbang + 10 input(=14) • f1 = 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)



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


Latihan di Rumah

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

Peta Karnaugh Minimisasi POS

• Cari cost terendah untuk POS dari soal sebelumnya!






• f 1 = x1 x 2 x 4 + x 1 x 2 x 3 x 4 + x 1 x 4 • f 1 = x1 x 2 x 4 + x 1 x 2 x 3 x 4 + x 2 x 4 • Cost gabungan total= 6 gerbang + 17 input (=23) @2011 eko didik widianto (http://didik.blog.undip.ac.id)




Review Kuliah. Peta Karnaugh. Recall:Penyederhanaan. Peta Karnaugh

Recommend Documents