6 - K-Map [PDF]

Citation preview

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 : 1.Mahasiswa dapat menerangkan dan memahami cara membuat k-map 2, 3, 4 variabel. 2.Mahasiswa dapat menerangkan dan memahami cara peng-cover-an minterm dalam sebuah k-map.. 3.Mahasiswa 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.



2



Karnaugh Map 2 Variabel : ( A dan B ) B Tabel Kebena ran Map



0 1 2



A 0 0 1



B 0 1 0



3



1



1



Value



0



A



A ’ B ’ B



0



A B ’ 2



Model II A 0



A’B’ 0



A’B 1



1



A’B



u e 1



AB’ 2



AB 3



3



Desain Pemetaan K- Map 2 Variabel A B



0



1 B’



0 1



B A’



4



A



Karnaugh Map 2 Variabel : dengan minterm-mintermnya



x



y



0



y 1



0 x’y’ x’y x 1 xy’ xy



5



F = Σ(m0,m1) = x’y + x’y’



xy 0 0



1



1 1



1



0



0



x 0



y 0



F 1



0



1



1



1 1



0 1



0 0



A



B



0 1



F=AB ′ 0 0 1 +A’B



A



B



01



0 0



1 F=AB +A′B +AB ′



1 1 1



1 1 0



AB



AB 01



F=AB ′ 0 0 1 +A’B 1 1 0



01



0 0



1 F=AB +A′B +AB ′



1 1 1 F=A+B



6



Contoh : 1 B Tabel Kebenaran Value



0 1 2 3



Map



A 0 0 1 1



B 0 1 0 1



Y 1 0 0 1



0



A



1



0 0



A’B’



0 2



1



0



1



3



1



B 0



A



AB



0



Jadi Y = A’B’ + AB



1



0



A’B’ 0



1



0 AB



1 2



7



1



3



Contoh : 2 B Tabel Kebenaran Value



0 1 2 3



Map



A 0 0 1 1



B 0 1 0 1



Y 1 1 0



0



A



1



1



0



1



0



A’B’



1



0



0



1



3



2



A’B



0



B 0



A 0



1



A’B’ A’B 1



0



Jadi Y = A’



0



0



1



3



2



8



Catatan untuk K-Map



A



0



1



2 Variabel



1



0



• 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 2 (1,



1



1



AB



A’B’ Y = AB + A’B’



n



A



2,4,8,16, ...)



0 1



1



1



1



1 B’



Y = B’ + A 9



0



A



Contoh 3: Dari Tabel Kebenaran dibawah, tulis persamaan logikanya dengan menggunakan K-map :



0 1 2



A 0 0 1



B 0 1 0



Y 1 1 0



3



1



1



1



Value



Map



A B 0 1



1



1 B’



1



1 B



A B 0



Jadi Y = A’ + B



0



1



A ’



A 1



0



1 1 1



B’



B 10



A’



A Jadi Y = A + B



Contoh 4 : Sederhanakan persamaan logika : Y = A + AB’ + A’B Menggunakan K- map :



0



A B



0



1



1 0



B’



1



1 A’



1 A



B



1 A’



1



1 1



11



Tabel Kebenara n Map Value



A B



0 1 2 3



0 0 0 0



0 0 1 1



4 5 6 C 7 0 1 0 1



1 1 1 1



0 0 1 1



0 1 0 1



A



B



Karnaug h Map 3 Variabel : (A ,B da n C)



Model I



BC



A



00



01



11



10



0



A’B’C’



A’B’C



A’BC



A’BC’



0



1



3



2



1



AB’C’



AB’C



ABC



ABC’



4



5



7



6



Model II



AB C



Map Value



0



00 A’B’C’



01 A’BC’



10 AB’C’



0



2



6



4



1



A’B’C



A’BC



ABC



AB’C



1



3



7



5



12



Tabel Kebenaran Map Value



ABC Y



0 0 0 0 1 0 0 1



Model III



2 3 4 5 6 7



