Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1) @2017,Eko Didik Widianto Peta Karnaugh Ringkasan
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Lisensi
Kuliah#4 TKC205 Sistem Digital
Eko Didik Widianto Departemen Teknik Sistem Komputer, Universitas Diponegoro
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
1
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Umpan Balik
@2017,Eko Didik Widianto
I
Sebelumnya dibahas tentang implementasi fungsi logika menjadi suatu rangkaian logika (disebut proses sintesis), baik menggunakan tabel kebenaran, maupun aljabar Boolean I I I I I
I I I
I
Peta Karnaugh Ringkasan Lisensi
Aljabar Boolean: aksioma, teorema, dan hukum Diagram Venn Manipulasi aljabar Sintesis ekspresi logika dari tabel kebenaran Bentuk kanonik: minterm/SOP dan maxterm/POS beserta notasinya Konversi SOP <-> POS Rangkaian AND-OR, OR-AND Rangkaian NAND-NAND, NOR-NOR
Rangkaian optimal dapat diperoleh dengan penyederhanaan ekspresi logika secara Aljabar
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
2
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Tentang Kuliah
@2017,Eko Didik Widianto
I
Dibahas proses sintesis rangkaian logika minimal menggunakan peta Karnaugh untuk menyederhanakan persamaan fungsi logika I
I
Peta Karnaugh Ringkasan Lisensi
Peta Karnaugh juga digunakan untuk merancang rangkaian multikeluaran minimal
Pokok Bahasan: I
I
I
I
I
peta Karnaugh: 2 variabel, 3-variabel, 4-variabel, 5-variabel dan 6-variabel strategi minimisasi rangkaian SOP (pengelompokan minterm) kondisi don’t care dan rangkaian dengan spesifikasi tidak lengkap literal, implicant, cover, cost, implicant utama dan fungsi minimum implementasi rangkaian logika SOP optimal dengan AND-OR dan/atau NAND-NAND
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
3
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Kompetensi Dasar
@2017,Eko Didik Widianto Peta Karnaugh
I
Ringkasan
Setelah mempelajari bab ini, mahasiswa akan mampu:
Lisensi
1. [C2] memahami prinsip-prinsip penyederhanaan fungsi logika menggunakan peta Karnaugh; 2. [C3] menggunakan Don’t care dalam peta Karnaugh; 3. [C4] mendesain dan menganalisis rangkaian logika SOP minimal (AND-OR atau NAND-NAND) menggunakan peta Karnaugh; I
Link I
I
Website: http://didik.blog.undip.ac.id/2017/03/06/ tkc205-sistem-digital-2016-genap/ Email:
[email protected]
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
4
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Buku Acuan/Referensi
@2017,Eko Didik Widianto
Eko Didik Widianto, Sistem Digital: Analisis, Desain dan Implementasi, Edisi Pertama, Graha Ilmu, 2014 (Bab 4: Peta Karnaugh dan Rangkaian Multikeluaran) I
Peta Karnaugh Ringkasan Lisensi
Materi: 4.1 Peta Karnaugh I I I
I I
4.1.1 Representasi Peta Karnaugh 4.1.2 Pengelompokan Minterm 4.1.3-5 K-map Tiga Variabel, Empat Variabel, dan Banyak Variabel 4.1.6 Literal, Implicant, Cover dan Cost 4.1.7 Implicant Utama dan Fungsi Minimum Rangkaian
I Website: I
http://didik.blog.undip.ac.id/ buku/sistem-digital/
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
5
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Bahasan
@2017,Eko Didik Widianto Peta Karnaugh Ringkasan
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Lisensi
Ringkasan
Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
6
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Rangkaian Optimal
@2017,Eko Didik Widianto Peta Karnaugh
I
Rangkaian optimal I
I I
Karnaugh Map Grouping K-Map
Cost rangkaian sekecil mungkin: jumlah gerbang (dan transistor), jumlah jalur Fungsional terpenuhi Constraint terpenuhi: delay, fanout (driving), area
I
Rangkaian optimal biasanya minimal
I
Rangkaian optimal bisa diperoleh dengan teknik:
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
1. Penyederhanaan fungsi logika I I
Menggunakan prinsip-prinsip Aljabar Boolean Menggunakan Karnaugh Map
2. Penggunaan gerbang secara bersama untuk beberapa fungsi sekaligus, membentuk rangkaian multi-keluaran
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
7
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Bahasan
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Ringkasan
Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
8
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Prinsip Penyederhanaan
@2017,Eko Didik Widianto
I Operasi penyederhanaan adalah mengurangi minterm atau maxterm di
ekspresi I I
Peta Karnaugh Karnaugh Map
SOP: menggunakan hukum 14a (x · y + x · y = x) POS: menggunakan hukum 14b ((x + y ) · (x + y ) = x)
Grouping K-Map Literal, Implicant, Cover dan Cost
I Beberapa minterm atau maxterm dapat digabungkan menggunakan
Ringkasan
hukum 14a atau 14b jika berbeda hanya di satu variabel saja f (x1 , x2 , x3 ) = x 1 x 2 x3 + x1 x 2 x 3 + x1 x 2 x3 + x1 x2 x 3 m1 dan m5 berbeda di x1 , dan m4 dan m6 berbeda di x2 f
= =
x 1 x 2 x3 + x1 x 2 x3 + x1 x 2 x 3 + x1 x2 x 3 (x 1 + x1 ) x 2 x3 + x1 (x 2 + x2 )x 3
=
x 2 x3 + x1 x 3
Lisensi
f (x , x , x ) = (x + x + x ) (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 x 2 ) (x1 x 1 + (x 2 + x 3 ))
=
(x1 + x3 ) (x 2 + x 3 )
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
9
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Peta Karnaugh
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map
I
I
Peta Karnaugh (K-map) menyediakan cara sistematik dan grafis untuk mencari rangkaian SOP dan POS minimal
Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan
K-map SOP
Lisensi I
I
I
mengelompokkan minterm-minterm bernilai 1 yang saling berdekatan, yang hanya mempunyai perbedaan di satu variabel saja membentuk rangkaian AND-OR
K-map POS I
I
mengelompokkan Maxterm-Maxterm bernilai 0 yang saling berdekatan membentuk rangkaian OR-AND minimal
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
10
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Representasi Peta Karnaugh
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
I
Literal, Implicant, Cover dan Cost
K-map juga merupakan alternatif untuk menyatakan suatu fungsi logika selain tabel kebenaran dan ekspresi logika I
Ringkasan Lisensi
K-map disusun atas sel-sel. Satu sel, satu minterm
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
11
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Bahasan
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Ringkasan
Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
12
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Grouping K-Map I
I I
@2017,Eko Didik Widianto
Minterm-minterm yang berdekatan dapat dikombinasikan karena mereka hanya berbeda di satu variabel saja, disebut Grouping Grouping dilakukan dengan melingkari nilai ’1’ yang berdekatan Melingkari dua nilai ’1’ bersama, berarti mengeliminasi satu term dan satu variabel dari ekspresi output I
I
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Variabel yang dieliminasi adalah yang mempunyai perbedaan nilai di grup, vertikal/horizontal Group merah: x1 dieliminasi, Grup biru: x2 dieliminasi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
13
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Ketentuan dan Tips Grouping
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
I
Hanya dapat mengkombinasikan nilai 1 yang berdekatan
I
Hanya dapat menggabungkan 2n minterm (1,2,4,8,16, dst)
I
Bentuk grup sebesar mungkin I I I
I
grup 2 minterm menghilangkan 1 variabel grup 4 minterm menghilangkan 2 variabel grup 8 minterm menghilangkan 3 variabel
Group yang sudah dicover oleh group lain tidak perlu digabungkan lagi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
14
Ringkasan Lisensi
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh Grouping Fungsi 2 Variabel Sederhanakan: f (x1 , x2 ) =
P
m(0, 3) dan f (x1 , x2 ) =
P
@2017,Eko Didik Widianto
m(1, 2)
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
I f (x1 , x2 ) =
P
m(0, 3) = x 1 x 2 + x1 x2
fungsi SOP tidak dapat disederhanakan P I f (x1 , x2 ) = m(1, 2) = x1 x 2 + x 1 x2 I
I
fungsi SOP tidak dapat disederhanakan
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
15
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh Grouping Fungsi 2 Variabel
@2017,Eko Didik Widianto Peta Karnaugh
I Sederhanakan: f (x1 , x2 ) =
P
m(0, 1) dan f (x1 , x2 ) =
P
Karnaugh Map
m(1, 3)
Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
I f (x1 , x2 ) =
P
m(0, 1) = x 1 x 2 + x 1 x2 = x 1 , x2 dieliminisi
I f (x1 , x2 ) =
P
m(1, 3) = x 1 x2 + x1 x2 = x2 , x1 dieliminasi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
16
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh Grouping Fungsi 2 Variabel
@2017,Eko Didik Widianto Peta Karnaugh
I Sederhanakan: f (x1 , x2 ) =
P
m(0, 1, 2) dan f (x1 , x2 ) =
P
Karnaugh Map
m(1, 2, 3)
Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
I f (x1 , x2 ) =
P
m(0, 1, 2) = x 1 x 2 + x 1 x2 + x1 x 2 = x 1 + x 2
I f (x1 , x2 ) =
P
m(1, 2, 3) = x 1 x2 + x1 x 2 + x1 x2 = x1 + x2
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
17
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
K-Map 3 Variabel
@2017,Eko Didik Widianto
I
K-map disusun sehingga minterm yang berdekatan hanya mempunyai perbedaan 1 variabel
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
x1 0 0 0 0 1 1 1 1
x2 0 0 1 1 0 0 1 1
x3 0 1 0 1 0 1 0 1
minterm mj m0 = x 1 x 2 x 3 m1 = x 1 x 2 x3 m2 = x 1 x 2 x 3 m3 = x 1 x2 x3 m4 = x1 x 2 x 3 m5 = x1 x 2 x3 m6 = x1 x2 x 3 m7 = x1 x2 x3
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
18
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh K-Map 3 Variabel
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map
I
Sederhanakan f (x1 , x2 , x3 ) =
P
Grouping K-Map
m(0, 1, 2, 5)
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
19
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh K-Map 3 Variabel
@2017,Eko Didik Widianto Peta Karnaugh
I
Sederhanakan f (x1 , x2 , x3 ) =
P
m(0, 2, 4, 7)
Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
I
menghasilkan f (x1 , x2 , x3 ) = x 1 x 3 + x 2 x 3 + x1 x2 x3
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
20
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh K-Map 3 Variabel
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
I Sederhanakan: f (x1 , x2 , x3 ) =
f (x1 , x2 , x3 ) =
P
P
Literal, Implicant, Cover dan Cost
m(1, 3, 5, 7),
Ringkasan
m(0, 2, 3, 6, 7)
Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
21
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Desain Rangkaian Logika
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Dari sebuah K-map, implementasi rangkaian logika bisa mempunyai dua bentuk, yaitu:
Ringkasan
1. Jika diinginkan rangkaian logika dengan AND-OR atau NAND-NAND, maka persamaan logika SOP minimal dapat diperoleh dengan mengelompokkan minterm bernilai 1; 2. Jika diinginkan rangkaian logika dengan OR-AND atau NOR-NOR, maka persamaan logika POS minimal dapat diperoleh dengan mengelompokkan Maxterm bernilai 0;
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
22
Lisensi
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh K-Map 3 Variabel I
@2017,Eko Didik Widianto
Rancang rangkaian P NAND-NAND dari fungsi Q f (x1 , x2 , x3 ) = m(0, 1, 3, 4, 5, 7) dan f (x1 , x2 , x3 ) = M(2, 7)
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
23
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
K-Map 4 Variabel
@2017,Eko Didik Widianto
I
Bentuk K-map 4 variabel:
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
24
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh: Grouping K-Map 4 Variabel
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
I Sederhanakan f (x1 , x2 , x3 , x4 ) =
P
Literal, Implicant, Cover dan Cost
m(2, 3, 8 − 11, 13)
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
25
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Grouping K-Map 4 Variabel I
@2017,Eko Didik Widianto
Sederhanakan fungsi f (x1 , x2 , x3 , x4 ) =
Q
M(0, 2, 4, 8 − 12, 14) dengan K-map
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
I
Menghasilkan f (x1 , x2 , x3 , x4 ) = x 1 x4 + x2 x4 + x1 x 2 x3
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
26
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Umpan Balik: Grouping K-Map 4 Variabel
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan
Sederhanakan:
Lisensi
f (x1 , x2 , x3 ) =
P
I
f (x1 , x2 , x3 ) =
P
m(0 − 4, 6, 9, 11, 12, 14)
I
f (x1 , x2 , x3 ) =
P
m(0, 2, 5, 7, 8, 10, 13, 15)
I
m(3 − 7, 9, 11, 12 − 15)
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
27
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
K-Map 5 Variabel
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
28
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh K-map 5 Variabel I
@2017,Eko Didik Widianto
Sederhanakan fungsi f (x1 , x2 , x3 , x4 , x5 ) = P m(4, 5, 10, 12 − 14, 16 − 19, 24 − 27, 30)
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
29
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
K-map 6 Variabel I
Bagaimana K-Map 6 Variabel? Tidak berguna dari sudut pandang praktis I
@2017,Eko Didik Widianto
Akan membutuhkan perangkat CAD, salah satunya bmin http://bukka.eu/bmin/0.5.0 P
I Contoh: f (f , e, d, c, b, a) =
Peta Karnaugh Karnaugh Map Grouping K-Map
m(21, 23, 29, 31, 53, 55, 61, 63) = ace
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
30
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Bahasan
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Ringkasan
Lisensi
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
31
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Terminologi I
@2017,Eko Didik Widianto
Literal = variabel di suatu term I
Peta Karnaugh
Contoh: x 1 x2 x3 x 4 (term dg 4 literal), x2 x3 (term dg 2 literal)
Karnaugh Map Grouping K-Map
I
Implicant: sebarang term bernilai ’1’ atau grup term bernilai ’1’ yang dapat digabungkan di K-map I
I
I
Ringkasan
minterm adalah implicant dasar. Untuk fungsi n-variabel, minterm adalah implicant dengan n literal
Lisensi
Prime Implicant: implicant yang tidak bisa digabungkan dengan implicant lain untuk menghilangkan sebuah variabel I
I
Literal, Implicant, Cover dan Cost
Literal dalam prime implicant tidak dapat dihapus untuk mendapatkan implicant valid
Cover: suatu himpunan implicant yang menghasilkan nilai fungsi ’1’ Cost: jumlah gerbang ditambah jumlah total masukan ke semua gerbang dalam rangkaian logika
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
32
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Implicant dan Prime Implicant
@2017,Eko Didik Widianto Peta Karnaugh
I
I I I
I
Grouping K-Map
7 buah minterm 1 term 3-literal (grup 2 minterm) 2 term 2-literal (grup 4 minterm)
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Terdapat 3 prime implicant I I
x1 x 2 , x 2 x3 , x1 x 3 x4 Tidak bisa disederhanakan lagi? I
http://didik.blog.undip.ac.id/buku/sistem-digital/
Karnaugh Map
Terdapat 10 implicant valid
Untuk x1 x 2 , jika sebuah literal dihapus menyisakan x1 atau x2, padahal x1 bukan implicant valid karena {1,1,0,0} menghasilkan f = 0
@2017,Eko Didik Widianto
33
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Cover dan Cost
@2017,Eko Didik Widianto
I
Cover untuk f (x1 , x2 , x3 , x4 ) =
P
m(2, 3, 8, 9, 10, 11, 13)
Peta Karnaugh
1. Persamaan dengan semua minterm 2. f = x1 x 2 + x 1 x 2 x3 + x1 x 3 x4 merupakan cover valid 3. f = x1 x 2 + x 2 x3 + x1 x 3 x4 merupakan cover valid yang berisi prime implicant I
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
I
Cover yang berisi prime implicant cenderung menghasilkan implementasi dengan cost terendah
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
34
Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Menghitung Cost Rangkaian
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map
I
Fungsi f = x1 x 2 + x 2 x3 + x1 x 3 x4
I
NOT tidak diperhitungkan
Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Gerbang #Gerbang #Masukan AND-3 1 1×3=3 AND-2 2 2×2=4 OR-3 1 1×3=3 Total 4 10 Cost= 4 + 10 = 14
http://didik.blog.undip.ac.id/buku/sistem-digital/
Keterangan →x1 x 3 x4 →x1 x 2 dan x 2 x3
@2017,Eko Didik Widianto
35
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Jika Gerbang NOT Diperhitungkan
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan Lisensi
Gerbang
#Gerbang
#Masukan
Keterangan
AND-3
1
1×3=3
→x1 x 3 x4
AND-2
2
2×2=4
→x1 x 2 dan x 2 x3
NOT
2
2×1=2
→1 masukan, x2 dan x3
OR-3
1
1×3=3
Total
6
12
Gerbang
#Gerbang
#Masukan
Keterangan
AND-3
1
1×3=3
→x1 x 3 x4
AND-2
2
2×2=4
→x1 x 2 dan x 2 x3
NOT
3
3×1=3
→1 masukan, x2 dan x3
OR-3
1
1×3=3
http://didik.blog.undip.ac.id/buku/sistem-digital/ Total 7 13
Cost= 6 + 12 = 18
Didik Widianto Cost= 7 @2017,Eko + 13 = 20
36
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Prime Implicant Esensial dan Non-Esensial
@2017,Eko Didik Widianto
SOP minimum hanya mengandung prime implicant (namun tidak semua prime implicant)
Peta Karnaugh Karnaugh Map Grouping K-Map
I I
Literal, Implicant, Cover dan Cost
Essential: diperlukan untuk membentuk SOP minimum Nonessensial: tidak diperlukan untuk SOP minimum, sehingga dapat dihilangkan I I I I
Ringkasan Lisensi
Prime implicant: x1 x 2 , x 2 x3 , x1 x 3 x4 dan x2 x 3 x4 Esensial: x1 x 2 , x 2 x3 , dan x2 x 3 x4 non-esensial: x1 x 3 x4 fmin = x1 x 2 + x 2 x3 + x2 x 3 x4 , x1 x 3 x4 dihilangkan
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
37
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Contoh
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
I I I
Prime implicant: x1 x 2 , x 2 x3 , x 1 x2 x 3 , x 1 x2 x4 dan x 1 x3 x4 Esensial: x1 x 2 , x 2 x3 , dan x 1 x2 x 3 non-esensial: x 1 x2 x4 , x 1 x3 x4 (harus
Ringkasan Lisensi
dipilih salah satu)
I
http://didik.blog.undip.ac.id/buku/sistem-digital/
fmin = x1 x 2 +x 2 x3 +x 1 x2 x 3 +
@2017,Eko Didik Widianto
x 1 x2 x4 x 1 x3 x4
38
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Langkah Penyederhanaan
@2017,Eko Didik Widianto Peta Karnaugh
I I
Karnaugh Map
SOP minimum berisi semua prime implicant esensial dan beberapa prime implicant non-esensial Langkah menemukan rangkaian dengan cost minimum:
Grouping K-Map Literal, Implicant, Cover dan Cost
Ringkasan
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 I
Menentukan prime implicant non-esensial? heuristik (mencoba semua kemungkinan untuk mendapatkan cover dengan cost minimum)
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
39
Lisensi
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Latihan
@2017,Eko Didik Widianto Peta Karnaugh Karnaugh Map Grouping K-Map Literal, Implicant, Cover dan Cost
I I I
http://didik.blog.undip.ac.id/buku/sistem-digital/
Cari semua prime implicant dari f Cari set prime implicant esensial Cari cover dengan cost terendah dari semua kombinasi prime implicant non-esensial
@2017,Eko Didik Widianto
40
Ringkasan Lisensi
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Ringkasan Kuliah
@2017,Eko Didik Widianto Peta Karnaugh
I
I
I
I
Ringkasan
Yang telah kita pelajari hari ini:
Lisensi
Penyederhanaan fungsi logika menggunakan peta Karnaugh melalui Grouping minterm untuk rangkaian SOP, baik fungsi 2-variabel sampai 6-variabel Terminologi dalam K-map, yaitu implicant, prime implicant (esensial, non-esensial), cover dan cost beserta contoh penggunaan istilah-istilah tersebut
Yang akan kita pelajari di pertemuan berikutnya adalah penyederhanaan fungsi logika menggunakan peta Karnaugh melalui grouping Maxterm untuk rangkaian POS, fungsi tidak lengkap dan rangkaian multikeluaran
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
41
Peta Karnaugh & Rangkaian Multi-Keluaran (Bagian 1)
Lisensi
@2017,Eko Didik Widianto
Creative Common Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)
Peta Karnaugh Ringkasan
I Anda bebas: I
I
Lisensi
untuk Membagikan — untuk menyalin, mendistribusikan, dan menyebarkan karya, dan untuk Remix — untuk mengadaptasikan karya
I Di bawah persyaratan berikut: I
I
Atribusi — Anda harus memberikan atribusi karya sesuai dengan cara-cara yang diminta oleh pembuat karya tersebut atau pihak yang mengeluarkan lisensi. Atribusi yang dimaksud adalah mencantumkan alamat URL di bawah sebagai sumber. Pembagian Serupa — Jika Anda mengubah, menambah, atau membuat karya lain menggunakan karya ini, Anda hanya boleh menyebarkan karya tersebut hanya dengan lisensi yang sama, serupa, atau kompatibel.
I Lihat: Creative Commons Attribution-ShareAlike 3.0 Unported License I Alamat URL: http://didik.blog.undip.ac.id/buku/sistem-digital/
http://didik.blog.undip.ac.id/buku/sistem-digital/
@2017,Eko Didik Widianto
42