PETA KARNAUGH DAN MAXTERN & MINTERN

  Peta Karnaugh

Peta karnaugh (atau K-Map) diperkenalkan oleh Maurice Karnaugh tahun 1953 (wikipedia) adalah sebuah metode untuk menyederhanakan fungsi persamaan logika sehingga (Freddy Kurniawan: Sistem Digital):

1. Menggunakan jumlah gerbang lebih sedikit sehingga waktu tunda total untai menjadi lebih kecil
2. Kemungkinan resiko kegagalan fungsi lebih kecil karena penggunaan gerbang dan perkawatan yang lebih sedikit
3. Daya total yang dikonsumsi untai logika juga akan lebih kecil.
4. Hemat biaya

Peta Karnaugh di-"ilustrasikan" seperti matrik 2 dimensi (terdiri atas baris dan kolom) dimana komponen baris dan kolom adalah masukan (input) dari sistem. Input dari masukan inilah yang kemudian disebut variabel K-Map nya. Sehingga ada sebutan K-Map 2 Peubah, K-Map 3 Peubah, 4 peubah dst.

K-Map efektif digunakan hanya sampai 6 peubah saja. Untuk peubah lebih dari 6, tidak lagi di-rekomendasikan menggunakan K-Map karena komputasinya sangat tinggi sehingga disarankan menggunakan program komputer khusus. Tutorial kali ini, saya akan membahas K-Map hingga 4 Variabel. Untuk K-Map 5 dan 6 Peubah akan dibahas pada tutorial berikutnya.

Menggambar peta karnagh

Peta Karnaugh 2 Peubah:

Ilustrasi berikut adalah peta karnaugh 2 peubah (A dan B).

Kelompok Baris adalah masukan A dan Kelompok Kolom adalah masukan B. Tidak ada yang spesial dari aturan K-Map 2 Variabel. Anda bisa menulisnya 0 kemudian 1 (sesuai contoh) atau 1 kemudian 0.

Sekarang kita lihat tabel kebenaran dari fungsi yang akan kita buat. Asumsikan, kita tidak memiliki fungsi persamaan dari tabel kebenaran berikut dan kita akan membuatnya.

Setiap cell dari matrik (bagian tengah) akan kita isi dengan hasil atau result dari tabel kebenaran. Sebagai contoh:

Peta Karnaugh 3 Peubah:
Sedikit berbeda dengan peta karnaugh 2 peubah, K-Map 3 peubah menggunakan 2 peubah di satu rusuk dan 1 peubah di rusuk yang lain. Anda bisa membuat K-Map dengan 2 peubah di rusuk tegak, dan 1 peubah di rusuk mendatar atau sebaliknya. Perhatikan gambar:

Yang perlu diperhatikan di sini adalah penyusunan kombinasi masukan 2 peubah harus mengikuti kaidah "perubahan di satu tempat". Artinya transisi dari "0" ke "1" hanya di satu tempat saja. Sebagai contoh, kombinasi masukan dari "01" menjadi "11". Transisi yang terjadi pada kombinasi ini hanya pada masukan A (dari 0 menjadi 1) sedangkan masukan B tetap (1 tetap 1). Jadi anda tidak boleh menulis "01" kemudian "10" (seperti yang biasa anda lakukan di tabel kebenaran). Mengapa? karena jika susunan-nya "01" kemudian "10", berarti perubahan terjadi di 2 masukan, A berubah dari "0" menjadi "1" dan masukan B berubah dari "1" menjadi "0".

Seperti pada K-Map 2 peubah, isi Cell dari K-Map 3 peubah juga berisi result (hasil) dari tabel kebenaran. Sebagai contoh:

Anda boleh menggunakan K-Map yang atas atau yang bawah.

Peta Karnaugh 4 Peubah:

Untuk K-Map 4 peubah, anda dapat memasukkan 2 peubah di rusuk tegak dan 2 peubah di rusuk mendatar. Perhatikan gambar:

Daerah Minterm

Nah sekarang kita sudah bisa menggambar peta Karnaugh atau K-Map dengan 2, 3 dan 4 peubah. Proses berikutnya adalah menentukan daerah minterm. Daerah minterm adalah sebuah daerah di dalam K-Map yang berisi nilai 1 yang "bertetangga" (akan dijelaskan dalam contoh). Keanggotaan sebuah daerah minterm bisa berisi 2^n dimana n bernilai 0, 1, 2, 3, ... dst. Sehingga keanggotaan wilayah minterm bisa 1, 2, 4, 8, 16, dst.

Melukiskan daerah minterm, bisa secara vertikal (atas bawah) atau horisontal (kiri dan kanan) tetapi tidak bisa secara diagonal.

Contoh daerah minterm untuk K-Map 2 peubah adalah sebagai berikut:

Keterangan:

(A): Karena nilai "1" hanya ada satu, maka daerah mintermnya juga hanya 1.

(B): Nilai "1" ada di dua tempat (cell) tetapi mereka bertetangga secara diagonal, maka angka-angka "1" tersebut tidak bisa menjadi satu wilayah minterm.

(C): Terdapat 2 wilayah minterm dengan masing-masing memiliki 2 anggota angka "1".

(D): Mirip dengan kasus point (B).

Sedikit berbeda untuk K-Map dengan dimensi yang lebih besar(di atas dimensi 2x2), K-Map "dipandang sebagai sebuah bidang yang "bulat" seperti globe. Artinya daerah minterm bisa saja "menyatukan" angka 1 yang di sisi atas dan bawah atau kiri dan kanan secara berputar. Lihat contoh di bawah ini:

Ingat: Tidak bisa diagonal saja.

Membangun persamaan dari daerah minterm di K-Map

Setelah daerah minterm sudah kita tandai, proses berikutnya adalah menentukan persamaan dari daerah minterm tersebut. Kita bisa menggunakan asas "konsistensi" untuk memudahkan membangun persamaan daerah minterm tersebut. Konsistensi yang saya maksud adalah nilai masukan yang TIDAK BERUBAH di setiap sel daerah minterm. Sebagai contoh untuk daerah minterm yang hanya berisi satu anggota seperti pada gambar berikut:

Karena kita tidak bisa membuat daerah minterm secara diagonal maka K-Map di atas memiliki 2 daerah minterm. Untuk daerah mintem yang berisi satu anggota saja, membuat persamaannya cukup mudah. Cukup lihat masukan untuk setiap daerah minterm tersebut.

Daerah minterm 1: masukan dari sisi baris adalah A'B dan dari sisi kolom adalah C'. Nilai akses (') di sini mengacu pada nilai 0 pada masukan A dan C (sedangkan karena nilai B bernilai "1" maka tidak diberi aksen atau NOT).

Daerah minterm 2: masukan dari sisi baris adalah AB dan dari sisi kolom adalah C (semua nilai masukan "1" maka tidak ada aksen)

Sehingga fungsi persamaan dari K-Map tersebut adalah: A'BC + ABC.

Pembuktian dengan tabel kebenaran:

Untuk daerah minterm yang berisi lebih dari satu, asas konsistensi bisa kita gunakan. Perhatikan contoh:

Pada contoh di atas, daerah mintem yang terbentuk memiliki empat anggota dimana masukannya adalah:

1. Sisi Baris (AB): 01 dan 11
2. Sisi Kolom (CD): 01 dan 11

Nilai yang konsisten di sisi baris adalah B. (A tidak konsisten karena ada A yang bernilai "1" dan ada A yang bernilai "0". Sedangkan nilai yang konsisten di sisi kolom adalah D. (nilai C tidak konsisten).

Sehingga persamaan untuk K-Map di atas adalah BD. Lihat pada tabel kebenaran berikut:

Contoh lain:

Daerah minterm 1 (yang berwarna biru): Masukan yang konsisten di sisi baris (masukan AB) adalah B dan masukan yang konsisten di sisi kolom adalah C sehingga rumus fungsinya adalah BC

Daerah minterm 2 (yang berwarna merah): Masukan yang konsisten di sisi baris (masukan AB) tidak ada (semuanya (baik A dan B) tidak ada yang konsisten) sedangkan masukan yang konsisten di sisi kolom adalah CD'.

Sehingga persamaan fungsi dari K-Map di atas adalah F = BC + CD'. Perhatikan tabel kebenaran berikut:

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)