tsk205 kuliah4 petakarnaugh v3
Post on 07-Jul-2018
236 Views
Preview:
TRANSCRIPT
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
1/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Rangkaian Logika Optimal: Peta
Karnaugh & Rangkaian Multi-KeluaranKuliah#4 TSK205 Sistem Digital - TA 2011/2012
Eko Didik Widianto
Teknik Sistem Komputer - Universitas Diponegoro
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
2/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Umpan Balik
Sebelumnya dibahas tentang implementasi fungsi logikamenjadi suatu rangkaian logika (disebut proses sintesis),baik menggunakan tabel kebenaran, maupun aljabarBoolean
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 diperoleh dengan penyederhanaanekspresi logika secara Aljabar
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
3/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Tentang Kuliah
Dalam kuliah ini, akan dibahas tentang rangkaian logikaoptimal, meliputi:
penyederhanaan fungsi logika menggunakan peta
Karnaugh strategi minimalisasi SOP/POS fungsi dengan don’t care rangkaian dengan banyak keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
4/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Kompetensi Dasar
Setelah mempelajari bab ini, mahasiswa akan mampu:
1. [C3] Mahasiswa akan mampu menggunakan don’t care
dalam peta Karnaugh
2. [C6] Mahasiswa akan mampu mendesain rangkaian logika
optimal dengan menyederhanakan persamaan logika
menggunakan peta Karnaugh3. [C6] Mahasiswa akan mampu mendesain rangkaian logika
optimal dengan menggabungkan beberapa fungsi dalam
satu rangkaian multi-keluaran
Link
Website:
Email: didik@undip.ac.id
mailto:didik@undip.ac.idmailto:didik@undip.ac.idhttp://didik.blog.undip.ac.id/2012/02/24/kuliah-sistem-digital-tsk-205-2011/http://didik.blog.undip.ac.id/2012/02/24/kuliah-sistem-digital-tsk-205-2011/http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
5/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Bahasan
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
6/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Rangkaian Optimal
Rangkaian optimal
Cost rangkaian minimal: jumlah gerbang (dan transistor),
jumlah jalur Fungsional terpenuhi Constraint terpenuhi: delay, fanout (driving ), area
Rangkaian optimal bisa diperoleh dengan teknik:
1. Penyederhanaan fungsi logika
Menggunakan prinsip-prinsip Aljabar Boolean Menggunakan Karnaugh Map
2. Penggunaan gerbang secara bersama untuk beberapafungsi sekaligus, membentuk rangkaian multi-keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
7/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Bahasan
Peta KarnaughKarnaugh MapGrouping K-MapLiteral, Implicant, Cover dan CostRangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
8/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Prinsip Penyederhanaan
Operasi penyederhanaan adalah mengurangi minterm atau maxterm diekspresi
SOP: menggunakan hukum 14a (x · y + x · y = x ) POS: menggunakan hukum 14b ((x + y ) · (x + y ) = x )
Beberapa minterm atau maxterm dapat digabungkan menggunakanhukum 14a atau 14b jika berbeda hanya di satu variabel sajaf
x 1, x 2, x 3
= x 1x 2 x 3 + x 1x 2 x 3 + x 1 x 2 x 3 + x 1 x 2x 3
m 1 dan m 5 berbeda di x 1, dan m 4 dan m 6 berbeda di x 2
f = x 1x 2 x 3 + x 1x 2 x 3 + x 1 x 2x 3 + x 1 x 2x 3
=
x 1 + x 1
x 2 x 3 + x 1 (x 2 + x 2 )x 3
= x 2x 3 + x 1 x 3
f x, x, x
=
x + x + x
x + x + x
x + x + x
x + x + x
M 0 dan M 2 berbeda di x 2, dan M 4 dan M 7 berbeda di x 1
f =
x 1 + x 3
+ x 2x 2
x 1x 1 +
x 2 + x 3
=
x 1 + x 3
x 2 + x 3
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
9/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
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
K-map juga merupakan alternatif untuk menyatakan suatu
fungsi logika selain tabel kebenaran dan ekspresi logika K-map disusun atas sel-sel. Satu sel, satu minterm
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
10/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Bahasan
Peta KarnaughKarnaugh MapGrouping K-MapLiteral, Implicant, Cover dan CostRangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
11/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Grouping K-Map
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
Variabel yang dieliminasi adalah yang mempunyai
perbedaan nilai di group, vertikal/horizontal Group merah: x 1 dieliminasi, Grup biru: x 2 dieliminasi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
12/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Ketentuan dan Tips Grouping
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
R k i L ik
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
13/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 3) dan f =
m (1, 2)
f =
m (0, 3) = x 1x 2 + x 1x 2 –> fungsi SOP tidak dapatdisederhanakan
f =
m (1, 2) = x 1x 2 + x 1x 2 –> fungsi SOP tidak dapatdisederhanakan
Rangkaian Logika
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
14/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 3) dan f =
m (1, 2)
f =
m (0, 3) = x 1x 2 + x 1x 2 –> fungsi SOP tidak dapatdisederhanakan
f =
m (1, 2) = x 1x 2 + x 1x 2 –> fungsi SOP tidak dapatdisederhanakan
Rangkaian Logika
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
15/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 1) dan f =
m (1, 3)
f =
m (0, 1) = x 1x 2 + x 1x 2 = x 1, x 2
f =
m (1, 3) = x 1x 2 + x 1x 2 = x 2, x 1dieliminasi
Rangkaian Logika
C h G i F i V i b l
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
16/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 1) dan f =
m (1, 3)
f =
m (0, 1) = x 1x 2 + x 1x 2 = x 1, x 2
f =
m (1, 3) = x 1x 2 + x 1x 2 = x 2, x 1dieliminasi
Rangkaian Logika
C h G i F i 2 V i b l
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
17/53
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 1, 2) dan f =
m (1, 2, 3)
f =
m (0, 1, 2) = x 1x 2 + x 1x 2 + x 1x 2 = x 1 + x 2 f =
m (1, 2, 3) = x 1x 2 + x 1x 2 + x 1x 2 = x 1 + x 2
Rangkaian Logika
C t h G i F i 2 V i b l
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
18/53
a g a a og a
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh Grouping Fungsi 2 Variabel
Sederhanakan: f =
m (0, 1, 2) dan f =
m (1, 2, 3)
f =
m (0, 1, 2) = x 1x 2 + x 1x 2 + x 1x 2 = x 1 + x 2 f =
m (1, 2, 3) = x 1x 2 + x 1x 2 + x 1x 2 = x 1 + x 2
Rangkaian Logika
K M 3 V i b l
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
19/53
g g
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
K-Map 3 Variabel
K-map disusun sehingga minterm yang berdekatan hanya
mempunyai perbedaan 1 variabel
x 1 x 2 x 3 minterm m j
0 0 0 m 0 = x 1x 2x 30 0 1 m 1 = x 1x 2x 30 1 0 m 2 = x 1x 2x 30 1 1 m 3 = x 1x 2x 31 0 0 m 4 = x 1x 2x 3
1 0 1 m 5 = x 1x 2x 31 1 0 m 6 = x 1x 2x 31 1 1 m 7 = x 1x 2x 3
Rangkaian Logika
Contoh K Map 3 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
20/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta KarnaughKarnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh K-Map 3 Variabel
Sederhanakan f =
m (0, 1, 2, 5)
Rangkaian Logika
Contoh K Map 3 Variabel
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
21/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh K-Map 3 Variabel
Sederhanakan: f =
m (1, 3, 5, 7), f =
m (0, 2, 3, 6, 7)
Rangkaian Logika
O ti l P tContoh K Map 3 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
22/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh K-Map 3 Variabel
Sederhanakan: f =
m (1, 3, 5, 7), f =
m (0, 2, 3, 6, 7)
Rangkaian Logika
Optimal: PetaContoh K Map 3 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
23/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh K-Map 3 Variabel
Sederhanakan: f =
m (0, 1, 3, 4, 5, 7) danf =
m (0, 1, 3, 4, 5, 6)
Rangkaian Logika
Optimal: PetaContoh K Map 3 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
24/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh K-Map 3 Variabel
Sederhanakan: f =
m (0, 1, 3, 4, 5, 7) danf =
m (0, 1, 3, 4, 5, 6)
Rangkaian Logika
Optimal: PetaK-Map 4 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
25/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
K-Map 4 Variabel
Bentuk K-map 4 variabel:
Rangkaian Logika
Optimal: PetaContoh: Grouping K-Map 4 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
26/53
Optimal: PetaKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh: Grouping K-Map 4 Variabel
Sederhanakan f =
m (2, 3, 8 − 11, 13)
Rangkaian Logika
Optimal: PetaContoh: Grouping K-Map 4 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
27/53
pKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Contoh: Grouping K Map 4 Variabel
Sederhanakan f =
m (2, 3, 8 − 11, 13)
Rangkaian Logika
Optimal: PetaUmpan Balik: Grouping K-Map 4 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
28/53
pKarnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Umpan Balik: Grouping K Map 4 Variabel
Sederhanakan:
f =
m (3 − 7, 9, 11, 12 − 15)
f =
m (0 − 4, 6, 9, 11, 12, 14) f =
m (0, 2, 5, 7, 8, 10, 13, 15)
Rangkaian Logika
Optimal: PetaK-Map 5 Variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
29/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
K Map 5 Variabel
Bagaimana K-Map 6 Variabel? Tidak berguna dari sudutpandang praktis
Akan membutuhkan perangkat CAD
Rangkaian Logika
Optimal: PetaK h
Bahasan
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
30/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Bahasan
Peta KarnaughKarnaugh MapGrouping K-MapLiteral, Implicant, Cover dan CostRangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
Rangkaian Logika
Optimal: PetaK h &
Terminologi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
31/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Terminologi
Literal = variabel di suatu term
Contoh: x 1x 2x 3x 4(term dg 4 literal), x 2x 3(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 digabungkandengan implicant lain untuk menghilangkan sebuahvariabel
Literal dalam prime implicant tidak dapat dihapus untuk
mendapatkan implicant valid
Cover : suatu himpunan implicant yang menghasilkan nilaifungsi ’1’
Cost : jumlah gerbang ditambah jumlah total masukan kesemua gerbang dalam rangkaian logika
Rangkaian Logika
Optimal: PetaKarnaugh &
Implicant dan Prime Implicant
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
32/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
p p
Terdapat 10 implicant valid
7 buah minterm 1 term 3-literal (grup 2 minterm) 2 term 2-literal (grup 4 minterm)
Terdapat 3 prime implicant
x 1x 2, x 2x 3, x 1x 3x 4 Tidak bisa disederhanakan lagi?
Untuk x 1x 2, jika sebuah literaldihapus menyisakan x 1 ataux 2, padahal x 1bukan implicantvalid karena {1,1,0,0}menghasilkan f = 0
Rangkaian Logika
Optimal: PetaKarnaugh &
Cover dan Cost
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
33/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Cover untuk f =m (2, 3, 8, 9, 10, 11, 13)1. Persamaan dengan semua minterm2. f = x 1x 2 + x 1x 2x 3 + x 1x 3x 4 3. f = x 1x 2 + x 2x 3 + x 1x 3x 4 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
Rangkaian Logika
Optimal: PetaKarnaugh &
Prime Implicant Esensial dan Non-Esensial
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
34/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
p
SOP minimum hanya mengandung prime implicant (namun
tidak semua prime implicant)
Essential: diperlukan untuk membentuk SOP minimum Nonessensial: tidak diperlukan untuk SOP minimum, sehingga
dapat dihilangkan
Prime implicant: x 1x 2, x 2x 3, x 1x 3x 4 x 2x 3x 4
Esensial: x 1x 2, x 2x 3, x 2x 3x 4 non-esensial: x 1x 3x 4 f min = x 1x 2 + x 2x 3 + x 2x 3x 4 , x 1x 3x 4
Rangkaian Logika
Optimal: PetaKarnaugh &
Contoh
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
35/53
Karnaugh &Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Prime implicant: x 1x 2, x 2x 3, x 1x 2x 3
x 1x 2x 4 x 1x 3x 4 Esensial: x 1x 2, x 2x 3, x 1x 2x 3 non-esensial: x 1x 2x 4 x 1x 3x 4
f min = x 1x 2 +x 2x 3 +x 1x 2x 3 +
x 1x 2x 4x 1x 3x 4
Rangkaian Logika
Optimal: PetaKarnaugh &
Ringkasan
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
36/53
gRangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
SOP minimum berisi semua prime implicant esensial danbeberapa 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 dimanaf = 1, maka set ini adalah cover dari f yang diinginkan. Jikatidak, 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)
Rangkaian Logika
Optimal: PetaKarnaugh &
Latihan
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
37/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Cari semua prime implicant dari f Cari set prime implicant esensial Cari cover dengan cost terendah
dari semua kombinasi primeimplicant non-esensial
Rangkaian Logika
Optimal: PetaKarnaugh &
Bahasan
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
38/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Peta KarnaughKarnaugh MapGrouping K-MapLiteral, Implicant, Cover dan CostRangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
Rangkaian Logika
Optimal: PetaKarnaugh &R k i
Minimisasi Ekspresi POS
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
39/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Menggunakan prinsip dualitas K-map dapat langsung dibentuk baik dari ekspresi
m
maupun
M Shortcut:
Maxterm mempunyai valuasi fungsi ’0’ Grouping Maxterm sebesar mungkin Bentuk persamaan POS dari set Maxterm minimum
Prinsip prime implicant esensial berlaku? bisa, denganpengertian implicant adalah Maxterm atau group Maxterm
Rangkaian Logika
Optimal: PetaKarnaugh &R k i
POS Minimal dari
m atau
M
http://find/http://goback/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
40/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Diberikan: f =
m (0, 1, 2, 5)
f =
m (0, 1, 2, 5)
= (x 1 + x 3) (x 2 + x 3) ; POS
= x 1x 3 + x 2x 3; SOP
=
M (3, 4, 6, 7)
Diberikan: f =
M (1, 4, 5)
f =
M (1, 4, 5)
= (x
1 + x
2) (x
2 + x
3) ; POS
= x 2 + x 1x 3; SOP
=
m (0, 2, 3, 6, 7)
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
POS 4-Variabel Minimal
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
41/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
f =
m (2, 3, 8, 9, 10, 11, 13)
=
M (0, 1, 4, 5, 6, 7, 12, 14, 15)
Prime implicant: x 1 + x 3, x 2 + x 3,x 2 + x 4 x 1 + x 2
Esensial: x 1 + x 3, x 2 + x 3, dan x 2 + x 4 non-esensial: x 1 + x 2 (biru) f min = (x 1 + x 3) (x 2 + x 3) (x 2 + x 4)
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Latihan di Rumah
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
42/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Persamaan POS Cari semua prime implicant dari f Cari set prime implicant esensial Cari cover dengan cost terendah
dari semua kombinasi primeimplicant non-esensial
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Bahasan
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
43/53
Rangkaian
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Peta KarnaughKarnaugh MapGrouping K-MapLiteral, Implicant, Cover dan CostRangkaian POS Optimal
Fungsi Tidak Lengkap
Rangkaian Multi-Keluaran
Lisensi
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Fungsi Tidak Lengkap
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
44/53
a g a a
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Dalam sistem digital, sering terjadi beberapa kondisi inputyang 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 diberikan0 atau 1 di tabel kebenaran)
Fungsi yang mengandung kondisi don’t care disebutfungsi yang dispesifikasikan tidak lengkap (incompletely specified )
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Contoh Don’t Care
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
45/53
g
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
Di K-Map, masukan don’t care bisa diberi nilai 0 atau 1sedemikian sehingga diperoleh fungsi yang optimal
x 1 x 2 x 3 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. Kombinasimasukan {x 2x 1} = 10 | 11 tidakpernah terjadi, selebihnyaf =
m (1, 4, 5, 6)
f =
m (1,
4,
5,
6) + D (2,
3); atauf =
M (0, 7) · D (2, 3)
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Contoh Don’t Care 4 variabel
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
46/53
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
Karnaugh Map
Grouping K-Map
Literal, Implicant, Cover dan
Cost
Rangkaian POS Optimal
Fungsi Tidak Lengkap
RangkaianMulti-Keluaran
Lisensi
SOP: f =
m (2, 4, 5, 6, 10) + D (12, 13, 14, 15) POS: f =
M (0, 1, 3, 7, 8, 9, 11) · D (12, 13, 14, 15)
SOP: f min = x 2x 3 + x 3x 4, POS: f min = (x 2 + x 3) (x 3 + x 4) Jika don’t care tidak disertakan: misalnya menganggap nilainya
selalu 0
SOP: f = x 1x 2x 3 + x 1x 3x 4 + x 2x 3x 4 POS: f = (x 2 + x 3) (x 3 + x 4) (x 1 + x 2) Cost mungkin lebih tinggi
Rangkaian Logika
Optimal: PetaKarnaugh &Rangkaian
Rangkaian dengan Banyak Keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
47/53
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Sebelumnya dibahas fungsi dengan keluaran tunggalberikut dengan implementasi rangkaiannya
Dalam prakteknya, beberapa fungsi tunggal tersebutmerupakan bagian dari rangkaian logika yang lebih besar
Rangkaian-rangkaian dari fungsi tersebut mungkin dapatdikombinasikan ke dalam rangkaian tunggal dengancost lebih murah dengan keluaran multiple
Pemakaian bersama blok gerbang oleh beberapa rangkaian
fungsi tunggal
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
M lti K l
Contoh Rangkaian Multi-Keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
48/53
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
f 1 = x 1x 3 + x 1x 3 + x 2x 3x 4, Cost=4 gerbang + 10 input(=14)
f 2 = x 1x 3 + x 1x 3 + x 2x 3x 4, Cost=4 gerbang + 10 input (=14) Cost total jika kedua fungsi diimplementasikan terpisah: 8
gerbang + 20 input (=28)
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
Multi Keluaran
Contoh Rangkaian Multi-Keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
49/53
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Mengkombinasikan (prime) implicant yang sama dari dua/lebih
fungsi mungkin bisa mengurangi cost
Rangkaian multi-keluaran:
f 1f 2
= x 1x 3 + x 1x 3 +
x 2x 3x 4
x 2x 3x 4
Cost=6 gerbang + 16 input(=22)
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
Multi Keluaran
Contoh Rangkaian Multi-Keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
50/53
Multi-Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Di contoh sebelumnya, terdapat prime implicant yang shared.Kalau tidak ada yang shared?
f 1
= x 1
x 4
+ x 2
x 4
+ x 1
x 2
x 3
, Cost=4 gerbang + 10 input(=14) f 2 = x 1x 4 + x 2x 4 + x 1x 2x 3x 4, 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)
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
Multi-Keluaran
Contoh Rangkaian Multi-Keluaran
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
51/53
Multi Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Tapi ada alternatif realisasi lainnya: menggunakan implicant
bersama antara 2 fungsi
f 1 = x 1x 2x 4 + x 1x 2x 3x 4 + x 1x 4 f 2 = x 1x 2x 4 + x 1x 2x 3x 4 + x 2x 4 Rangkaian multikeluaran:
f 1f 2
= x 1x 2x 4 + x 1x 2x 3x 4 +
x 1x 4x 2x 4
Cost gabungan total= 6 gerbang + 17 input (=23)
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
Multi-Keluaran
Latihan
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
52/53
Multi Keluaran
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Cari cost terendah untuk POSnya!
Rangkaian LogikaOptimal: Peta
Karnaugh &Rangkaian
Multi-Keluaran
Lisensi
http://find/
-
8/19/2019 TSK205 Kuliah4 PetaKarnaugh v3
53/53
@2012,Eko Didik
Widianto
Peta Karnaugh
RangkaianMulti-Keluaran
Lisensi
Creative Common Attribution-ShareAlike 3.0 Unported (CC
BY-SA 3.0)
Anda bebas: untuk Membagikan — untuk menyalin, mendistribusikan,
dan menyebarkan karya, dan untuk Remix — untuk mengadaptasikan karya
Di bawah persyaratan berikut:
Atribusi — Anda harus memberikan atribusi karya sesuai
dengan cara-cara yang diminta oleh pembuat karya
tersebut atau pihak yang mengeluarkan lisensi. Pembagian Serupa — Jika Anda mengubah, menambah,
atau membuat karya lain menggunakan karya ini, Anda
hanya boleh menyebarkan karya tersebut hanya denganlisensi yang sama, serupa, atau kompatibel.
Lihat: Creative Commons Attribution-ShareAlike 3.0Unported License
http://creativecommons.org/licenses/by-sa/3.0/http://creativecommons.org/licenses/by-sa/3.0/http://creativecommons.org/licenses/by-sa/3.0/http://creativecommons.org/licenses/by-sa/3.0/http://find/
top related