Karnaugh Map

Karnaugh map adalah sebuah metode untuk menyederhanakan ekspresi aljabar Boolean. Karnaugh map mengurangi kebutuhan untuk perhitungan luas dengan mengambil keuntungan dari kemampuan pengenalan pola-manusia ', yang memungkinkan identifikasi cepat dan penghapusan kondisi ras potensial.

Dalam Karnaugh map  variabel boolean ditransfer (biasanya dari tabel kebenaran) dan memerintahkan sesuai dengan prinsip-prinsip kode Gray di mana hanya satu perubahan variabel di antara kotak. Setelah tabel dihasilkan dan kemungkinan-kemungkinan output ditranskripsi, data diatur ke dalam kelompok mungkin terbesar yang mengandung sel-sel 2n (n = 0,1,2,3 ...)[ 1] dan minterm yang dihasilkan melalui hukum aksioma aljabar boolean.

Karnaugh map digunakan untuk memfasilitasi penyederhanaan fungsi Aljabar Boolean.

Berikut ini adalah fungsi Aljabar Boolean unsimplified dengan variabel Boolean A, B, C, D, dan invers mereka. Mereka dapat direpresentasikan dalam dua fungsi yang berbeda:

f(A,B,C,D) = ∑(6,8,9,10,11,12,13,14) 
Catatan: Nilai-nilai di dalam Σ adalah minterms untuk memetakan (yaitu yang memiliki output baris 1 di tabel kebenaran)..

Tabel Kebenaran

Menggunakan minterms didefinisikan, tabel kebenaran dapat diciptakan:

#         A         B          C         D         f(A,B,C,D)

0          0          0          0          0          0

1          0          0          0          1          0

2          0          0          1          0          0

3          0          0          1          1          0

4          0          1          0          0          0

5          0          1          0          1          0

6          0          1          1          0          1

7          0          1          1          1          0

8          1          0          0          0          1

9          1          0          0          1          1

10        1          0          1          0          1

11        1          0          1          1          1

12        1          1          0          0          1

13        1          1          0          1          1

14        1          1          1          0          1

15        1          1          1          1          0

K-map yang menunjukkan minterms dan kotak meliputi minterms diinginkan. Daerah coklat adalah tumpang tindih daerah merah (persegi) dan hijau.

Variabel input dapat dikombinasikan dalam 16 cara yang berbeda, sehingga Karnaugh mapmemiliki 16 posisi, dan karena itu diatur dalam kotak 4 × 4.

Angka biner di peta merupakan keluaran fungsi untuk setiap kombinasi masukan tertentu. Jadi 0 adalah ditulis di sudut paling kiri atas dari peta karena f = 0 bila A = 0, B = 0, C = 0, D = 0. Demikian pula kita tandai sudut kanan bawah sebagai 1 karena A = 1, B = 0, C = 1, D = 0 memberikan ƒ = 1. Perhatikan bahwa nilai-nilai yang diperintahkan dalam kode Gray, sehingga perubahan variabel tepat satu antara setiap pasangan sel yang berdekatan.

Setelah Karnaugh map telah dibangun tugas berikutnya adalah untuk menemukan persyaratan minimal untuk digunakan dalam ekspresi akhir. Istilah-istilah ini ditemukan oleh kelompok mengelilingi 1s di peta. Kelompok-kelompok harus persegi panjang dan harus memiliki luas yang merupakan kekuatan dua (yaitu 1, 2, 4, 8 ...). Persegi panjang harus seluas mungkin tanpa mengandung apapun 0s. Pengelompokan optimal dalam peta ini ditandai dengan garis hijau, merah dan biru. Perhatikan bahwa kelompok mungkin tumpang tindih. Dalam contoh ini, kelompok merah dan hijau tumpang tindih. Kelompok merah adalah persegi 2 × 2, kelompok hijau adalah sebuah persegi panjang 4 × 1, dan tumpang tindih area ditunjukkan dalam coklat.

grid adalah toroidally tersambung, yang berarti bahwa kelompok empat persegi panjang dapat membungkus di sekitar tepi, jadi \ scriptstyle A \ overline {D} adalah istilah yang sah, meskipun bukan bagian dari minimal set-ini meliputi Minterms 8, 10, 12, dan 14 .

Mungkin yang paling sulit-untuk-memvisualisasikan wrap-around istilah \ scriptstyle \ overline {B} \, \ overline {D} yang meliputi empat sudut-ini meliputi minterms 0, 2, 8, 10.

Solusi

Setelah Karnaugh map telah dibangun dan kelompok berasal, solusi dapat ditemukan dengan menghilangkan variabel ekstra dalam kelompok menggunakan hukum aksioma dari aljabar boolean. Dapat disimpulkan bahwa daripada menghilangkan variabel bahwa perubahan dalam pengelompokan, fungsi minimal dapat diturunkan dengan mencatat yang variabel tetap sama.

Untuk pengelompokan Merah:

    * Variabel A mempertahankan negara yang sama (1) di seluruh mengelilinginya, sehingga harus dimasukkan dalam jangka untuk mengelilingi merah.
    * Variabel B tidak mempertahankan negara yang sama (itu bergeser 1-0), dan karena itu harus dikeluarkan.
    * C tidak berubah: selalu 0. Karena C adalah 0, itu harus ditiadakan sebelum dimasukkan (dengan demikian, C).
    *D mengalami pergantian, sehingga dikecualikan juga.

Jadi istilah pertama dalam jumlah Boolean-of-produk ekspresi adalah AC.

Untuk Green pengelompokan kita melihat bahwa A dan B mempertahankan negara yang sama, tetapi perubahan C dan D. B adalah 0 dan harus ditiadakan sebelum dapat disertakan. Jadi istilah kedua adalah  AB.

Dengan cara yang sama, pengelompokan Biru memberikan SM istilah BCD.

Solusi dari setiap kelompok digabungkan menjadi: AC+AB+BCD.

• Invers
  
  Invers dari suatu fungsi diselesaikan dengan cara yang sama dengan mengelompokkan 0s gantinya.
  
  Ketiga istilah untuk menutup kebalikannya semua ditampilkan dengan kotak berwarna abu-abu dengan batas-batas yang berbeda:
  
      * Coklat—AB
      * Emas—AC
      * Biru-BCD
  
  Ini menghasilkan kebalikannya:
  
            F=AB+AC+BCD
  Melalui penggunaan hukum De Morgan, produk dalam jumlah dapat ditentukan: