Cara menyederhanakan logika Boolean dengan peta Karnaugh, termasuk kondisi don't-care
Susun peta Karnaugh untuk 2 sampai 4 variabel, buat kelompok yang sah, baca suku produknya, dan manfaatkan don't-care agar jumlah gerbang dan masukan gerbang berkurang.
Peta Karnaugh (K-map) adalah tabel kebenaran yang digambar ulang sebagai kisi, sehingga dua sel bertetangga hanya berbeda pada satu variabel masukan. Menurut ChipVerify, setiap literal (satu kemunculan variabel dalam suku) yang terbuang berarti satu masukan gerbang yang tidak perlu dibangun. Pakai cara ini saat merancang atau merapikan rangkaian logika digital dan logika kontrol.
Panduan STEM Success Center, California State University San Marcos (CSUSM), menyebut ekspresi Boolean 2, 3, atau 4 variabel dapat diminimalkan dengan mudah tanpa teorema aljabar Boolean. Untuk enam variabel dibutuhkan empat peta 4-variabel yang ditumpuk, dan mencari kelompok di sana menjadi tidak andal. Di atas itu, peta tidak praktis.
Langkah
- Pilih peta sesuai jumlah variabel. Lalu tentukan minterm atau maxterm sesuai soal, kata CSUSM. Minterm adalah suku hasil kali untuk kombinasi masukan yang menghasilkan 1, sedangkan maxterm adalah suku jumlah untuk kombinasi yang menghasilkan 0.
- Tulis label dengan kode Gray. Menurut ChipVerify, label baris dan kolom ditulis 00, 01, 11, 10, bukan urutan biner. Pada kode Gray, label bertetangga hanya berbeda satu bit.
- Beri nomor minterm di sudut setiap sel sebelum mengisi nilai. Pada peta 4 variabel, nomor di baris atas berjalan 0, 1, 3, 2, dan di kolom pertama 0, 4, 12, 8. Sel 2 dan 3 tertukar di setiap baris dibanding urutan biasa, begitu juga baris 2 dan 3 (sel 12 sampai 15 berada di atas sel 8 sampai 11).
- Isi peta. Untuk bentuk SOP (jumlah dari hasil kali), isi 1 pada sel yang sesuai minterm dan 0 di tempat lain. Untuk bentuk POS (hasil kali dari jumlah), isi 0 pada sel yang sesuai maxterm dan 1 di tempat lain, menurut CSUSM.
- Buat kelompok persegi panjang. Jumlah sel per kelompok harus pangkat dua, dan jangkau sebanyak mungkin sel dalam satu kelompok. ChipVerify menyebut ukuran yang sah: 1, 2, 4, 8, atau 16 sel, dan kelompok boleh melingkar melewati tepi.
- Baca suku dari tiap kelompok. Lihat setiap variabel di seluruh sel kelompok: variabel yang tetap 1 ditulis apa adanya, yang tetap 0 ditulis komplemennya, dan yang berubah dibuang. Jumlahkan semua suku untuk bentuk SOP.
- Pilih kelompok dengan prosedur yang andal. ChipVerify menganjurkan mencari semua prime implicant (kelompok terbesar yang mungkin), mengambil semua essential prime implicant, lalu menutup angka 1 yang tersisa dengan prime implicant tambahan sesedikit mungkin.
- Periksa hasilnya. Cocokkan dengan penyederhanaan aljabar, misalnya untuk F = A'B'C' + A'B'C + A'BC'.
Aturan pengelompokan
CSUSM merangkum aturannya: tidak boleh ada nol dalam kelompok, tidak boleh diagonal, jumlah sel pangkat dua, kelompok sebesar mungkin, setiap angka 1 masuk minimal satu kelompok, tumpang tindih boleh, melingkar tepi boleh, dan jumlah kelompok sesedikit mungkin.
ChipVerify menambahkan bahwa tepi kiri dan kanan saling bertetangga, begitu juga tepi atas dan bawah. Akibatnya, empat sel pojok pada peta 4 variabel membentuk satu kelompok berisi empat sel. Kelompok 3 sel, bentuk L, dan sel diagonal tidak sah.
Berapa literal yang tersisa
Tabel berikut dari ChipVerify untuk peta 4 variabel:
| Ukuran kelompok | Literal tersisa dalam suku |
|---|---|
| 1 sel | 4 |
| 2 sel | 3 |
| 4 sel | 2 |
| 8 sel | 1 |
| 16 sel | 0 (F = 1) |
Contoh 3 variabel
Contoh dari ChipVerify: F(A,B,C) = Σm(0,1,2). Kelompok sel 0 dan 1 menghasilkan A'B'. Kelompok sel 0 dan 2, yang melintasi tepi, menghasilkan A'C'. Jadi F = A'B' + A'C'.
Sel 0 dipakai oleh kedua kelompok. Tumpang tindih diperbolehkan karena setara dengan menulis suku dua kali (X + X = X).
Bentuk POS
Menurut ChipVerify, kelompokkan angka 0, bukan angka 1. Hasilnya adalah SOP untuk F'. Komplemenkan hasil itu dengan teorema De Morgan untuk mendapat POS dari F. Bila suku jumlah dibaca langsung dari kelompok 0, konvensinya berkebalikan: variabel yang tetap 0 ditulis apa adanya, dan yang tetap 1 ditulis komplemennya.
Memakai kondisi don't-care
Don't-care (X) adalah nilai keluaran yang tidak penting, karena kombinasi masukan itu tidak pernah muncul atau keluarannya tidak dipakai. ChipVerify menjelaskan bahwa setiap X boleh dianggap 1 bila membuat kelompok lebih besar, selain itu dianggap 0. X tidak wajib ditutup.
Contoh dari ChipVerify: rangkaian menerima digit BCD (0 sampai 9) pada masukan ABCD dan memberi keluaran 1 bila digit 5 atau lebih. Kode 10 sampai 15 tidak pernah muncul pada BCD, sehingga menjadi don't-care.
| Kondisi | Hasil | Ukuran |
|---|---|---|
| Tanpa don't-care | F = AB'C' + A'BD + A'BC | 3 suku, 9 literal |
| Dengan don't-care | F = A + BD + BC | 3 suku, 5 literal |
Kesalahan yang sering terjadi
- Label berurutan biner. Dengan urutan 00, 01, 10, 11, sel tengah berbeda pada dua variabel, kelompok yang melintasinya tidak sah, dan hasilnya salah, kata ChipVerify. Periksa bahwa label bertetangga hanya berbeda satu bit.
- Mengisi peta 4 variabel menurut urutan nomor biasa. ChipVerify menyebut urutan yang salah saat mengisi sebagai sumber kesalahan K-map yang paling sering. Tulis nomor minterm dulu di tiap sel.
- Kelompok berukuran 3, 5, atau 6 sel. Himpunan seperti itu tidak sesuai dengan satu suku produk mana pun. Pecah menjadi persegi panjang sah yang saling tumpang tindih.
- Melewatkan tepi dan empat pojok. Akibatnya kelompok lebih kecil dan literal lebih banyak.
- Mempertahankan kelompok yang semua angka 1-nya sudah tertutup kelompok lain. Kelompok semacam itu mubazir. Ambil essential prime implicant lebih dulu, lalu tambah hanya yang masih diperlukan.
- Menambah kelompok khusus untuk X. Masukkan X hanya bila membuat kelompok lebih besar. Kelompok yang hanya berisi X, atau kelompok tambahan hanya untuk menutup X, menambah logika tanpa guna.
- Menganggap jawaban minimal pasti tunggal. Bentuk minimal tidak selalu unik. Dua jawaban bisa sama kecilnya, dan perancang atau alat tinggal memilih salah satu.
Peringatan don't-care dan batas peta
ChipVerify mengingatkan bahwa perilaku perangkat keras untuk masukan don't-care adalah apa pun yang dipilih alat. Jika masukan yang dianggap mustahil ternyata bisa muncul, misalnya akibat bit flip atau glitch reset, respons rangkaian tidak terencana.
Peta juga punya batas. ChipVerify menyebut XOR 4 masukan (paritas ganjil) membentuk pola papan catur, dengan tidak ada dua angka 1 yang bertetangga. Pola papan catur, utuh atau sebagian, menandakan fungsi XOR atau XNOR. K-map hanya menemukan bentuk AND-OR dua tingkat terbaik, sedangkan struktur XOR dan faktorisasi bertingkat di luar jangkauannya.
Untuk 5 variabel, ChipVerify menggambar dua peta 4-variabel, satu untuk A = 0 dan satu untuk A = 1. Sel di posisi yang sama bertetangga, dan kelompok yang muncul di tempat yang sama pada kedua peta kehilangan variabel A.