Bab_6_k-map.pdf

BAB 6 KARAUGH MAP (K-MAP)

6.1 Pendahuluan Salah satu cara dalam penyerdehanaan persamaan aljabar Boolean adalah K-Map. Dalam bab ini akan kita pelajari cara membangun suatu K-Map .

6.2 Penyajian 6.2.1 Varibel K-Map K-Map Dua Variabel Andaikan kita memiliki tabel kebenaran seperti dalam tabel 6.1, berikut ini ditunjukkan cara menyusun K-Map untuk tabel tersebut. Dimulai dengan melukis gambar 6-1, Lajur(kolom) vertikal terdiri dari B’ dan B, sedangkan baris horizontal diisi dengan A’ dan A. Kemudian, carilah keluaran bernilai 1 dalam tabel 6.1. Keluaran 1 yang pertama bersesuain dengan masukan A=1 dan B=0. Hasil kali fundamental dari keadaan ini adalah AB’. Hal yang sama diperoleh pada saat A=1 dan B= 1. Hasil kali fundamentalnya adalah AB. Selanjutnya angka 1 dituliskan pada kotak yang sesuai dengan hasil kali fundamentalnya, dan sisanya diisi dengan angka 0, maka diperoleh

K-Map

seperti gambar 6.2. Berikutnya kita lihat contoh lain dari K-Map 2 Variabel. Dari tabel kebenaran 6.2 terbaca bahwa hasil kali fundamental yang terdapat disini adalah A’B dan AB’. Bila kita tuliskan angka 1 untuk hasil kali tesebut dan angka 0 ditempat-tempat sisanya, maka diperoleh K-Map seperti gambar 6.3.

T

a

b

e

l

6

.

1

6

.

2

A

B

0

Y

0

0

0

1

1

0

0

1

1

1

T

a

b

e

1

6

l

A

.

2

B

0

Y

0

0

0

1

1

1

0

1

1

1

0

B'

B

A' A G

a

m

b

a

r

6

.

1

K

-

M

a

2

p

B' A' A G

a

m

b

a

r

6

.

2

G

a

m

b

a

r

6

.

3

M

a

p

b

e

l

c

o

n

t

o

1

h

0

1

-

a

B

0

K

i

1

B' A' A

r

0

0

-

a

B

1

K

V

M

1

a

p

c

o

n

t

o

h

2

K-Map Tiga Variabel Misalkan kita mempunyai tabel kebenaran seperti tabel 6.3. Maka mulailah dengan melukiskan gambar 6.4. Lajur baris horisontal ditandai dengan A’B’, A’B, AB dan AB’, kolom ditandai dengan C’D’, C’D, CD, dan CD’ seperti yang diberikan Gambar 6.4. Selanjutnya, carilah keluaran 1 dalam tabel 6.3 dan diperoleh hasil kali fundamental untuk tersebut, yaitu : A’BC’, ABC’ dan ABC. Selanjutnya tuliskan angka 1 pada K-Map ditempat-tempat yang sesuai dengan

6

.

3

hasil kali fundamental, dan sisanya diisi dengan angkah 0, maka diperoleh K-Map seperti Gambar 6.5. T

a

b

e

6

l

A

.

3

B

0

0

0

0

C

1

0

1

0

0

0

1

0

0

1

0

1

1

1

0

0

0

1

1

1

1

1

0

0

1

1

1

C' A'B' A'B AB AB' G

a

m

b

a

r

6

.

4

K

C

0

0

1

-

M

a

p

3

v

C' A'B' A'B AB AB' G

a

m

b

a

r

6

.

5

K

Y

0

i

a

b

e

l

0

1

0

1

1

0

M

r

C

0

-

a

0

a

p

k

a

s

u

s

d

a

l

a

m

T

a

b

e

l

5

.

3

K-Map Empat Variabel Contoh penyusunan K-Map empat-variabel akan dijabarkan berikut ini. Perhatikan Tabel 6.4. Langkah pertama, buat K-Map kosong seperti nampak pada gambar 6.6. Baris horison diberi tanda A’B’, A’B, AB, dan AB’, sedangkan kolom ditandai dengan C’D’, C’D, CD, dan CD’. Dalam Tabel 5.4, keluarankeluaran bernilai 1 memberikan hasil kali fundamental : A’B’C’D, A’BCD’, A’BCD, dan ABCD’. Setelah mengisikan angka 1 sesuai dengan hasil kali

6

.

4

fundamentalnya pada K-Map dan angka 0 pada sisanya, diperoleh K=Map seperti Gambar 6.6. T

a

b

e

6

l

A

.

8

B

C

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

1

0

1

0

0

1

0

1

0

0

0

1

0

0

1

0

0

0

1

