Karnaugh MAP (K-Map)
Pokok Bahasan :
1. K-map 2 variabel
2. K-map 3 variabel
3. K-map 4 variabel
4. Penyederhanaan rangkaian dengan k-map
Tujuan Instruksional Khusus :
[Link] dapat menerangkan dan memahami cara
membuat k-map 2, 3, 4 variabel.
[Link] dapat menerangkan dan memahami cara
peng-cover-an minterm dalam sebuah k-map..
[Link] dapat menyederhanakan persamaan logika
melalui metode k-map.
1
Karnaugh Map (K-Map)
Suatu peralatan grafis yang digunakan untuk menyederhanakan
persamaan logika atau mengkonversikan sebuah tabel
kebenaran menjadi sebuah rangkaian logika.
Salah satu metode yang paling mudah untuk
penyederhanaan Rangkaian Logika.
Karnaugh Map 2 Variabel :
( A dan B )
B
Map
Value
0
1
2
3
A
0
0
1
1
Tabel Kebenaran
B
0
1
0
1
AB AB
0
Model I
1
AB
AB
AB
AB
Map Value
AB
A
AB
AB AB
0
Model II
AB
AB
Desain Pemetaan K- Map
2 Variabel
B
B
A
Karnaugh Map 2 Variabel :
dengan minterm-mintermnya
x
0
x
y
0
1
xy xy
xy
xy
F = (m0,m1) = xy + xy
x
F=AB
+AB
1
0 0 1
1 1 0
F=AB +AB +AB
1
0 0 1
1 1 1
A
1
0
F=AB
0 1 +AB
F=AB +AB +AB
F=A+
B
1 0
1
01
00 1
11 1
Contoh : 1
B
Tabel Kebenaran
Map
Value
0
1
2
3
A
0
0
1
1
B
0
1
0
1
A
0
Y
1 AB
0
0
1
1
0
0
2
1
1
1
3
B
1
AB
AB
Jadi Y = AB + AB
0
1
0 AB
1
2
Contoh : 2
B
Tabel Kebenaran
Map
Value
0
1
2
3
A
0
0
1
1
B
0
1
0
1
Y
1
1
0
0A
A
0
AB
1
0
1
1
1
2
0
3
AB
B
1
0
Jadi Y = A
AB
0
AB
1
1
2
0
3
Catatan untukK-Map 2 Variabel
0 kotak terlingkupi = 0 (Low)
1 kotak terlingkupi = 2 variabel output
2 kotak terlingkupi = 1 variabel output
4 kotak terlingkupi = 1 (High)
Melingkupinya harus posisi Horisontal
atau vertikal , yang dilingkupi digit 1
dan jumlah digit 1 yang dilingkupi 2n (1,
0
1
1
AB
0
1
1
AB
Y = AB + AB
2,4,8,16, ...)
1
1
1
B
Y = B + A
Contoh 3:
Dari Tabel Kebenaran dibawah, tulis persamaan
logikanya dengan menggunakan K-map :
Map
Value
0
1
2
3
A
0
0
1
1
B
0
1
0
1
Y
1
1
0
1
A
1
B
0
1
Jadi Y = A + B
1
1
Contoh 4:
10
Sederhanakan persamaan logika :
Y = A + AB + AB
Menggunakan K- map :
A
1
B
0
B
1
1
A
1
1
B
B
B
0
1
A
1
Jadi Y = A + B
11
Karnaugh Map 3 Variabel :
( A, B dan C )
Tabel Kebenaran
Map
Value
A B C Y
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
BC
00
0 ABC
1
Model I
01
11
ABC
ABC
ABC
ABC
ABC
ABC
ABC
Map Value
Model II
AB
00
0
10
11
01
10
ABC
ABC
ABC
ABC
ABC
ABC
ABC
1 ABC
1
Map
Value
A B C Y
0Tabel0 Kebenaran
0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
AB
CModel III
0
00
ABC
ABC
ABC
ABC
ABC
ABC
ABC
ABC
01
11
10
Model IV
BC
00
Map Value
ABC
ABC
01
ABC
ABC
10
ABC
ABC
Desain Pemetaan K- Map
3 Variabel
C
C
BC
00
A
0
01
11
10
A
A
B
Catatan untuk KMap 3 Variabel
0 kotak terlingkupi = 0 (Low)
1 kotak terlingkupi = 3 variabel output
2 kotak terlingkupi = 2 variabel output
4 kotak terlingkupi = 1 variabel output
8 kotak terlingkupi = 1 (High)
Melingkupinya harus posisi Horisontal
atau vertikal , yang dilingkupi digit 1
dan jumlah digit 1 yang dilingkupi 2n (1,
00
01
11
10
Y = ABC + ABC
+ ABC
0
1
2, 4,
8, ... )
A0
00
01
11
1
1
1
A
0
1
BC00
1
1
01
11
10
11
1
10
1
1
Contoh pengcoveran
C
AB
00
A
11
10
01
ab
c
00 01 11 10
0
C 1
1
cout = ab + bc + ac
B
0 0 1 0
0 1 1 1
A
C
G(A,B,C) = A
0 0
A
1
ab
c
00 01 11 10
0 0 0 1 1
1 0 0 1 1
f=a
1
1
F(A,B,C) =
m(0,4,5,7)= AC + BC
A
0
A
0
0
0
0
1
1
1
1
BC
00 01 11 10
0 1 0 1
11 1 1 1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
1
1
0
1
1
1
1
F=ABC +AB C +ABC +ABC + ABC +
ABC
BC
00 01 11 10
A
001 0 1
1 1 1 1 1 F=A+B C
F=ABC +AB C +ABC +ABC + ABC +
ABC
Contoh 1 :
Tabel Kebenaran
Diketahui Tabel Kebenaran seperti disamping :
Cari persamaan
logikanya :
Map
Value
A B C Y
0
1
2
3
4
5
6
7
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
0
1
1
1
BC
A
0
00
01
11
10
AB
AB
AC
1
Jadi Y = AC + AB + AB
Contoh 2 :
Diketahui Persamaan Boolean :
D = ABC + ABC + ABC + ABC + ABC
Sederhanakan dengan metode K-map
A
0
BC
00
01
10
11
BC
00
01
0
1
ABC
ABC
A
ABC
ABC
1
ABC
11
10
19
AC
Jadi D = B + AC
20
Karnaugh Map 4 Variabel :
( A, B, C dan D )
Tabel Kebenaran
Map
Valu
e
D CD
Y
AB
0
CD 8
10
11
12
13
14
15
00
01
ABCD ABCD
11
ABCD
10
ABCD
ABCD
ABCD
ABCD
ABCD
ABCD
ABCD
ABCD
ABCD
12
13
15
14
ABCD
ABCD
ABCD
ABCD
11
10
00
01
ABCD ABCD
11
ABCD
10
ABCD
12
ABCD
ABCD
ABCD
ABCD
13
ABCD
ABCD
ABCD
ABCD
15
11
ABCD
ABCD
ABCD
ABCD
14
10
00
01
Model 1
11
10
AB
00
01
Model 2
11
10
20
Dengan wxyz input
21
Desain Pemetaan K- Map
4 Variabel
A
AB
CD
00
A
01
11
00
10
C
01
D
D
11
10
B
B
Catatan untuk KMap 4 Variabel
AB
CD
00
0 kotak terlingkupi = 0 (Low)
1 kotak terlingkupi = 4 variabel output
2 kotak terlingkupi = 3 variabel output
4 kotak terlingkupi = 2 variabel output
8 kotak terlingkupi = 1 variabel output
16 kotak terlingkupi = 1 (High)
Melingkupinya harus posisi Horisontal
atau vertikal , yang dilingkupi digit 1 dan
jumlah digit 1 yang dilingkupi 2n ( 1,2, 4,
8,
16, ... )
01
11
10
00
01
1
1
1
1
1
1
1
1
11
1
1
10
1
1
ABCD
AC
BC
A ACD
ABCD
AB
CD
00
00
01
11
1
1
01
11
10
1
1
23
10
Contoh pengcoveran
A
A0
D
C
D
C
K-map untuk LT
K-map untuk EQ
K-map untuk GT
LT =
EQ = GT
24
Contoh pengcoveran
A' B' D + A'B'C'D' + A'BC'D + ABCD + AB'CD
A' C
B C' D' + A C' + A B D'
B' C D
25
CD
00
11
00 0 0 0 1
AB
10
01 01
11
10
F= ABC +ACD +ABC
+AB CD +ABC +AB C
1 1 0 1
1 1 1 1
1 0 1 1
F=BC +CD + AC+ AD
Contoh 1
F(A,B,C,D) =
m(0,2,3,5,6,7,8,10,11,14,15)
F=
C +
ABD
+ BD
0111
A
1
C 1
C
0000
1111
1000
Kalau digambarkan dengan system coordinate
26
Contoh 2 : Diketahui Tabel Kebenaran ,
cari persamaan logikanya.
AB
CD
00
00
Map
Value
A B
01
0 0
0 0
0 0
11
C
10
0 0
0 1
0 1
0 1
0 1
1 0
1 0
10
1 0
11
1 0
12
1 1
13
1 1
14
1 1
15
1 1
01
11
1
1
1
1
1
1
1
00
01
11
10
00
01
AC
A B
AB
CD
10
1
1
1
1
1
1
ABCD
ABD
Jadi Y = AC + ABD + ABCD
27
YZ
WX
00
00
1
01
11
Y 10
W
01
11
Contoh 3 : Lingkarilah dan
Tulis Persamaan Logikanya.
10
1
1
1
1
X
1
1
Z
WXZ
WX
YZ
00
00
WXYZ
YZ
W
01
11
10
01
Y
11
1
1
1
10
Y
WXZ
Jadi M = WXYZ + WXZ + WXXZ + YZ
28
Physical Implementasi
A
B C
D
11
C 10
Step 1: Truth table
Step 2: K-map
EQ
Step 3: Minimized sum-ofproducts
Step 4: Implementasi dengan
gates
A
Physical Implementasi
K-map untuk EQ
29
Poin-poin penggunaan K-map
Buat persamaan ke
bentuk SOP (melalui
tabel kebenaran).
Minterm-mintermnya
masukkan ke k-map
( sesuaikan jumlah
kotak atau variabel
input).
Lingkari (pe-ngcoveran) yang benar.
Tulis persamaan
logika hasil pengcoveran.
30
Dont Care
Kondisi dont care merupakan kondisi dimana ada beberapa
kombinasi variable input yang tidak selalu dapat dinyatakan
nilai outputnya.
Keadaan dimana nilai outputnya tersebut bisa berlogic 1 atau
berlogic 0 yang disimbulkan dengan X atau d.
Kegunaan dari kondisi dont care pada penyederhanaan fungsi
dapat dinyatakan pada fakta bahwa dapat diset dengan logic
1 atau logic 0, berdasar kegunaannya untuk format
kelompok logic 1 yang lebih besar.
Karnaugh maps: dont cares (contd)
f(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13)
f = A'D + B'C'D tanpa don't cares
f = AD + CD
dengan don't cares
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
+1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
f
0
1
0
1
0
1
X
1
0
1
0
0
X
X
0
0
Pengcoveran dengan Dont Cares
CD
AB
00
01
11
10
00
01
11
10
0
x
1
x
1
x
1
0
0
x
1
1
0
1
x
1
F=ACD+B+AC
Bentuk ilustrasi pengkoveran
A
6 prime implicants:
1
0
X
A'B'D, BC', AC, A'C'D, AB, B'CD
essential
minimum cover: 3 essential implicants
minimum cover: AC + BC' + A'B'D
A
5 prime implicants:
BD, ABC', ACD, A'BC, A'C'D
essential
C
0
1
minimum cover: 4 essential implicants
minimum cover: ABC+ACD+ABC+ACD
0
34
Aplikasi K-map
Pada Rangkaian Full Adder
Cin
A
B
Adder
A
0
0
0
0
1
1
1
1
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
Metode Aljabar Boole
S = ABCin + ABCin + ABCin + ABCin
Cout = ABCin + A BCin + ABCin + ABCin
= ABCin + ABCin + ABCin + ABCin + ABCin + ABCin
= (A + A)BCin + (B + B)ACin + (Cin + Cin)AB
= 1BCin + 1 ACin + 1 AB
35
Aplikasi K-map
Pada Rangkaian Full Adder
= BCin + ACin + AB
36
Cin
Adder
Cout
A
0
0
0
0
1
1
1
1
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
Cin
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Pengisiaan digit 1 ke K-map
Karnaugh Map for Cout
Cin
Adder
A
0
0
0
0
1
1
1
1
Cout
A
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
Cin
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Pengcoveran pertama.
Karnaugh Map untuk Cout
Cout = ACin
Cin
Adder
A
0
0
0
0
1
1
1
1
Cout
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Pengcoveran kedua.
Karnaugh Map for Cout
38
Cin
Cout = Acin + AB
Karnaugh Map for Cout
39
Cin
Adder
A
0
0
0
0
1
1
1
1
Cout
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Cin
Karnaugh Map untuk Cout
39
Pengcoveran
ketiga
(seluruhnya)
Cout = ACin + AB + BCin
Karnaugh Map untuk Cout
40
Cin
A
B
A
0
0
0
0
1
1
1
1
Adder
Cout
Cin
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
S = ABCin
Karnaugh Map untuk S
40
Cin
S = ABCin
Karnaugh Map untuk S
40
Cin
Adder
A
0
0
0
0
1
1
1
1
B
Cout
A
1
Cin
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
0
B
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Karnaugh Map untuk S
41
S = ABCin + ABCin
41
Cin
Adder
Cout
A
0
0
0
0
1
1
1
1
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
Cin
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
Karnaugh Map untuk S
42
S = ABCin + ABCin + ABCin
42
Coba anda gambar rangkaian diagramnya ?
Cin
Adder
Cout
A
0
0
0
0
1
1
1
1
S
0
1
1
0
1
0
0
1
Cout
0
0
0
1
0
1
1
1
Cin
B Cin
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
S = ABCin + ABCin + ABCin + ABCin
43
Karnaugh untuk S
Tidak bisa direduksi
43
Latihan Soal 1:
Gambarlah K-map untuk setiap ekspresi logika
dibawah serta sederhanakan dengan pengcoveran
yang benar :
1. AB + BC + AB
2. AC + ACB + BC + BC
3. XY + XZ + YZ
4. XY +YZ + XZ +XY
44
Latihan Soal 2 :
Gambarlah K-map untuk setiap ekspresi logika
dibawah serta sederhanakan dengan pengcoveran
yang benar :
1. A(BC + C) + B(A + AC)
2. (AC + ACB). (BC + BC)
3. Z(XY + XZ) . YZ(X+ Z)
Catatan : cari minterm-mintermnya dulu (rubah kebentuk SOP)