Pemecah Peta Karnaugh (K-Map)

Pemecah Peta Karnaugh (K-Map) meminimalkan fungsi logika Boolean apa pun dari 2 hingga 5 variabel dan memvisualisasikan penyederhanaannya sebagai peta K-map klasik dengan pengelompokan berkode warna. Masukkan minterm, maxterm, atau gunakan tabel kebenaran interaktif — pemecah masalah ini menjalankan algoritma Quine-McCluskey di balik layar, menemukan setiap implikan prima, menandai yang esensial, dan menghasilkan ekspresi Sum-of-Products (SOP) atau Product-of-Sums (POS) minimal dengan penjelasan langkah demi langkah. Klik chip implikan prima mana pun untuk memberikan efek denyut pada sel yang dicakupnya dan lihat bagaimana pengelompokan tersebut menyederhanakan logika.

Apa itu Peta Karnaugh?

Peta Karnaugh (ditemukan oleh Maurice Karnaugh pada tahun 1953) adalah representasi grafis dari tabel kebenaran, disusun sedemikian rupa sehingga sel-sel yang hanya berbeda satu variabel input berada berdekatan secara fisik. Trik utamanya adalah pengurutan kode Gray pada baris dan kolom: label berurutan seperti 00, 01, 11, 10 berbeda tepat satu bit. Kedekatan ini memungkinkan Anda melihat kelompok angka 1 (atau 0) secara visual yang dapat digabungkan menjadi satu suku yang disederhanakan.

Untuk n variabel input, peta K-map memiliki 2^n sel. Peta K-map 4 variabel adalah kisi 4×4 dengan 16 sel; peta 5 variabel digambarkan sebagai dua kisi 4×4 yang berdampingan.

SOP vs POS: Bentuk Mana yang Harus Dipilih

Sum of Products (SOP)

SOP mengelompokkan sel-1. Setiap kelompok menjadi produk (AND) dari literal, dan semua kelompok di-OR-kan bersama. Contoh: AB'C + BD. SOP biasanya menjadi standar karena memetakan langsung ke jaringan gerbang AND–OR.

Product of Sums (POS)

POS mengelompokkan sel-0. Setiap kelompok menjadi jumlah (OR) dari literal yang dikomplemenkan, dan semua jumlah di-AND-kan bersama. Contoh: (A + B')(C + D'). POS seringkali lebih kecil ketika fungsi memiliki lebih banyak angka 1 daripada angka 0.

Alat ini menghitung kedua bentuk secara independen — alihkan mode output untuk membandingkan jumlah literal dan pilih mana yang lebih sederhana untuk implementasi Anda.

Aturan Pengelompokan untuk Peta Karnaugh

• Hanya kelompok pangkat dua: kelompok harus berisi 1, 2, 4, 8, atau 16 sel. Kelompok berisi 3 atau 5 tidak diperbolehkan.
• Bentuk persegi panjang: sel dalam satu kelompok membentuk persegi panjang (secara horizontal, vertikal, atau membungkus tepi).
• Kedekatan bungkus-tepi (wrap-around): baris paling atas berdekatan dengan baris paling bawah; kolom paling kiri berdekatan dengan paling kanan. Inilah sebabnya pengurutan kode Gray itu penting.
• Kelompok terbesar terlebih dahulu: kelompok yang lebih besar mengeliminasi lebih banyak variabel, menghasilkan suku produk yang lebih pendek. Kelompok 8 sel menghilangkan 3 variabel; kelompok 4 sel menghilangkan 2; kelompok 2 sel menghilangkan 1.
• Setiap angka 1 harus tercakup: setidaknya satu kelompok harus mencakup setiap sel-1 (untuk SOP) atau sel-0 (untuk POS).
• Tumpang tindih diperbolehkan: angka 1 yang sama dapat dicakup oleh beberapa kelompok jika hal itu menghasilkan kelompok yang lebih besar.
• Don't-care bersifat fleksibel: mereka boleh dikelompokkan jika menghasilkan kelompok yang lebih besar, tetapi tidak harus dicakup.

Implikan Prima dan Implikan Prima Esensial