0 0 1 1 1 1



1 1 0 0 1 1



Model IV AB 00 01 11 10



C



0



1



A’B’C’



A’B’C



0



1



A’BC’



A’BC



2



3



ABC’



ABC



6



7



AB’C’



AB’C



4



5



Map Value



A



0



1



A’B’C’



AB’C’



0



4



A’B’C



AB’C



1



5



A’BC



ABC



3



7



A’BC’



ABC’



2



6



13



Desain Pemetaan K- Map 3 Variabel C’ C A



BC



00



01



11



10



0



A’



1



A B’



14



B



Catatan untuk KMap 3 Variab el • • •



00



1 A



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 n



dilingkupi 2 (1, 2, 4,



8, ... )



01 11 10



1 1 Y = AB’C’ + A’BC + A’BC’



00



A 0 1 A BC 0 1 15



01



11



1 1 00



1 1



01



11



10



1 1



B



10



1 1



B’



Contoh pengcoveran C



AB



00



A 01



11



10



ab



0



c



C 1 B



cout = ab + bc + ac A



C



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



0



0



1



1



0



0



1



1



G(A,B,C) = A



B



ab c 00 01 11 10 0 0 0 1 1 10 0 1 f=a



A C



1



0



0



1



0



0



1



1



B 16



F(A,B,C) =



Σm(0,4,5,7)



= AC + B’C’



1



BC



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



+



A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1



C 0 1 0 1 0 1 0 1



F 0 1 1 0 1 1 1 1



F=AB’C’ +AB ′C +ABC +ABC ′ + A’B’C + A’BC’



BC A 00 01 11 10 00 1 0 1 1 1 1 1 1 F=A+B ′C +BC ′ F=AB’C’ +AB ′C +ABC +ABC ′ + A’B’C + A’BC’ 17



Contoh 1 :



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



1 1 0A 00 01 1 1 1



Diketahui Tabel Kebenaran seperti disamping : Cari persamaan logikanya : BC 00



1



01



11



10



1 1



A’B’



1



1



AB



AC Jadi Y = AC + AB + A’B’



18



Contoh 2 : Diketahui Persamaan Boolean :



D =



A’BC + A’BC’ + ABC’ + ABC + AB’C Sederhanakan dengan metode K-map



A



BC



00



01



0 1



1



11



10



1



1



1



AB’C A



BC



00



01



0 1



1 Jadi D = B + AC



19



1



11



10



1



1



AC



A’BC’ ABC’



ABC



1



A’BC



1



B



Karnaugh Map 4 Variabel : ( A, B, C dan D )



Tabel Kebenaran Map Valu e



A



B



C



D



0



0



0



0



0



1



0



0



0



CD AB



00 01 A’B’C’D’ A’B’C’D



11 A’B’CD



10 A’B’CD’



0



1



3



2



A’BC’D’



A’BC’D



A’BCD



A’BCD’



4



5



7



6



ABC’D



ABCD



ABCD’



13



15



14



AB’C’D



AB’CD



AB’CD’



9



11



10



00 01 A’B’C’D’ A’BC’D’



11 ABC’D’



10 AB’C’D’



0



4



12



8



A’BC’D



ABC’D



AB’C’D



5



13



9



A’BCD



ABCD



AB’CD



7



15



11



A’BCD’



ABCD’



AB’CD’



6



14



10



00



1



01



2



0



0



1



3



0



0



1



0 Model 1 1



4



0



1



0



0



5



0



1



0



1



6



0



1



1



0



7



0



1



1



1



8



1



0



0



0



9



1



0



0



1



10



1



0



1



11



1



0



1



A’B’C’D 0 01 1 1Model 2



12



1



1



0



0



13



1



1



0



1



14



1



1



1



0



15



1



1



1



1



11 ABC’D’ 12



10 AB’C’D’ 8



AB CD 00



11 A’B’CD 3



10 A’B’CD’ 2



20



Dengan wxyz input



21



