41 V2 Karnaugh Map.pdf

Karnaugh Map + BCD, Don’t Care, Minterm, Maxterm Quine-McCluskey Method

Karnaugh Map  Sebuah peta Karnaugh menyediakan metoda sistematik untuk penyederhanaan ekspresi Boolean  jika tepat digunakan akan menghasilkan ekspresi SOP atau POS yang paling sederhana, yang disebut ekspresi minimum.  Peta Karnaugh, tidak seperti penyederhanaan sebelumnya yang menggunakan hokum, aturan dan teorema aljabar Boolean, sebaliknya, menyediakan sebuah metoda “cookbook” untuk penyederhanaan.  teknik penyederhanaan yang lain seperti metoda Quine-McCluskey dan algoritma Espresso.

 Karnaugh map di-arrange dalam sebuah array of cells, dimana setiap cell merepresentasikan sebuah nilai biner dari variable masukan.  Karnaugh map dapat digunakan untuk ekspresi dengan 2,3,4,5 variabel.  Jumlah sel pada peta Karnaugh sejumlah total jumlah kemungkinan kombinasi variabel masukan.  Untuk 3 variabel, jumlah sel adalah 23 = 8;  untuk 4 variabel, jumlah sel adalah 24 = 16.

Peta Karnaugh 3 variable  Berikut peta Karnaugh 3 variabel yaitu A, B, dan C (huruf lain bisa juga digunakan)

Peta Karnaugh 4 variabel  Peta ini adalah sebuah array dari 16 sel, seperti di gambar.

Cell Adjacency (Kedekatan sel)  Sel-sel pada peta Karnaugh di-arrange supaya hanya ada sebuah variabel tunggal berubah antara sel yang berdekatan.  Adjacency didefinisikan oleh sebuah perubahan single-variable.  Pada peta 3-variabel, sel 010 berdekatan dengan sel 000, sel 011 dan sel 110.  Namun sel 010 tidak berdekatan dengan sel 001, sel 111, sel 100 atau sel 101. Secara fisik, setiap sel adalah berdekatan dengan sel yang bersebelahan langsung dengan sel tersebut (dari salah satu sisi dari 4 sisi sel).  Namun sebuah sel tidak berdekatan ke sel yang secara diagonal bersentuhan dengan salah satu sudutnya.

 Juga sel di baris paling atas adalah berdekatan dengan sel yang bersesuaian dengan baris paling bawah dan sel di kolom kiri terluar berdekatan dengan sel yang bersesuaian di kolom kanan terluar. Ini disebut dekat “wrap-arround” adjacency karena kita dapat membayangkan bahwa peta diwrapping arround dari atas ke bawa untuk membentuk silinder atau dari kiri ke kanan untuk membentuk silinder.

Minimalisasi SOP Karnaugh Map  Peta Karnaugh digunakan untuk menyerderhanakan ekspresi Boolean ke bentuk minimumnya. Ekspresi SOP yang diminimalkan berisi beberapa kemungkinan term dengan beberapa kemungkinan variabel per term.  Untuk sebuah ekspresi SOP bentuk standar, sebuah 1 ditempatkan pada peta Karnaugh bagi setiap product term pada ekspresi.  Setiap 1 ditempatkan pada sebuah sel yang berkaitan ke nilai dari product term. Sebagai contoh product term AB’C, sebuah 1 muncul pada sel 101 pada peta 3-variable.

 Langkah berikut dan ilustrasinya pada gambar menunjukkan proses pemetaan.  Tentukan nilai biner dari setiap product term pada ekspresi standar.  Sebagaimana setap product term di-evaluasi, tempatkan sebuah 1 di peta Karnaugh pada sel yang memiliki nilai yang sama sebagaimana product term

Contoh  Petakan ekspresi SOP standar berikut ke peta Karnaugh 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶  Evaluasi setiap ekspresi. Tempatkan 1 pada peta Karnaugh 3-variable untuk setiap term product ekspresi standar.

 Petakan ekspresi SOP standar berikut ke peta Karnaugh 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶 𝐷  Evaluasi ekspresi. Tempatkan 1 pada peta Karnaugh 4-variabel di sel yang sesuai dengan setiap term product standar dalam ekspresi