Implikan prima adalah kelompok yang tidak dapat diperluas lagi — memperbesarnya akan mencakup sel-0 (untuk SOP). Pemecah masalah mencantumkan setiap implikan prima yang ditemukannya. Kemudian ia memilih cakupan minimal: set terkecil dari implikan prima yang mencakup setiap minterm yang diperlukan.

Implikan prima esensial ditandai sebagai ESENSIAL jika ia adalah satu-satunya implikan prima yang mencakup setidaknya satu minterm tertentu. Setiap ekspresi minimal harus menyertakan semua implikan prima esensial. Setelah memilihnya, minterm yang belum tercakup akan ditutupi oleh implikan prima tambahan yang paling efisien.

Kondisi Don't-Care

Don't-care (ditunjukkan sebagai X pada peta K-map) adalah kombinasi input yang outputnya tidak relevan — baik karena tidak pernah terjadi di sirkuit nyata atau nilainya tidak penting. Algoritma bebas memperlakukan setiap X sebagai 0 atau 1, memilih mana yang menghasilkan ekspresi lebih sederhana. Dalam praktiknya, don't-care sering kali mengurangi jumlah literal sebesar 30–60%. Sumber dunia nyata yang umum: dekoder digit desimal yang hanya menggunakan 10 dari 16 kombinasi input empat bit, membiarkan kombinasi 10–15 sebagai don't-care.

Algoritma Quine-McCluskey

Peta K-map adalah metode visual, tetapi untuk lebih dari 4–5 variabel, ia menjadi tidak praktis. Algoritma Quine-McCluskey (QM) adalah padanan tabularnya — secara matematis ketat dan terukur. Pemecah masalah ini menggunakan QM secara internal:

1. Daftar minterm dalam biner, kelompokkan berdasarkan jumlah bit-1.
2. Gabungkan pasangan dari kelompok yang berdekatan (berbeda satu bit), ganti bit yang berbeda dengan tanda pisah. Contoh: 0011 + 0111 → 0-11.
3. Ulangi sampai tidak ada lagi penggabungan yang memungkinkan. Suku yang tidak dapat digabungkan lagi adalah implikan prima.
4. Buat tabel implikan prima — baris adalah implikan prima, kolom adalah minterm yang diperlukan. Identifikasi implikan esensial (kolom dengan tanda centang tunggal).
5. Metode Petrick / pencarian mendalam: untuk minterm sisa yang belum tercakup, temukan set terkecil implikan prima tambahan yang mencakup mereka.

Cara Menggunakan Kalkulator Ini

1. Pilih jumlah variabel: 2, 3, 4, atau 5. Kisi peta K-map akan menyesuaikan secara otomatis.
2. Pilih metode input:
   • Minterm: masukkan indeks di mana F = 1 (misal 1, 3, 5, 7) dan don't-care apa pun.
   • Maxterm: masukkan indeks di mana F = 0. Pemecah masalah akan menghitung sisanya sebagai 1 secara otomatis.
   • Tabel Kebenaran: klik setiap baris untuk mengganti output antara 0, 1, dan X. Sangat cocok untuk desain logika manual.
3. Pilih output SOP atau POS. Bandingkan kedua bentuk dengan beralih — satu bentuk sering kali lebih pendek dari yang lain.
4. Klik Selesaikan. Peta K-map muncul dengan setiap implikan prima dalam warna yang berbeda. Klik chip apa pun untuk memberikan efek denyut pada sel yang dicakupnya.
5. Periksa langkah-langkahnya: perincian Quine-McCluskey menunjukkan bagaimana setiap implikan prima diturunkan dan mana yang esensial.

Contoh Pengerjaan: Fungsi 4-Variabel dengan Don't-Care

Pertimbangkan F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Tanpa don't-care, SOP minimal akan memerlukan beberapa suku. Memperlakukan {0, 2} sebagai 1 memungkinkan pemecah membangun grup 4-sel A'B' (mencakup 0, 1, 2, 3). Memperlakukan 5 sebagai 1 memungkinkan perluasan cakupan CD. Hasil penyederhanaannya adalah:

Hanya 4 literal — turun dari 10+ tanpa trik don't-care. Anda dapat memuat contoh persis ini dengan contoh cepat "4-var dengan Don't-Care" di atas.

Mengapa Meminimalkan Fungsi Boolean?

• Lebih sedikit gerbang = biaya perangkat keras lebih rendah, area chip lebih kecil, konsumsi daya lebih rendah.
• Sirkuit lebih cepat: lebih sedikit penundaan gerbang pada jalur kritis.
• Dokumentasi lebih bersih: ekspresi yang ringkas lebih mudah diverifikasi dan dipelihara.
• Fondasi desain digital: setiap alat sintesis FPGA menjalankan keturunan Quine-McCluskey (Espresso-II, dan versi setelahnya).

Keterbatasan dan Kapan Menggunakan Alat Lain

• Variabel 5+: Peta K-map menjadi berantakan secara visual. Alat ini mendukung hingga 5 dengan membagi menjadi dua peta 4×4. Di luar itu, andalkan langkah-langkah Quine-McCluskey atau gunakan alat sintesis seperti ABC / Espresso.
• Hazard dan glitch: cakupan minimal mungkin mengandung hazard statis. Untuk desain bebas hazard, sertakan implikan prima redundan — alat ini menandainya tetapi tidak menambah cakupan hazard secara otomatis.
• Minimisasi multi-output: jika beberapa fungsi berbagi variabel, minimisasi bersama (berbagi gerbang) menghasilkan perangkat keras yang lebih kecil. Alat ini meminimalkan satu fungsi pada satu waktu.

Pertanyaan yang Sering Diajukan

Apa itu Peta Karnaugh?

Peta Karnaugh (K-map) adalah metode visual untuk meminimalkan ekspresi Boolean. Sel-sel disusun sedemikian rupa sehingga sel yang berdekatan hanya berbeda satu variabel (pengurutan kode Gray). Mengelompokkan angka 1 ke dalam persegi panjang berukuran 1, 2, 4, 8, atau 16 akan menghasilkan ekspresi Sum-of-Products minimal.

Apa perbedaan antara SOP dan POS?

SOP (Sum of Products) mengelompokkan sel-1 dan menghubungkan suku produknya dengan operasi OR, misal A'B + CD. POS (Product of Sums) mengelompokkan sel-0 dan menghubungkan suku jumlahnya dengan operasi AND, misal (A + B')(C' + D). Keduanya mendeskripsikan fungsi yang sama tetapi salah satu bentuk biasanya lebih ringkas.

Apa itu don't-care dan mengapa menggunakannya?

Suku don't-care (ditandai X) adalah kombinasi input yang nilai outputnya tidak relevan — kombinasi tersebut tidak pernah terjadi atau nilainya tidak menjadi masalah. Pemecah masalah dapat menganggapnya sebagai 0 atau 1, mana pun yang menghasilkan ekspresi lebih sederhana. Don't-care sering kali mengurangi jumlah literal secara drastis.

Apa itu implikan prima?

Implikan prima adalah kelompok sel-1 berdekatan terbesar (ukuran pangkat dua) yang tidak dapat diperluas lagi. Implikan prima esensial adalah implikan yang secara unik mencakup setidaknya satu minterm dan harus disertakan dalam setiap ekspresi minimal.

Bagaimana cara kerja algoritma Quine-McCluskey?

Quine-McCluskey adalah padanan tabular dari K-map, cocok untuk banyak variabel. Algoritma ini mencantumkan semua minterm dalam biner, mengelompokkannya berdasarkan jumlah angka 1, dan secara iteratif menggabungkan pasangan yang berbeda tepat satu bit. Suku yang tidak dapat digabungkan lagi adalah implikan prima. Tabel implikan prima kemudian digunakan untuk memilih cakupan minimum.

Berapa banyak variabel yang didukung oleh pemecah K-map ini?

Alat ini mendukung 2 hingga 5 variabel. K-map 5 variabel ditampilkan sebagai dua peta 4×4 yang berdampingan (satu untuk A=0, satu untuk A=1). Di atas 5 variabel, K-map menjadi tidak praktis; gunakan langkah-langkah Quine-McCluskey untuk fungsi yang lebih besar.

Bacaan Lebih Lanjut

• Peta Karnaugh — Wikipedia
• Algoritma Quine-McCluskey — Wikipedia
• Metode Petrick — Wikipedia