1

1

0

1

1

Y 0

1

1

0

0

D 0

1

1

1

0

0

1

1

1

1

1

0

1

1

0

1

1

1

1

1

1

0

0

0

1

0

0

0

1

0

0

1

1

0

C'D' C'D CD CD' A'B' A'B AB AB' G

a

m

b

a

6

r

.

6

K

-

M

a

4

p

v

a

r

i

a

b

e

l

C'D' C'D CD CD' A'B' A'B AB AB' G

a

m

b

a

r

6

.

7

K

0

-

M

1

0

0

0

0

0

0

0

0

0

a

p

k

a

0

1

s

u

s

d

a

1

1

0

l

a

m

T

a

b

e

l

6

.

8

6

.

5

6.2.2 Pasangan , Dual, Kuad dan Oktet Fungsi uatama K-Map adalah digunakan dalam penyedehanaan rangkaian logika. Tetapi sebelum kita memahami bagaimana ini dilakukan, perlu di pelajari dahulu pengertian tentang pasangan, kuad, ( kelompok berempat ) dan oktet ( kelompok ber delapan ).

Dual Dalam K-Map jumlah angka 1 boleh digabung membentuk pasangan, berdua (dual), berempat (kuad), dan berdelapan (oktet). Gabungan diperbolehkan baik ke arah vertikal, maupun ke arah horisontal. Pasangan dari gambar 6.8, angka 1 pertama menyatakan perkalian ABCD, ABCD.

yang kedua mewakili perkakilan

Selanjutnya pasangan tersebut ditandai dengan kotak membentuk

pasangan dual. Hal sama, kotak A’B’C’D’ bergabung dengan kotak A’B’CD’ membentuk pasangan dual. Pasangan dari gambar 6.9, semua angka satu pada kotak baris pertama membentuk pasangan kuad, demikian juga angka 1 pada kotak ABC’D, ABCD, AB’C’D, dan AB’CD membentuk kuad ke dua. Gambar 6.10 memperlihatkan pasangan oktet, yang dibentuk dari semua angka angka 1 pada baris pertama dan baris ke empat. Oktet ke dua dibentuk dari semua angka 1 pada kolom 3 dan kolom 4. C

A

A

'

B

'

B

'

'

D

'

C

1

'

D

C

0

0

0

0

0

0

0

0

0

D

C

D

'

1

0

1

A

A

B

B

'

G

a

m

b

1

0

a

r

6

.

0

8

6

.

6

C

'

D

'

C

'

D

C

D

C

D

'

D

'

1

A

A

'

B

'

B

'

1

0

1

0

1

0

0

1

A

A

B

0

B

'

0

1

G

C

A

'

B

'

B

'

a

'

m

D

b

a

'

C

1

6

r

'

.

1

0

1

0

9

D

C

1

D

1

C

1

1

A

A

B

0

0

0

0

1

1

1

1

1

1

A

B

'

1

G

a

m

b

a

r

6

.

1

0

Perhatikan Gambar 6.8, pasangan dual, terdapat variabel yang berubah ( dari D ke D’), sementara variabel lain yang lain tidak mengalami perubahan bentuk ( A, B, dan C tetap seperti semula ). Bila mana hal ini terjadi, kita dapat menghapus variabel yang berubah tersebut sehingga hasil kalinya ABC. Secara aljabar hal ini dapat dibuktikan. Persamaan jumlah hasil kali yang bersesuaian dengan pasangan dual pada gambar 5.8 adalah : Y = ABCD + ABCD’ Faktorisasi menghasilkan: Y = ABC ( D+D’ )

Sesuai dengan hukum aljabar boolean , D+D’=1, maka persama di atas dapat direduksi menjadi: Y = ABC

Untuk memudahkan indentifikasi biasanya pasangan angka 1 yang berdekatan di beri tanda kotak atau lingkaran , sebagaimana tampak dalam gambar 6.8. Dengan cara ini , dengan mudah kita mengenali adanya variabel dan komplemennya yang dapat dihilangkan.

6

.

7

Pasangan lain adalah pasangan dari kotak A’B’C’D’ dengan A’B’CD’ membentuk pasangan dual secara vertikal. Dalam pasangan tersebut variabel C berubah ke komplemennya (C ke C’) sementara variabel lain A’, B’, dan D’ tidak berubah. Karena itu, C dan C’ dapat ditanggalkan, dan pasangan dual pada Gambar 6.8 menyatakan hasil kali A’B’D’. Jika dalam sebuah K-Map terdapat lebih dari satu pasangan, kita dapat melakukan operasi OR pada hasil kali yang telah disederhanakan itu untuk memperoleh persamaan Boole yang bersangkutan. Misalnya, dalam gambar 6.8, terdapat 2 pasangan dengan hasil kali adalah ABC dan A’B’D’. Persamaan Boole yang bersangkutan untuk K-Map ini adalah:

Y = ABC + A’B’D’

Kuad ( Quad ) Kuad adalah kelompok yang terdiri dari empat buah angka 1 yang tersusun berdampingan dari ujung ke ujung atau kelompok yang membentuk susunan segi empat seperti pada Gambar 6.9. Adanya sebuah pasangan kuad berarti terhapusnya dua variabel beserta komplemennya dari persamaan Boole yang bersangkutan. Hal ini dapat dijelaskan sebagai berikut. Bayangkan empat buah angka 1 dari gambar 6.9 sebagai gabungan dua pasangan dual . Pasangan pertama memiliki A’B’C’, dan pasangan kedua memiliki A’B’C. Persamaan Boole bagi kedua pasangan ini adalah : Y = A’B’C’ + A’B’C Faktorisasi persamaan tersebut menghasilkan Y = A’B’ ( C’+C ) Sehingga diperoleh bentuk lebih sederhana Y = A’B’ Jelaskan bahwa Kuad pada baris pertama Gambar 6.9 mengungkapkan sebuah hasil kali yang telah disederhanakan

dengan terhapusnya dua variabel dan

komplomenya. 6

.

8

Oktet Oktet adalah kelompok dari delapan angka 1 yang berdampingan seperti tampak dalam gambar 6.10. Sebuah oktet selalu berarti penghapusan tiga buah variabel

dan komplomen-komplomennya dari persamaan Boolean

yang

bersangkutan. Untuk lebih jelas, kita ikuti uraian berikut. Pandanglah oktet pada gambar 6.10 sebagai dua buah kuad. Persamaan untuk kedua kuad ini adalah Y = A’B’ + AB’ Faktorisasi menghasilkan Y = B’ ( A + A’ ) Tetapi ini tak lain adalah Y =B’

Jadi, adanya oktet pada gambar 5.10 berarti bahwa tiga buah variabel dan komplomen-komplomennya akan terhapus dari hasil kali yang bersangkutan. Pembuktian serupa berlaku pula untuk bentuk-bentuk oktet yang lain. Selanjutnya, kita tidak akan dipusingkan kerumitan aljabar tersebut. Langkah yang dibutuhkan hanyalah penentuan angka 1 dari oktet dan mencari tiga buah variabel yang mengalami perubahan bentuk. Variabel-variabel inilah yang akan terhapuskan dari persamaan.

6.2.3 Penyederhanaan K-Map Telah dijelaskan bagaimana sebuah angka 1, sebuah Dual, kuad, dan sebuah oktet, masing-masing dapat menghapuskan satu, dua, dan tiga variabel. Berdasarkan alasan ini, dalam rangka penyederhanaan persamaan Boole, kita harus melakukan identifikasi mulai dengan melingkari oktet, kemudian kuad, dan akhirnya pasangan angka-angka 1. Melalui langkah demikian, penyederhanaan yang maksimum dapat dicapai.

6

.

9

Contoh : Andaikan anda telah menerjemahkan suatu tabel keluaran ke dalam K-Map yang di tunjukkan gambar 5-11. Pertama, carilah oktet dalam K-Map tersebut. Ternyata tidak ada oktet di dalam K-Map. Kemudian, carilah kuad. Anda akan menjumpai dua buah kuad. Dan akhirnya, carilah pasangan angka 1, dan kita akan menemukan sebuah pasangan tersebut.

C'D' C'D CD CD' A'B' 0 1 1 1 A'B 0 0 0 1 AB 1 1 0 1 AB' 1 1 0 1 Gambar 5.11 Pasangan tersebut mewakili perkalian yang telah disedehanakan A’B’D, kuad bagian bawah menyatakan hasil kali AC’, dan kuad disebelah kanan merupakan representasi perkalian CD’. Pelakasanaan operasi OR antara hasil kali yang telah disederhanakan ini, akan menghasilkan persamaan Boolean seperti berikut.

Y = A’B’D + AC’ + CD’

Kelompok yang bertumpang-tindih (overlapping) Bila

kita

melingkari

kelompok-kelompok

dalam

K-Map

,

kita

diperbolehkan memakai angka 1 tertentu lebih dari sekali. Gambar 6.12 menjelasakan pernyataan ini.

C'D' C'D CD CD' A'B' 0 0 0 0 A'B 0 1 0 0 AB 1 1 1 1 AB' 1 1 1 1

6

.

1

0

Gambar 6.12 Persamaan yang telah disederhanakan maing-masing dual dengan hasil kali BC’D dan oktet dengan hasil kali A. Kedua hasil kali ini kemudian dijumlahkan dan menghasilkan keluaran seperti berikut.