Desain Pemetaan K- Map 4 Variabel A’



AB CD



00



01



11



00



C’



01



D’



D 11 C



10 B B’ 22



Catata n untuk K-Map 4V a ri a b e l •



•



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 n 2 ( 1,2, 4, 8, 16, ... )



AB CD 00 01 11 10



00 01



10 CD



AB



00 01 11



1 1 1 1



1 1 1 1



1 1 1



1



00



01



11



10



1 1 1 1



ABCD’



AC’ A’



1 1



10 A’BCD



1 1



23



ACD’



B’C’



:



Contoh pengcoveran A



A



0



0



0



0



1



0



0



0



1



1



0



1



1



1



0



0



C



D C



B



K-map untuk LT



24



A



1



0



0



0



0



1



0



0



0



0



1



0



0



0



0



1



D C



0



1



1



1



0



0



1



1



0



0



0



0



0



0



1



0



B



B



K-map untuk EQ



K-map untuk GT



LT =



A' B' D + A' C + B' C D



EQ =



A'B'C'D' + A'BC'D + ABCD + AB'CD’



GT =



B C' D' + A C' + A B D'



D



Contoh pengcoveran CD AB 00 01 11



0 1 1 10 1 00 01 11



0 1 1 0



0 0 1 1



:



F= A′BC ′+A ′CD ′+ABC +AB ′C′D ′ +ABC ′ +AB ′C



F=BC ′+CD ′+ AC+ AD ′



25



Contoh 1 • F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15) F= C + A’BD + B’D’ A



C



1



0



0



1



0



1



0



0



1



1



1 1



1 1



1



1



0111



D



CD 0000



1000



B



Kalau digambarkan dengan system coordinate



26



1111



Contoh 2 : Diketahui Tabel Kebenaran , cari persamaan logikanya.



CD



AB



00



01



A B



C



D



11



1



0



Map Value



A 10



Y



1



1



0



0 0



0



0



0



1



0 0



0



1



0



2 3 4 5



0 0 0 0



0 0 1 1



1 1 0 0



0 1 0 1



1 1 0 0



6 7 8



0 1 0 1 1 0



1 1 0



0 1 0



1 1 0



9



1 0



0



1



1



10



1 0



1



0



0



11



11



1 0



1



1



1



12 13



1 1 1 1



0 0



0 1



1 0



C 10



14



1 1



1



0



0



15



1 1



1



1



0



C



11



3



10



2



AB



1 1



1 1



1 A



00



01



D



11



B 10



1



CD 00



ABC’D’



01



1 1 1



A’C Jadi Y = A’C + AB’D + ABC’D’



1 1



D



AB’D B 27



YZ 00



WX 00



W 01



11



1



1



1



1 1 1



01



Y



11



10



1



10



Contoh 3 : Lingkarilah dan Tulis Persamaan Logikanya.



Z



1 X



WXZ’ YZ



01



11



1



W’X’Y’Z’ YZ



WX 00



W



1



01 Y



11



1



1



1



10



1 1



Z



1 Y



Jadi M = W’X’Y’Z’ + WXZ’ + WXX’Z + YZ 28



10



WX’Z



Physical Implementasi A



B C



° Step 1: Truth table



D



EQ



° Step 2: K-map ° Step 3: Minimized sum-ofproducts ° Step 4: Implementasi dengan gates A



C



1



0



0



0



0



1



0



0



0



1



0



0



0



0 0



B



1



D



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. 30



• Tulis persamaan logika hasil pengcoveran.



Don’t Care • Kondisi don’t 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 don’t 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.



31



Karnaugh maps: don’t cares (cont’d) • 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 = A’D + C’D dengan don't cares



+



A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 +



B C D 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1



f 0 1 0 1 0 1 X 1 0 1 0 0 X X 0 0



A



C



0



0



X



0



1



1



X



1



1



1



0



0



0



X



0



0



D



B



32



Pengcoveran dengan Don’t Cares CD 00 AB 00 01 11 10