Latihan  Petakan ekspresi standar SOP berikut ke peta Karnaugh 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶  Petakan ekspresi SOP standar berikut pada peta Karnaugh 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶𝐷

Minimalisasi SOP peta Karnaugh  Proses yang menghasilkan di dalam sebuah ekspresi berisi beberapa kemungkinan term dengan beberapa kemungkinan variabel disebut minimization (minimalisasi). Setelah sebuah ekspresi SOP dipetakan, ekspresi SOP minimum diperoleh dengan mengelompokkan 1 dan menentukan ekspresi minimum SOP dari peta.  Pengelompokkan 1.  Anda dapat mengelompokkan satu pada peta Karnaugh berdasarkan aturan berikut dengan menyertakan adjacent cell (sel tetangga/yang berdekatan) yang berisi 1. Tujuannya adalah memaksimalkan ukuran dari group dan untuk meminimalkan jumlah dari group.

Aturan  Sebuah grup harus berisi 1, 2, 4, 8 atau 16 sel, dimana semuanya 2n . Pada kasus peta 3-variabel, 23 = 8 sel adalah group maksimum  Setiap sel di dalam sebuah group harus adjacent dari 1 atau lebih sel dalam grup yang sama, tetapi semua sel di dalam group tidak harus menjadi adjacent setiap sel yang lain  Selalu sertakan kemungkinan jumlah 1 yang terbesar di dalam group menurut aturan 1  Setiap 1 pada peta harus disertakan pada sekurang-kurangnya 1 group. 1 yang telah di dalam group dapat disertakan ke group lain sepanjang group overlapping menyertakan noncommon 1

Contoh Pengelompokkan 1

Penentuan Ekspresi SOP minimum dari Peta  Ketika semua 1 merepresentasikan product term standar dalam sebuah ekspresi tepat di-petakan dan dikelompokkan, proses penentuan untuk menghasilkan ekspresi SOP minimum dimulai.  Aturan berikut diterapkan untuk mencari product term minimum dan ekspresi SOP minimum.

 Kelompokkan sel yang memiliki 1. Setiap group dari sel berisi 1 menciptakan sebuah product term terdiri dari semua variabel yang muncul dalam hanya satu bentuk (complement atau tidak komplemen) di dalam group. Variabel yang muncul komplemen dan tidak komplemen, di eliminasi. Ini disebut contradictory variables.

 Tentukan product term minimum untuk setiap group  Untuk peta 3-variabel    

1-cell group menghasilakn sebuah product term 3-variable 2-cell group menghasilkan sebuah product term 2-variable 4-cell group menghasilkan 1-variable term 8-cell group menghasilan sebuah nilai dari 1 bagi ekspresi

 Untuk peta 4-variabel     

1-cell group menghasilakn sebuah product term 4-variable 2-cell group menghasilkan sebuah product term 3-variable 4-cell group menghasilkan sebuah product term 2-variable 8-cell group menghasilan 1-variable term 16-cell grop menghasilkan sebuah nilai dari 1 bagi ekspresi

 Ketika semua product term minimum diturunkan dari peta Karnaugh, semuanya dijumlahkan untuk membentuk ekspresi SOP

 Tentukan product terms untuk peta Karnaugh berikut dan tuliskan ekspresi SOP yang minimum  Solusi:

 Eliminasi variabel yang di dalam sebuah group kedua complement dan tidak complement.  Pada contoh ini, product term untuk group 8 sel adalah B karena sel di dalam group tersebut berisi 𝐴 dan 𝐴, 𝐶 dan 𝐶, 𝐷 dan 𝐷, dimana dieliminasi.  Group 4 sel berisi 𝐵 dan 𝐵, 𝐷 dan 𝐷

Memetakan ekspresi SOP non standar  Ekspresi Boolean harus berbentuk standar sebelum memetakan ke Karnaugh. Jika belum, ekspresi harus diubah ke bentuk standar  Karena ekspresi harus dievaluasi sebelum mapping, ekspasi numerik (numerical expansion) adalah pendekatan yang paling efisien  Contoh: 1 product term dalam 3 variable ekspresi SOP, misalnya 𝐴𝐵. Ini term dapat diekspan secara numerik ke bentuk standar dengan cara sbb:

1. Tuliskan nilai biner dari dua variable dan tambahkan 0 utk variable 𝐶 yang tdk ada: 100 2. Tuliskan nilai binary dari dua variable dan tambahkan 1 untuk variable 𝐶 : 101 3. Bilangan biner yang dihasilkan adalah nilai dari term SOP standar 𝐴𝐵 𝐶 dan 𝐴𝐵𝐶

Contoh  Satu product term ekspresi 3 variable 𝐵. Ini bisa diekspan secara numerik ke standar form dengan cara sbb:

1. Tuliskan nilai biner dari variable; 2. kemudian attach semua nilai yang mungkin utk variable yang hilang seperti berikut: _B_ 1. 010, 011, 110, 111

3. Bilangan biner yang dihasilkan adalah nilai dari term SOP sandar 𝐴𝐵𝐶, 𝐴𝐵𝐶, 𝐴𝐵𝐶, dan 𝐴𝐵𝐶

 Bentuk standar tersebut kemudian dapat dipetakan ke Karnaugh Map

Latihan  Petakan ekspresi SOP berikut ke peta Karnaugh  𝐴 + 𝐴𝐵 + 𝐴𝐵𝐶  𝐵𝐶 + 𝐴𝐶  𝐵𝐶 + 𝐴𝐵 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷

Minimalisasi POS Karnaugh Map  Untuk ekspresi POS dalam bentuk standar, sebuah 0 ditempatkan pada peta Karnaugh untuk setiap sum term di ekspresi  Setiap 0 ditempatkan pada sebuah sel berkaitan dengan nilai dari sebuah sum term.  Misalnya sum term 𝐴 + 𝐵 + 𝐶, sebuah 0 pada sel 010 pada peta 3 variable  Ketika ekspresi POS telah lengkap dipetakan, di peta ada sejumlah 0 yang sama dengan jumlah sum term pada ekspresi standar  Sel yang tidak memiliki 0 adalah sel yang ekspresinya adalah 1  Biasanya ketika bekerja dengan ekspresi POS, 1 dibiarkan

Proses pemetaan  Tentukan nilai biner dari setiap sum term pada ekspresi standar POS. Nilai biner ini yang menjadikan the term = 0  Sebagaimana setiap sum term di-evaluasi, tempatkan 0 pada peta Karnaugh pada sel terkait

Penyederhaan Ekspresi POS Peta Karnaugh  Prinsip penyerderhanaan ekspresi POS secara mendasar sama sbgmana ekspresi SOP, kecuali pengelompokkan dilakukan untuk kelompok 0 yang menghasilkan sum term minimum (bukan mengelompokkan 1)  Aturan pengelompokkan 0 sama seperti pengelompokkan 1

Contoh (1)  Gunakan peta Karnaugh untuk menyederhanakan ekspresi POS standar berikut:  Tentukan ekspresi yang ekivalen dengan SOP

 Kombinasi nilai biner dari ekspresi adalah  Petakan ekspresi tersebut dan kelompokkan sel seperti berikut:

Penyederhanaan  Group 1:A+B+C, A+B+C’, A+B’+C, A+B’+C’  A  Group 2: A+B’+C, A’+B’+C  B’+C   A(B’+C)  Group 3: AB’C, ABC  AC  Group 4: AB’C’, AB’C  AB’   ekivalen SOP: AC + AB’  A(B’+C)

Contoh (2)  Gunakan peta Karnaugh untuk meminimalkan ekspresi berikut  Term pertama harus di ekspand: 𝐴 + 𝐵 + 𝐶 + 𝐷 dan (𝐴 + 𝐵 + 𝐶 + 𝐷)  Ekspresi POS minimum  (𝑪 + 𝑫)(𝑨 + 𝑩 + 𝑫)(𝑨 + 𝑩 + 𝑪)

