Metode Peta Karnaugh

ini merupakan sambungan dari Aljabar booelen dan aplikasinya

2.2 Metode Peta Karnaugh

Metode Peta Karnaugh (atau K-map) merupakan metode grafis untuk menyederhanakan fungsi Boolean. Peta Karnaugh adalah diagram/peta yang berbentuk dari kotak-kotak yang bersisian. Caranya dengan menggambarkan kotak-kotak yang berisi “Minterm” (Minimum-Terms)

a. Peta Karnaugh dengan dua peubah

Misalkan dua peubah di dalam fungsi Boolean adalah x dan y. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah y. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 0 (menyatakan y’), sedangkan kolom kedua dengan 1 (menyatakan y). Juga bisa kita lihat pada gambar 1.1.

0 1

	m₀	m₁	x 0	x’y’	x’y
	m₂	m₃	1	xy’	xy

Gambar 1.1

b. Peta Karnaugh dengan tiga peubah

Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 00 (menyatakan x’y’), kolom kedua diidentifikasi nilai 01 (menyatakan xy’), kolom ketiga diidentifikasi nilai 11 (menyatakan xy),sedangkan kolom keempat diidentifikasi nilai 10 (menyatakan xy’). Juga bisa kita lihat pada gambar 1.2.

					00	yz 01	11	10
m₀	m₁	m₃	m₂	x 0	x’y’z’	x’y’z	x’yz	x’yz’
m₄	m₅	m₇	m₆	1	xy’z’	xy’z	xyz	xyz’

Gambar 1.2

Perhatikan urutan dari mi-nya. Urutan disusun sedemikian rupa sehingga setiap dua kotak yang bertetangga hanya berbeda satu bit

Contoh: Diberikan fungsi Boolean dengan tiga buah peubah yang direpresentasikan dengan tabel kebenaran, gambarkan Peta Karnaugh.

X	y	Z	f(x, y, z)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Penyelesaian :

Tinjau hanya nilai fungsi yang memberikan 1. Fungsi Boolean yang merepresentasikan tabel kebenaran adalah f(x,y)=x’y’z + xy’z’ + xy’z +xyz. Tempatkan 1 di dalam kotak di peta Karnaugh untuk kombinasi nilai x dan y yang bersesuaian (dalam hal ini 001,100,101,dan 111).

	00	yz 01	11	10
x 0	0	0	0	1
1	0	0	1	1

c. Peta dengan empat peubah

Perhatikan urutan dari mi-nya pada Gamabr 1.3. Urutan disusun sedemikian rupa sehingga setiap dua kotak yang bertetangga hanya berbeda satu bit.

Gambar 1.3

Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh

Penggunaan Peta Karnaugh dalam penyederhanaan fungsi Boolean dilakukan dengan cara menggabungkan kotak yang bernilai 1 dan saling bersisian. Kelompok kotak yang bernilai 1 dapat membentuk pasangan (dua), kuad (empat), dan oktet (delapan).

1. Pasangan: dua buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	0	0	1	1
10	0	0	0	0

Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’

Hasil Penyederhanaan: f(w, x, y, z) = wxy

Bukti secara aljabar:

f(w, x, y, z) = wxyz + wxyz’

= wxy(z + z’)

= wxy(1)

= wxy

2. Kuad: empat buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	0	0	0	0

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’

Hasil penyederhanaan: f(w, x, y, z) = wx

Bukti secara aljabar:

f(w, x, y, z) = wxy’ + wxy

= wx(z’ + z)

= wx(1)

= wx

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	0	0	0	0

3. Oktet: delapan buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	1	1	1	1

Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ + wx’y’z’ + wx’y’z + wx’yz + wx’yz’

Hasil penyederhanaan: f(w, x, y, z) = w

Bukti secara aljabar:

f(w, x, y, z) = wy’ + wy

= w(y’ + y)

= w

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	1	1	1	1

Penggulungan

Ada kemungkinan kotak-kotak bernilai 1 terdapat di sisi pinggir yang berseberangan (sisi kiri dengan sisi kanan, sisi atas dengan sisi bawah). Kotak-kotak yang terletak pada sisi bersebrangan sebenarnya adalah kotak yang bertetangga juga. Seperti sebuah peta karnaugh itu adalah sebuah kertas yang ujungnya itu ditautkan dengan cara menggulung.