Y=A+BCD

6.2.4 Penyelesaian Soal

Contoh 1. Sederhanakan dengan K-Map kasus yang diberikan pada Tabel benaran di bawah ini : Tabel 6.9 A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

Y 1 1 1 0 0 0 1 0

Langkah pertama adalah menterjemahkan tabel ke dalam K-Map. Di sini terdapat 4 angka 1 (A’B’C’, A’B’C, A’BC’ dan ABC’). Jika keempat kondisi ini dimasukkan dalam K-Map, diperoleh hasil seperti yang diberikan gambar 6.13.

C' C A'B' 1 1 A'B 1 0 AB 1 0 AB' 0 0

6

.

1

1

Gambar 6.13 Hasil akhir diperoleh : Dual 1 dengan hasil kali A’B’ dan dual 2 dengan hasil kali AC’, sehingga persamaan keluaran Tabel 6.9 adalah : Y = A’B’ + AC’ Kembali ke Tabel 5.9, jika diselesaikan secara Aljabar Boolean diperoleh : Y = (A’B’C’ + A’B’C + A’BC’ +ABC’) Disederhanakan menjadi : Y = A’B’(C’+C) + BC’(A’+A) Y = A’B’+BC’ Contoh 2 Sederhanakan dengan K-Map kasus yang diberikan pada Tabel benaran di bawah ini : Tabel 5.10 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

Y 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1

Pada kasus ini, juga terdapat 4 angka 1 (A’B’C’D, A’BC’D, ABC’D dan ABCD). Jika keempat kondisi ini dimasukkan dalam K-Map, diperoleh hasil seperti yang diberikan gambar 6.14.

6

.

1

2

C

'

D

'

C

'

D

C

D

C

D

'

1

'

A

B

'

A

B

B

A

A

'

B

'

0

0

0

1

0

1

0

0

a

m

b

0

1

0

G

0

0

0

a

r

6

.

0

1

4

Hasil akhir diperoleh : Dual 1 dengan hasil kali A’C’D dan dual 2 dengan hasil kali ABD, sehingga persamaan keluaran Tabel 6.9 adalah : Y = A’C’D +ABD Kembali ke Tabel 5.10, jika diselesaikan secara Aljabar Boolean diperoleh : Y = A’B’C’D + A’BC’D + ABC’D + ABCD Disederhanakan menjadi : Y = A’C’D(B’+ B) + ABD(C’+C) Y = A’C’D +ABD

6.3 Penutup 6.3.1 Kesimpulan 1. Dari uraian di atas, dapat disimpulkan bahwa suatu persolan logika yang rumit dapat disederhanakan dengan mudah melalui K-Map 2. K-Map adalah salah satu tool untuk penyederhanaan aljabar logika

6.3.2 Soal-soal 1. Sebuah tabel benaran dengan 4 variabel input satu keluaran. Delapan keadaan masukan pertama menghasilkan keluaran 0 dan delapan keadaan masukan terakhir menghasilkan keluaran 1. Buat K-Map dari tabel benaran tersebut. 2. Lukiskan K-Map untuk keluaran Y1 dan Y0 tabel benaran di bawah ini. Tabel 6.12

6

.

1

3

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

Y1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 1

Y0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1

3. Buat persamaan logika dari K-Map di bawah ini : C

'

A

B

'

A

'

D

'

C

'

1

B

0

B

A

0

B

A

'

'

D

C

D

1

0

0

1

0

0

1

0

C

1

0

D

'

D

'

D

'

0

0

1

(

a

C

'

A

B

'

A

'

'

B

B

A

'

C

1

'

D

C

1

1

1

1

C

1

1

'

D

1

0

B

A

D

)

1

0

0

1

0

0

0

(

b

C

'

A

B

'

A

B

B

A

A

'

B

'

'

D

'

C

'

D

)

C

D

1

1

0

1

1

0

1

1

1

1

1

0

1

0

C

0

1

6

.

1

4

(

c

C

'

A

B

'

A

'

B

'

C

'

D

C

1

0

D

1

'

D

'

1

1

0

D

0

1

1

'

C

0

0

0

B

A

D

1

B

A

'

)

0

0

1

(

d

C

'

A

B

'

A

'

B

B

A

A

'

B

'

0

D

'

C

'

)

D

C

D

0

C

1

1

1

1

1

1

1

1

1

1

0

0

0

1

(

e

)

4. Bual rangkaian logika dari hasil penyederhanaan keluaran Y1 dan Y0 dari Tabel 6.12 5. Buat rangkaian logi dari hasil penyederhanaan K-Map dari aoal N0.3

-----

6

.

1

5