Latihan (1) 1. Petakan ekspresi standar berikut ke peta Karnaugh (𝐴 + 𝐵 + C + D)(𝐴 + 𝐵 + 𝐶 + 𝐷)(𝐴 + 𝐵 + 𝐶 + 𝐷)(𝐴 + 𝐵 + 𝐶 + 𝐷)(𝐴 + 𝐵 + 𝐶 + 𝐷) 1. Kemudian sederhanakan ekspresi POS Karnaugh Map

2. Petakan ekspresi standar berikut ke peta Karnaugh (𝐴 + 𝐵 + 𝐶 + D)(𝐴 + 𝐵 + 𝐶 + 𝐷)(𝐴 + 𝐵 + 𝐶 + 𝐷)(𝐴 + 𝐵 + 𝐶 + 𝐷)

1. Kemudian sederhanakan ekspresi POS peta Karnaugh

Latihan (2)  Gunakan peta Karnaugh untuk menyederhanakan ekspresi standar POS berikut: 𝑋 + 𝑌 + 𝑍 𝑋 + 𝑌 + 𝑍 (𝑋 + 𝑌 + 𝑍)(𝑋 + 𝑌 + 𝑍)

 Gunakan peta Karnaugh untuk menyerderhanakan ekspresi POS berikut 𝑊 + 𝑋 + 𝑌 + 𝑍 𝑊 + 𝑋 + 𝑌 + 𝑍 (𝑊 + 𝑋 + 𝑌 + 𝑍)(𝑊 + 𝑋 + 𝑍)

Pemetaan langsung dari Truth Table  Perhatikan truth table yang keluarannya 1 untuk 4 kombinasi variable masukan yang berbeda.  Angka 1 pada kolom dari table kebenaran dipetakan langsung ke peta Karnaugh, ke sel yang bersesuaian dengan nilai dari gabungan kombinasi variable masukan.

Kondisi “Don’t Care”  Kadang ada kombinasi variable masukan yang tidak diizinkan.  Misalnya pada code BCD, ada 6 kombinasi yang invalid: 1010, 1101, 1100, 1101, 1110 dan 1111  Karena states yang tidak dibolehkan ini tidak akan pernah muncul/digunakan termasuk dalam code BCD, dianggap kombinasi tersebut sebagai term “don’t care” berkaitan dengan efeknya pada keluaran.  Term “don’t care” apakah diassign 1 atau 0 pada output; tidak masalah karena tidak akan pernah muncul  Term “don’t care” dapat digunakan untuk bermanfaat pada peta Karnaugh.

 Setiap term “don’t care”, sebuah X ditempatkan pada sel. Ketika mengelompokkan 1, X dapat diperlakukan sebagai 1 untuk membuat pengelompokkan yang panjang atau sebagai 0 jika tidak dapat digunakan untuk dimanfaatkan  Sebuah group yang besar, menghasilkan term yang lebih sederhana

BCD (Binary Coded Decimal ) Code  BCD code adalah sebuah cara untuk mengekspresikan setiap bilangan digit bilangan decimal dengan kode biner.  Hanya ada 10 kelompok kode dalam system BCD, sehingga mudah sekali mengkonversi antara decimal dan BCD  Kode 8421 BCD adalah sebuah tipe BCD (Binary Coded Decimal). BCD berarti setiap digit decimal, 0 – 9 direpresentasikan oleh 4 bit kode biner  8421 menunjukkan bobot dari 4 bit tersebut (23,22,21,20)  Kemudahan mengkonversi antara bilangan kode 8421 dan bilangan decimal adalah keuntungan utama dari kode BCD.

Invalid Code  Dengan 4 bit, 16 bilangan dapat direpresentasikan, tetapi dalam 8421 hanya 10 yang digunakan  Kombinasi 6 kode yang lain yang tidak digunakan yaitu 1010, 1011, 1100, 1101, 1110 dan 1111 – dianggap invalid di system kode BCD  Contoh BCD  35  0011 0101  98  1001 1000  170  0001 0111 0000  2469  0010 0100 0110 1001

BCD Code ke Desimal  10000110  ?  001110100001  ?  1001010001110000  ?  10000010001001110110  ?

