pertemuan 4: inf203 (3 sks) penyederhanaan persamaan...

Penyederhanaan

Persamaan Logika

Oleh Wayan Suparta, PhD

Prodi Informatika

Universitas Pembangunan Jaya

Pertemuan 4: INF203 (3 SKS)

Sub Pokok Bahasan: 1. Konsep Penyederhanan

2. Metode-Metode Penyederhaaan

Peta Karnaugh (K-Map)

Implicant

Kondisi Don’t Care

Capaian Pembelajaran Mahasiswa mampu menyederhanakan persamaan logika

menggunakan Karnaugh Map (K-Map).

Mahasiswa mampu menyederhanakan rangkaian digital pada

gate level dengan metode tabulasi.

• Tahap minimalisasi rangkaian logika diperlukan agar

diperoleh rangkaian dengan fungsi yang sama namun

menggunakan gerbang yang paling sedikit.

• Rangkaian dengan jumlah gerbang yang paling

sedikit akan lebih murah harganya, dan dari segi tata

letak komponennya akan lebih sederhana.

• Selain harga murah konsumsi daya yang diperlukan

juga rendah sehingga sistem dapat bekerja lebih

cepat.

• Cara penyederhanaan dapat dilakukan dengan Aljabar

Boole dan Peta Karnaugh (K-Maps).

Konsep Penyederhanaan

Penyederhanaan dengan Aljabar Boole

Sederhanakan rangkaian berikut:

Penyelesaian:

Y = (A+B) BC + A

Metode-Metode Penyederhanaan

1. Metode Peta Karnaugh (K-Map)

• Metode Aljabar Boole masih tetap diperlukan namun belum dapat menentukan rangkaian yang paling minimal.

• Metode peta karnaugh memberikan suatu prosedur yang mudah dan langsung dalam proses penyederhanaan fungsi Boole. Metode pemetaan itu awalnya diusulkan oleh EdwardVeitch 1952, lalu dimodifikasi oleh Karnaugh. Itulah alasannya namanya dikenal sebagai diagram Veitch atau Peta Karnaugh (K-Map).

Pembentukan K-Map

Memetakan tabel kebenaran dalam kotak segi empat yang

jumlahnya tergantung jumlah variabel masukan

Penyederhanaan untuk setiap “1” yang bersebelahan 2,4,8,16…

menjadi suku minterm sederhana.

Contoh:

K-Map untuk 3 Variabel

Perhatikan: Nilai “11” tidak

berada di kolom

paling kanan

Gabungkan dengan

memberi lingkaran

pada minternnya

dengan nilai

terdekat 2n.

Hasilnya:

Y = AB+C

Kaitan dengan Mintern

Contoh 2 Tuangkanlah persamaan berikut ke dalam peta karnaugh:

FABC = m (0, 1, 2, 4, 6)

Penyelesaian:

2

1

Hasil penggabungan:

Y = A’ + C’

B’C’ B’C BC BC’ B’C’ B’C BC BC’

A’

A

A’

A

K-Map dengan 4 variabel Perhatikan peletakan suku mintern.

mo m4 m12 m8

m1 m5 m13 m9

m2 m6 m15 m11

m3 m7 m14 m10

mo m1 m3 m2

m4 m5 m7 m6

m12 m13 m15 m14

m8 m9 m11 m10

00 01 11 10

00 0 1 3 2

01 4 5 7 6

11 12 13 15 14

10 8 9 11 10

CD AB

Contoh K-Map 4 variabel

K-Map yz

wx

Penyelesaian: yz

wx w’yz’

w’xy

xyz’

w’x’y’z

Jadi, f = w’yz’ + w’xy + xyz’ + w’x’y’z

f = w’y (z’+x) + xyz’ + w’x’y’z

K-Map dengan 5 variabel

atau

Contoh: f = m (0, 7, 8, 15, 16, 23, 24)

2. Metode Tabulasi (Implicant)

Metode Tabulasi (Quine McCluskey)

Metode tabulasi dapat mengatasi jumlah variable yang besar.

Metode tabulasi dirumuskan oleh Quine dan kemudian

diperbaiki oleh McCluskey, sehingga metode ini dikenal dengan

metode Quine McCluskey.

Metode penyederhanaan dengan tabulasi terdiri dari dua

bagian, yaitu :

1. Penentuan Prime Implicant

Mencari semua suku (term) yang merupakan calon untuk

dicantumkan dalam fungsi yang disederhanakan itu. Suku

tersebut dinamakan prime implicant.

2. Pemilihan Prime Implicant

Memilih diantara semua suku prime implicant yang tersedia itu

yang akan memberikan pernyataan yang paling sederhana.

Penentuan Penyusun Utama

• langkah pertama yang harus dilaksanakan adalah mengelompokkan semua sukumin berdasarkan cacah bit 1

• Penyederhanaan dilakukan dengan penggabungan sukumin yang berbeda 1 bit dari tiap kelompok.

Penentuan Penyusun Utama

• Contoh 1: f = m(0,2,3,4,8,10,11,12,13,15)

Penentuan Penyusun Utama Dengan tabel disederhanakan

penggabungan bit dengan jarak 2^n

» Contoh 2: f = m (1,4,6,7,8,9,10,11,15)

Penyusun Utama Inti

Dilakukan dengan mengambil penyusun utama yang mencakup

semua sukumin yang ada

Untuk Contoh 1 di atas

Penyusun Utama Inti

Untuk Contoh 2 di atas

• Untuk fungsi tidak lengkap, dengan sukumin

don’tcare, tetap dilakukan penentun penyusun

utama dengan menganggap d=1.

• Akan tetapi pada saat penentuan penyusun

utama inti, sukumin d tidak diikutkan.

• Contoh :

f(v,w,x,y) = m (2,3,7,9,11,13) + d (1,10,15)

KONDISI DON’T CARE

Fungsi Tidak Lengkap

LATIHAN 4

1. Diketahui: g = M(1,3,4,5,6,7,9,11,13,15)

(a). Realisasikan dalam K-Map

(b). Carilah persamaan sederhananya

(c). Gambarkan rangkaian digitalnya

2. Diketahui persamaan: Y = AC+BC’ + AB’C

(a). Realisasikan dalam K-Map

(b). Carilah persamaan sederhananya

(c). Gambarkan rangkaian digitalnya

3. Buatlah tabel Peta Karnaugh (K-Map) untuk 6

perubah. Tentukan juga Maxnternnya.

4. Sederhanakan fungsi Bolean berikut dengan K-Map

dan Aljabar Boole:

f(x, y, z) = x’z + x’y + xy’z + yz

5. Sederhanakan K-Map berikut:

(a). (b).

Rancanglah rangkaian digitalnya.

6. Sederhanakan fungsi berikut dengan menggunakan

metode tabulasi.

f(w,x,y,z) = ∑(1,4,6,7,8,9,10,11,15)

7. Sederhanakan persamaan berikut dengan

menggunakan peta karnaugh.

f(a,b,c,d) = m (0,1,4,5,11,13,15) + (2,7,9,12,14),

dimana menyatakan minterm yang bernilai don’t

care. Rancanglah rangkaian digitalnya.

8. Sederhanakan persamaan Product of Sum berikut

dengan menggunakan metode Quine McCluskey

F(W,X,Y,Z) = ΠM (2,7,9) • (3,6,8,10)

Rancanglah rangkaian digitalnya.