33



0 x 1 x



01



11



10



1 x 1 0



0 x 1 1



0 1 x 1



F=A′C′D+B+AC



Bentuk ilustrasi pengkoveran A



C



0



X



1



0



1



1



1



0



1



0



1



1



0



0



1



1



B



6 prime implicants: A'B'D, BC', AC, A'C'D, AB, B'CD D



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 minimum cover: 4 essential implicants minimum cover: ABC’+ACD+A’BC+A’C’D



C



0



0



1



0



1



1



1



0



0



1



1



1



0



1



0



0



B



D



34



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout



+



A 0 0 0 0 1 1 1



B 0 0 1 1 0 0 1



Cin 0 1 0 1 0 1 0



1



1 1



S 0 1 1 0 1 0 0



Cout 0 0 0 1 0 1 1



1



1



Metode Aljabar Boole



S = A’B’Cin + A’BCin’ + A’BCin + ABCin Cout = A’BCin + A B’Cin + ABCin’ + ABCin = = = = 35



A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB 1·BCin + 1· ACin + 1· AB BCin + ACin + AB



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A 0 B



0



0 1



1 1



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



0 1



Cin Karnaugh Map for Cout 36



A 0 0 0 0 1 1 1 1



Pengisiaan digit 1 ke K-map



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A



B



0



0



1 0



0



1



1 1



A 0 0 0 0 1 1 1 1



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



Pengcoveran pertama.



Cin Karnaugh Map untuk Cout



Cout = ACin



Cout 0 0 0 1 0 1 1 1



37



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A 0 B



0



0 1



1 1



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



0 1



Cin Karnaugh Map for Cout 38



A 0 0 0 0 1 1 1 1



Pengcoveran kedua.



Cout = Acin + AB



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A



B



0



0



0



1



A 0 0 0 0 1 1 1 1



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



1 0



Pengcoveran ketiga 1 1 (seluruhnya)



Cin Karnaugh Map untuk Cout



Cout = ACin + AB + BCin



Cout 0 0 0 1 0 1 1 1



39



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A



B



0



1



0 1



1



0



1 0 Cin



Karnaugh Map untuk S 40



A 0 0 0 0 1 1 1 1



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



S = A’B Cin’



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A



B



0



1



0 1



1



0



1 0 Cin



Karnaugh Map untuk S 41



A 0 0 0 0 1 1 1 1



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



S = A’BCin’ + A’B ’Cin



Aplikasi K-map Pada Rangkaian Full Adder Cin A



Adder



S



B Cout A



B



0



1



0 1



1



0



1 0 Cin



Karnaugh Map untuk S 42



A 0 0 0 0 1 1 1 1



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



S = A’B Cin’ + A’B’Cin + ABCin



Aplikasi K-map Pada Rangkaian Full Adder Coba anda gambar rangkaian diagramnya ? Cin



A



Adder



B



S



Cout



B



A



0



1



0 1



1



0



1 0



Cin Karnaugh untuk S 43



A 0 0 0 0 1 1 1



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



1



Cout 0 0 0 1 0 1 1 1



S = A’BCin’ + A’B’Cin + ABCin + AB’Cin’ Tidak bisa direduksi



Latihan Soal 1:



Gambarlah K-map untuk setiap ekspresi logika dibawah serta sederhanakan dengan pengcoveran yang benar :



1. 2. 3. 4.



44



AB + B’C + A’B’ AC + AC’B + BC + B’C’ XY + X’Z + Y’Z’ XY +YZ + XZ +X’Y’



Latihan Soal 2 : Gambarlah K-map untuk setiap ekspresi logika dibawah serta sederhanakan dengan pengcoveran yang benar :



1. A(BC’ + C) + B(A + A’C) 2. (AC + AC’B). (BC + B’C’) 3. Z(XY + X’Z) . Y’Z’(X+ Z) Catatan : cari minterm-mintermnya dulu (rubah kebentuk SOP)



45