Contoh : Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’.

Jawab:

Peta Karnaugh untuk fungsi tersebut adalah:

	yz 00	01	11	10
x 0	0	0	1	0
1	1	0	1	1

Hasil penyederhanaan: f(x, y, z) = yz + xz’

Kelompok Berlebihan

Pengelompokan yang berlebihan (redundan) ini menghasilkan fungsi Boolean dengan term yang tidak perlu.

Contoh : Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini :

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	0	1	1	0
10	0	0	1	0

Jawab: f(w, x, y, z) = xy’z + wxz + wyz ® masih belum sederhana.

Penyelesaian yang lebih minimal:

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	0	1	1	0
10	0	0	1	0

f(w, x, y, z) = xy’z + wyz ===> lebih sederhana

Ketidakunikan Fungsi Hasil Penyederhanaan

Hasil penyederhanaan dengan peta Karnaugh tidak selalu unik. Artinya, mungkin terdapat beberapa bentuk fungsi minimasi yang berbeda meskipun jumlah literal dan jumlah term-nya sama.

	yz 00	01	11	10
wx 00	0	0	1	1
01	0	1	0	0
11	1	0	1	1
10	1	1	1	0

Fungsi minimasi: f(w,x,y,z)=w’x’y’ + w’xy’z + wy’z’ + wxy + wx’z

2.3 Peta Karnaugh untuk lima peubah

Peta Karnaugh untuk lima peubah dibuat dengan anggapan ada dua buah peta empat peubah yang disambungkan. Demikian juga untuk enam peubah dianggap ada dua buah peta empat peubah yang disambungkan . Setiap ‘sub-peta’ ditandai dengan garis ganda di tengah-tengahnya. Dua kotak dianggap bertetangga jika secara fisik berdekatan dan merupakan pencerminan terhadap garis ganda. Contoh :

000 001 011 010 110 111 101 100

00	m₀	m₁	m₃	m₂	m₆	m₇	m₅	m₄
01	m₈	m₉	m₁₁	m₁₀	m₁₄	m₁₅	m₁₃	m₁₂
11	m₂₄	m₂₅	m₂₇	m₂₆	m₃₀	m₃₁	m₂₉	m₂₈
10	m₁₆	m₁₇	m₁₉	m₁₈	m₂₂	m₂₃	m₂₁	m₂₀

Garis pencerminan

Contoh penggunaan Peta 5 peubah Carilah fungsi sederhana dari f(v, w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)

Jawab:

Peta Karnaugh dari fungsi tersebut adalah:

xyz

000 001 011 010 110 111 101 100

00	1	0	0	1	1	0	0	1
01	0	1	1	0	0	1	1	0
11	0	1	1	0	0	1	1	0
10	0	1	0	0	0	0	1	0

Fungsi minimasi: f(v,w,x,y,z) = wz + v’w’z’ + vy’z

2.4 Keadaan Don’t Care

Keadaan don’t care adalah kondisi dimana nilai peubah yang tidak diperhitungkan oleh fungsinya. Artinya nilai 1 atau 0 dari peubah don’t care tidak berpengaruh pada hasil fungsi tersebut.

Dalam menyederhanakan Peta Karnaugh yang mengandung keadaan don’t care, ada dua hal penting yang dijadikan pegangan. Pertama, kita anggap semua nilai don’t care (disimbolkan dengan X) sama dengan 1 dan kemudian membentuk kelompok sebesar mungkin yang melibatkan angka 1 termasuk tanda X tersebut. Kedua, semua nilai X yang tidak termasuk dalam kelompok tersebut kita anggap bernilai 0. Dengan cara ini, keadaan – keadaan X telah dimanfaatkan semaksimal mungkin; dan kita boleh melakukannya secara bebas sebab keadaan don’t care dapat diperlakukan sebagai 0 atau 1, terserah pada kita.

Contoh : Minimasi fungsi Boolean berikut (hasil penyederhanaan dalam bentuk baku SOP dan bentuk baku POS) :

f(w,x,y,z) = ∑ (1, 3, 7, 11, 15)

dengan kondisi don’t care adalah d(w,x,y,z) = ∑ (0, 2, 5)

Jawab :

Peta Karnaugh dari fungsi tersebut adalah :