Peta Karnaugh dan Maxterm&Minterm

PETA KARNAUGH

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.

Adjacency didefiniskan oleh sebuah perbuahan single-variabel. Pada peta 3-variabel, sel -1- berdekatan dengan sel 000, sel -11 dan sel 110. Namun sel 010 tidak berdekatan dengan sel 001, sel 111, sel 100 atau sel 1-1. Secara fisik, setiap sel adalah berdekatan dengan sel yang bersebelahan langsung dengan sel tersebut (dari salah satu 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 di-wrapping arround dari atas ke bawa untuk membentuk silinder atau dari kiri ke kanan untuk membentuk silinder.

Minimalisasi SOP Karnaugh Map

Peta Karnaugh digunakan untuk menyederhanakan ekspresi Boolean ke bentuk minimumnya. Ekspresi SOP yang di-minimalkan 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-Variabel.

Langkah berikut dan ilustrasinya pada gambar menunjukkan proses pemetaaan.

Contoh 1

Petakan ekspresi SOP standar berikut ke peta Karnaugh

A'B'C+A'BC'+ABC'+ABC

Solusi

Evaluasi setiap ekspresi. Tempatkan 1 pada peta Karnaugh 3-Variabel untuk setiap term product ekspresi standar.

Contoh 2

Petakan ekspresi SOP standar berikut ke peta Karnaugh

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

Solusi

Evaluasi ekspresi. Tempatkan 1 pada peta Karnaugh 4-variabel di sel yang sesuai dengan setiap term product standar dalam ekspresi

Aturan Penyerdahanaan Karnaugh Map

1. Sebuah grup harus berisi 1,2,4,8 atau 16 sel, dimana semuanya 2n. Pada kasus peta 3-variabel, 23=8 sel adalah grup maksimum

2. Setiap sel didalam sebuah grup 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

3. Selalu sertakan kemungkinan jumlah 1 yang terbesar di dalam grup menurut aturan 1

4. Setiap 1 pada peta harus disertakan pada sekurang-kurangnya 1 grup. 1 yang telah di dalam grup dapat disertakan ke grup lain sepanjang grup overlapping menyertakan noncommon 1

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: 1 product term dalam 3 variabel ekspresi SOP, misalnya AB'. Ini term dapat diekspan secara numerik ke bentuk standar dengan cara sbb:

1. Tuliskan nilai biner dari dua variabel dan tambahkan 0 untuk variabel C yang tidak ada: 100

2. Tuliskan nilai binary dari dua variabel dan tambahkan 1 untuk variabel C:101

3. Bilangan biner yang dihasilkan adalah nilai dari term SOP standar AB'C dan AB'C'

Minterm

Properti karakteristiknya bahwa minterm merepresentasikan tepat satu kombinasi dari nilai variabel biner dalam table kebenaran. Ia memiliki nilai 1 untuk kombinasi tersebut dan 0 untuk yang lain.

Contoh: untuk variabel X dan Y, minterm nya adalah X'Y', X'Y, XY' dan XY

Setiap minterm adalah product term dari tepat n literal, dimana n adalah jumlah variabel. Untuk setiap kombinasi biner, ada minterm terkait. Setiap minterm adalah sebuah procut term dari tepat n literal, dimana n adalah jumlah dari variabel.

Simbol mj untuk setiap minterm yang ditunjukkan di table, dimana j menunjukkan ekivalen decimal untuk setiap kombinasi biner yang terkait minter. Daftar minterm untuk setiap n variable dapat dibentuk dari daftar bilangan biner dari 0s/d 2n-1.

Pada table, tampat setiap minterm adalah 1 untuk kombinasi biner terkait dan 0 untuk kombinasi yang lain

Maxterm

Sebuah sum term yang berisi semua variabel (complemen atau tidak komplemen) membentuk => maxterm. Memungkinkan meng-formulasikan 2n maxterm dengan n variabel. Setiap maxterm adalah penjumlahan logic dari 3 variabel dengan masing-masing variabel komplemen jika bit biner terkait adalah 1 dan tidak komplemen jika 0. Simbol maxterm adalah Mj, dimana j menyatakan ekivalen decimal dari kombinasi biner maxterm terkait. Perhatikan bahwa maxterm=0 untuk kombinasi terkait dan 1 untuk semua kombinasi yang lain.

Lanjutan Minterm dan Maxterm

Sebuah minterm adalah sebuah fungsi, tidak sama dengan 0, memiliki sejumlah minimum 1 di dalam table kebenarannya. Sebuah maxterm adalah sebuah fungsi, tidak sama dengan 1, memiliki jumlah maksimum dari 1 didalam table kebenarannya. Dari 2 table sebelumnya, minterm dan maxterm dengan index yang sama adalah berkomplemen Mj=mj dan mj=Mj

Contoh: j=3; M3=X+Y+Z=XYZ=m3

Fungsi Boolean dapat direpresentasikan secara aljabar dari table kebenaran yang tersedia dengan membentuk penjumlahan logic dari semua minterm yang menghasilkan 1 didalam 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 untuk minterms, fungsi F dapat diekspresikan secara aljabar sebagai penjumlahan logic dari minterm

F=XYZ+XYZ+XY Z+XYZ=m0+m2+m5+m7

Selanjutnya dapat disingkat dengan hanya daftar dari index dari mintermnya

FX,Y,Z=m(0,2,5,7)

Simbol adalah penjumlahan logic(OR) dari minterm; angka menunjukan minterm dari fungsi

Contoh: F(X,Y,Z)=X'Y'Z+X'YZ+ZY'Z=m1+m3+m4+m6 yang disingkat menjadi F(X.Y.Z)=m(1,3,4,6)