Minterm dan Maxterm  Tabel kebenaran mendefinsikan fungsi Boolean. Ekspresi aljabar utk fungsi tersebut dapat diturunkan dari table dengan mencari logic penjumlahan dari product term dimana fungsi mengansumsikan nilai biner = 1  Sebuah product term yang mana semua variable muncul tepat sekali, apakah dia complement atau tidak complement disebut minterm.  Sebuah sum term yang berisi semua variable dalam bentuk complement atau tidak complement disebut maxterm

Minterm  Properti karakteristiknya bhw minterm merepresentasikan tepat satu kombinasi dari nilai variable biner dalam table kebenaran  Ia memiliki nilai 1 untuk kombinasi tersebut dan 0 untuk yang lain  Contoh: untuk variable X dan Y, minterm nya adalah 𝑋𝑌, 𝑋𝑌, 𝑋𝑌 dan 𝑋𝑌  Ada 8 minterm untuk 3 variable (lihat table berikut)  Setiap minterm adalah product term dari tepat 𝑛 literal, dimana 𝑛 adalah jumlah variable.

 Untuk setiap kombinasi biner, ada minterm terkait. Setiap minterm adalah sebuah product term dari tepat n literal, dimana n adalah jumlah dari variable  Simbol 𝑚𝑗 untuk setiap minterm yang ditunjukkan di table, dimana 𝑗 menunjukkan ekivalen decimal utk setiap kombinasi biner yang terkait minterm  Daftar minterm untuk setiap 𝑛 variable dapat dibentuk dari daftar bilangan biner dari 0 s/d 2𝑛 − 1.  Pada table, tampak setiap minterm adalah 1 utk kombinasi biner terkait dan 0 utk kombinasi yang lain

Minterm untuk 3 variable

Maxterm  Sebuah sum term yang berisi semua variable (complemen atau tidak komplemen) membentuk  maxterm  Memungkinkan meng-formulasikan 2𝑛 maxterm dengan 𝑛 variable.  8 maxterm ditampilkan pada table berikut ini  Setiap maxterm adalah penjumlahan logic dari 3 variable dengan masing-masing variable komplemen jika bit biner terkait adalah 1 dan tidak komplemen jika 0.  Simbol maxterm adalah 𝑀𝑗 , dimana j menyatakan ekivalen decimal dari kombinasi biner maxterm terkait.  Perhatikan bawha maxterm =0 utk kombinasi terkait dan 1 utk semua kombinasi yang lain.

Maxterm untuk 3 variable

Minterm dan Maxterm  Sebuah minterm adalah sebuah fungsi, tidak sama dengan 0, memiliki sejumlah minimum 1 di dalam table kebenaranya.  Sebuah maxterm adalah sebuah fungsi, tidak sama dengan 1, memiliki jumlah maksimum dari 1 di dalam table kebenarannya  Dari 2 table sebelumnya, minterm dan maxterm dengan index yang sama adalah berkomplemen 𝑀𝑗 = 𝑚𝑗 dan 𝑚𝑗 = 𝑀𝑗  Contoh: j= 3; 𝑀3 = 𝑋 + 𝑌 + 𝑍 = 𝑋𝑌𝑍 = 𝑚3

 Fungsi Boolean dapat direpresentasikan secara aljabar dari table kebenaran yang tersedia dengan membentuk penjumlahan logic dari semua minterm yang menghasilkan 1 di dalam fungsi  Ekspresi ini disebut sum of terms. Perhatikan fungsi Boolean F pada table. Fungsi F = 1 untuk kombinasi biner dari variable X, Y, Z: 000, 010, 101 dan 111. Kombinasi ini berkaitan dengan minterm 0,2,5, dan 7

 Dengan memperhatikan table Fungsi Boolean, dan table kebenaran utk minterms, fungsi F dapat diekspresikan secara aljabar sebagai penjumlahan logic dari minterm  𝐹 = 𝑋𝑌𝑍 + 𝑋𝑌𝑍 + 𝑋𝑌𝑍 + 𝑋𝑌𝑍 = 𝑚0 + 𝑚2 + 𝑚5 + 𝑚7

 Selanjutnya dapat disingkat dengan hanya daftar dari index dari mintermnya  𝐹 𝑋, 𝑌, 𝑍 =

