K-MAP

Peta Karnaugh (K-peta untuk pendek), Maurice Karnaugh 's 1953 penyempurnaan dari Edward Veitch 's diagram Veitch 1952, adalah metode untuk menyederhanakan aljabar Boolean ekspresi. Peta Karnaugh mengurangi kebutuhan untuk perhitungan luas dengan mengambil keuntungan dari kemampuan pengenalan pola manusia ', yang memungkinkan identifikasi cepat dan penghapusan potensi kondisi ras . Dalam peta Karnaugh dengan boolean variabel ditransfer (umumnya dari tabel kebenaran ) dan memerintahkan sesuai dengan prinsip-prinsip kode Gray di mana hanya satu variabel perubahan di antara kotak yang berdekatan. Setelah tabel dihasilkan dan kemungkinan output ditranskripsi, data diatur ke dalam kelompok terbesar yang mungkin mengandung 2 sel ^{n (n} = 0,1,2,3 ...) ^[1] dan minterm dihasilkan melalui aksioma hukum aljabar boolean. 

Peta Karnaugh digunakan untuk memfasilitasi penyederhanaan aljabar Boolean fungsi. Berikut ini adalah fungsi Aljabar Boolean unsimplified dengan variabel Boolean A, B, C, D, dan invers mereka. Mereka dapat direpresentasikan dalam dua notasi yang berbeda:

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

peta Karnaugh

K-peta konstruksi.

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

Angka biner dalam peta merupakan keluaran fungsi untuk setiap kombinasi input tertentu. Jadi 0 adalah ditulis di sudut paling kiri atas dari peta karena ƒ = 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 tepat satu variabel perubahan antara sepasang sel yang berdekatan.

Setelah peta Karnaugh telah dibangun tugas berikutnya adalah untuk menemukan istilah minimal untuk digunakan dalam ekspresi akhir. Istilah-istilah ini ditemukan oleh kelompok mengelilingi 1s dalam 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 0s apapun. Pengelompokan optimal dalam peta ini ditandai oleh, 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 4 × 1 persegi panjang, dan daerah tumpang tindih ditunjukkan dalam coklat.

Grid toroidally terhubung, yang berarti bahwa kelompok-kelompok persegi panjang bisa membungkus di sekitar tepi, sehingga adalah istilah yang valid, meskipun bukan bagian dari minimal set-ini mencakup Minterms 8, 10, 12, dan 14.

Mungkin istilah yang paling sulit-untuk-memvisualisasikan wrap-sekitar adalah yang meliputi empat sudut-ini mencakup minterm 0, 2, 8, 10.

[ sunting ] Solusi

Setelah Peta Karnaugh telah dibangun dan kelompok berasal, solusi dapat ditemukan dengan menghilangkan variabel tambahan di dalam kelompok dengan menggunakan aljabar boolean aksioma . Hal ini dapat tersirat bahwa daripada menghilangkan variabel yang berubah dalam pengelompokan, fungsi minimal dapat diturunkan dengan memperhatikan variabel-variabel yang tetap sama.

Untuk pengelompokan Merah:

• Variabel Sebuah mempertahankan keadaan yang sama (1) di seluruh keliling, oleh karena itu harus dimasukkan dalam jangka untuk mengelilingi merah.
• Variabel B tidak mempertahankan negara yang sama (itu bergeser dari 1 ke 0), dan karenanya harus dikeluarkan.
• C tidak berubah: selalu 0. Karena C adalah 0, itu harus dinegasikan sebelum dimasukkan (dengan demikian, ).
• Perubahan D, sehingga dikecualikan juga.

Jadi istilah pertama dalam ekspresi sum-of-produk Boolean adalah

Untuk pengelompokan Hijau kita melihat bahwa A, B mempertahankan negara yang sama, tetapi C dan D berubah. B adalah 0 dan harus menegasikan sebelum dapat disertakan. Jadi istilah kedua adalah

Dengan cara yang sama, pengelompokan Biru memberikan istilah

Solusi dari setiap pengelompokan digabungkan menjadi:

[ sunting ] Invers

Invers dari fungsi ini diselesaikan dengan cara yang sama dengan mengelompokkan 0s sebagai gantinya.

Tiga istilah untuk menutupi terbalik semua ditampilkan dengan kotak abu-abu dengan batas-batas warna yang berbeda:

• coklat-
• emas-
• biru B C D

Ini menghasilkan invers:

Melalui penggunaan hukum De Morgan , yang produk dari jumlah dapat ditentukan:

Jangan peduli

Ke-15 minterm dijatuhkan dan diganti sebagai tidak peduli, ini menghilangkan istilah hijau sepenuhnya tapi membatasi istilah invers biru

Peta Karnaugh juga memungkinkan minimizations mudah fungsi yang kebenarannya tabel termasuk " tidak peduli "kondisi (yaitu, set input yang desainer tidak peduli apa output adalah) karena" tidak peduli "kondisi dapat dimasukkan dalam kelompok dilingkari dalam upaya untuk membuatnya lebih besar. Mereka biasanya ditunjukkan pada peta dengan sedikit atau X.

Contoh ke kanan adalah contoh di atas sama tetapi dengan minterm 15 turun dan diganti sebagai tidak peduli. Hal ini memungkinkan istilah merah untuk memperluas semua jalan ke bawah dan, dengan demikian, menghilangkan istilah hijau sepenuhnya.

Ini menghasilkan persamaan minimum baru:

Perhatikan bahwa istilah pertama hanya A tidak . Dalam kasus ini, tidak peduli telah menjatuhkan istilah (hijau); disederhanakan lain (merah), dan dihapus bahaya ras (kuning seperti yang ditunjukkan pada bagian berikut).

Juga, sejak kasus invers tidak lagi memiliki untuk menutupi minterm 15, minterm 7 dapat ditutup dengan bukan dengan keuntungan serupa.

[ sunting ] bahaya Ras

[ sunting ] Penghapusan

Di atas k-peta dengan jangka ditambahkan untuk menghindari bahaya ras

Peta Karnaugh berguna untuk mendeteksi dan menghilangkan bahaya ras . Bahaya ras sangat mudah untuk menemukan menggunakan peta Karnaugh, karena kondisi lomba mungkin ada ketika bergerak antara sepasang berdekatan, tapi terputus-putus, daerah dilingkari pada peta.

• Dalam contoh ke kanan, kondisi lomba potensial yang ada ketika C adalah 1 dan D adalah 0, A adalah 1, dan perubahan B dari 1 ke 0 (bergerak dari biru ke negara negara hijau). Untuk kasus ini, output didefinisikan untuk tetap tidak berubah pada 1, tetapi karena transisi ini tidak tercakup oleh istilah tertentu dalam persamaan, potensi glitch (transisi sesaat output ke 0) ada.

·  Ada kesalahan potensial kedua dalam contoh yang sama yang lebih sulit untuk spot: bila D adalah 0 dan A dan B keduanya 1, dengan C berubah dari 1

• ke 0 (bergerak dari biru ke negara negara merah). Dalam hal ini kesalahan yang membungkus di sekitar dari atas peta ke bawah.

Apakah ini benar-benar akan terjadi gangguan tergantung pada sifat fisik pelaksanaan, dan apakah kita perlu khawatir tentang hal itu tergantung pada aplikasi.

Dalam hal ini, istilah tambahan akan menghilangkan potensi bahaya ras, menjembatani antara negara-negara keluaran hijau dan biru atau negara output yang biru dan merah: ini adalah ditampilkan sebagai daerah kuning.

Istilah ini berlebihan dalam hal logika statis dari sistem, tetapi berlebihan seperti itu, atau istilah konsensus , sering dibutuhkan untuk menjamin performa bebas ras dinamis.

Demikian pula, istilah tambahan harus ditambahkan dengan kebalikan untuk menghilangkan bahaya lain ras potensial. Menerapkan hukum De Morgan menciptakan produk lain dari ekspresi jumlah untuk F, tetapi dengan faktor baru

.