𝑚(0,2,5,7)

 Simbol Σ adalah penjumlahan logic (OR) dari minterm; angka menunjukkan minterm dari fungsi  Contoh:𝐹 𝑋, 𝑌, 𝑍 = 𝑋𝑌𝑍 + 𝑋𝑌𝑍 + 𝑍𝑌𝑍 + 𝑋𝑌𝑍 = 𝑚1 + 𝑚3 + 𝑚4 + 𝑚6  Disingkat: 𝐹 𝑋, 𝑌, 𝑍 = 𝑚(1,3,4,6)

 Komplemen dari F adalah  𝐹 = 𝑚1 + 𝑚3 + 𝑚4 + 𝑚6 = 𝑚1 . 𝑚3 . 𝑚4 . 𝑚6  = 𝑀1 𝑀3 𝑀4 𝑀6 karena 𝑚𝑗 = 𝑀𝑗  = 𝑋 + 𝑌 + 𝑍 𝑋 + 𝑌 + 𝑍 𝑋 + 𝑌 + 𝑍 (𝑋 + 𝑌 +

Metoda Quine-McCluskey  Metoda formal tabular untuk menerapkan hukum distribusi Boolean ke berbagai term untuk mencapai SOP minimum dengan mengeliminasi literal yang muncul dalam 2 term sebagai komplemen  Contoh: ABCD + ABCD’ = ABC  Sangat cocok untuk reduksi yang terkomputerisasi. Peta Karnaugh, bersifat metoda grafik.

Cara menerapkan metoda Quine-McCluskey  Tuliskan fungsi dalam bentuk minterm standar (SOP).  Representasikan ekspresi sebagai bilangan biner seperti yagn ditunjukkan pada table kebenaran berikut

Langkah 2  Arrange minterm dalam ekspresi asli dalam grup berdasarkan jumlah angka 1 pada setiap minterm

Langkah ke-3  Bandingkan dengan grup yang berdekatan, lihat jika ada minterm yang memiliki posisi yang sama kecuali 1 posisi. Jika ada, berikan tanda cek pada setiap minterm di masing-masing group.  Kecuali 𝑚10 tidak di-cek, krn tidak memenuhi syarat (disebut essential prime implicant)

 Term pada daftar first level digunakan untuk membentuk table yang direduksi dengan jumlah 1 pada group lebih kecil dari group lain.  Term pada group baru dibandingkan. Dipilih jika hanya memiliki x pd posisi yang sama dengan group berdekatan (second level)

 Pada second level dapat dibaca sebagai B𝐶  Term yang tidak di-cek akan membentuk term lain pada ekspresi yang direduksi final.  Term 1 tidak di-cek: 𝐴𝐵𝐷  Term 2 : 𝐴𝐶D  Term 3 : 𝐴𝐵𝐷  Pada first level: 𝐴𝐵𝐶 𝐷  Ekspresi yang dikurangi (yg tidak di-cek)  B𝐶 + 𝐴𝐵𝐷 + 𝐴𝐶D+𝐴𝐵𝐷 + 𝐴𝐵𝐶 𝐷

 Meskipun ekspresi sdh tepat, tetapi bukan ekspresi yang minimum.  Pengecekan terakhir mengeliminasi term yang tidak perlu.  Term2 tersebut ditulis dalam table prime implicant dengan minterm utk setiap prime implicant yang di-cek

 Jika prime implicant memiliki 1 centang, dia penting dan harus dimasukkan dalam ekspresi final  Term 𝐴𝐵𝐷 harus disertakan karena 𝑚15 hanya dicover oleh term tsb  Begitu juga 𝑚10 hanya di-cover oleh 𝐴𝐵𝐶 𝐷, maka akan masuk dalam ekspresi final  Dua minterm di 𝐴𝐶D di-cover oleh prime implicants pada 2 baris pertama, karenanya term ini tidak perlu. Sehingga ekspresi final adalah B𝐶 + 𝐴𝐵𝐷+𝐴𝐵𝐷 + 𝐴𝐵𝐶 𝐷

Latihan