Aljabar Boolean, Penyederhanaan Logika, dan Peta Karnaugh
Rahma Putriyana
2303015068
2D - Teknik Informatika
Sistem Digital dan Gelombang
Metode K-map untuk menyelesaikan ekspresi logika disebut sebagai teknik grafis untuk menyederhanakan ekspresi boolean. K-map juga disebut sebagai tabel kebenaran 2D karena setiap K-map tidak lain hanyalah format berbeda yang mewakili nilai-nilai yang ada dalam tabel kebenaran satu dimensi.
K-maps pada dasarnya berkaitan dengan teknik memasukkan nilai variabel keluaran ke dalam sel dalam kotak persegi panjang atau persegi menurut pola tertentu. Jumlah sel dalam K-map ditentukan oleh jumlah variabel masukan dan secara matematis dinyatakan sebagai dua pangkat dari jumlah variabel masukan, yaitu 2 n , dimana jumlah variabel masukan adalah n.
Jadi, untuk menyederhanakan ekspresi logika dengan dua masukan, kita memerlukan K-map dengan 4 (= 2 2 ) sel. Ekspresi logis empat masukan akan menghasilkan peta K-sel 16 (= 2 4 ), dan seterusnya.
Gray Coding
Selanjutnya, setiap sel dalam K-map memiliki nilai tempat tertentu yang diperoleh dengan menggunakan teknik pengkodean yang dikenal sebagai gray code.
Keistimewaan kode ini adalah kenyataan bahwa nilai kode yang berdekatan hanya berbeda satu bit. Artinya, jika kata kode yang diberikan adalah 01, maka kata sandi sebelumnya dan berikutnya dapat berupa 11 atau 00, dalam urutan apa pun, namun tidak boleh 10 dalam hal apa pun.
Di K-maps, baris dan kolom tabel menggunakan pelabelan gray code yang pada gilirannya mewakili nilai variabel input terkait. Ini berarti bahwa setiap sel K-map dapat dialamatkan menggunakan Gray Code-Word yang unik.
Konsep-konsep ini selanjutnya ditekankan oleh peta K 16 sel yang ditunjukkan pada Gambar 1, yang dapat digunakan untuk menyederhanakan ekspresi logis yang terdiri dari 4 variabel (A, B, C, dan D disebutkan di sudut kiri atas) .
Gambar 1. Peta Karnaugh yang khas namun kosong dengan 16 sel
Di sini baris dan kolom K-map diberi label menggunakan kode Gray 2-bit, yang ditunjukkan pada gambar, yang memberikan alamat pasti untuk setiap selnya.
Misalnya, sel K-map berwarna abu-abu yang ditampilkan dapat dialamatkan menggunakan kata kode "0101" yang setara dengan 5 dalam desimal (ditunjukkan sebagai angka hijau pada gambar) dan sesuai dengan kombinasi variabel masukan A̅BC̅D atau A+B̅+C+D̅, bergantung pada apakah hubungan input-output masing-masing dinyatakan dalam bentuk SOP (jumlah produk) atau bentuk POS (produk jumlah). Demikian pula, AB̅CD atau A̅+B+C̅+D̅ mengacu pada kata kode Gray "1011", setara dengan 11 dalam desimal (sekali lagi, ditunjukkan dalam warna hijau pada gambar), yang berarti kita menangani warna merah muda- sel K-map berwarna pada gambar.
Teknik Penyederhanaan K-Map
Dengan gambaran umum K-maps ini, sekarang mari kita beralih ke prosedur yang digunakan dalam merancang sistem digital yang optimal (dalam hal jumlah gerbang logika yang digunakan untuk merealisasikan logika). Kita akan mulai dengan pernyataan masalah tertentu.
Contoh 1:
Rancang sistem digital yang keluarannya didefinisikan sebagai rendah secara logis jika bilangan biner masukan 4-bit adalah kelipatan 3; jika tidak, outputnya akan tinggi secara logis. Output ditentukan jika dan hanya jika bilangan biner input lebih besar dari 2.
Langkah 1: Tabel Kebenaran / Ekspresi Kanonik yang Mengarah ke Syarat Min atau Maks
Langkah pertama dalam merancang sistem digital apa pun adalah memiliki gagasan yang jelas tentang variabel-variabel yang terlibat dalam proses tersebut, beserta nilai-nilai statusnya. Selanjutnya, bergantung pada rumusan masalahnya, kita harus sampai pada jumlah variabel keluaran dan nilainya untuk setiap kombinasi literal masukan, yang dapat dengan mudah direpresentasikan dalam bentuk tabel kebenaran.
Dalam contoh yang diberikan:
- Banyaknya variabel masukan = 4, yang kita sebut A, B, C, dan D.
- Banyaknya variabel keluaran = 1, yang kita sebut Y.
Di mana:
- Y = “Tidak Peduli,” jika angka yang dimasukkan kurang dari 3 (entri oranye pada tabel kebenaran)
- Y = 0, jika bilangan masukan merupakan kelipatan integral 3 (entri berwarna hijau pada tabel kebenaran)
- Y = 1, jika bilangan masukan bukan kelipatan integral 3 (entri biru pada tabel kebenaran)
Tabel 1. Tabel kebenaran
Perhatikan bahwa, selain kolom masukan dan keluaran, tabel kebenaran juga memiliki kolom yang memberikan ekuivalen desimal dari kombinasi biner masukan, yang memudahkan kita mendapatkan perluasan minterm atau maxterm untuk soal yang diberikan. Jadi untuk contoh yang diberikan:
- Ekspansi mintermnya adalah ∑ m (4,5,7,8,10,11,13,14) + ∑ d (0,1,2)
- Ekspansi maksimumnya adalah ∏ M (3,6,9,12,15) · ∏ D (0,1,2)
Namun terkadang ungkapan logika yang ingin disederhanakan bisa langsung diberikan dalam bentuk SOP atau POS. Dalam hal ini, persyaratan tabel kebenaran dapat diabaikan asalkan kita menyatakan ekspresi yang diberikan dalam bentuk kanoniknya, yang darinya dapat diperoleh minterms atau maxterms yang sesuai.
Langkah 2: Pilih dan Isi K-Map
Dari Langkah 1, kita mengetahui jumlah variabel masukan yang terlibat dalam ekspresi logika yang akan menentukan ukuran K-map yang diperlukan. Selanjutnya kita juga mengetahui jumlah K-map yang diperlukan untuk merancang sistem yang diinginkan karena jumlah variabel keluaran juga akan diketahui secara pasti. Artinya, untuk contoh yang dipertimbangkan, kita memerlukan satu peta K (karena satu variabel keluaran) dengan 16 sel (karena ada empat variabel masukan).
Selanjutnya, kita harus mengisi sel K-map dengan satu untuk setiap minterm, nol untuk setiap maxterm, dan X untuk istilah "Jangan Peduli". Prosedur ini harus diulangi untuk setiap variabel keluaran. Untuk contoh ini, kita mendapatkan K-map seperti yang ditunjukkan pada Gambar 2.
Gambar 2. K- map
Langkah 3: Bentuk Grup
Penyederhanaan K-map juga bisa disebut sebagai teknik “penyederhanaan dengan pengelompokan” karena hanya mengandalkan pembentukan cluster. Artinya, tujuan utama dari keseluruhan proses adalah untuk mengumpulkan sebanyak mungkin angka (untuk solusi SOP) atau angka nol (untuk solusi POS) di bawah satu atap untuk setiap variabel keluaran dalam masalah yang disebutkan. Namun, saat melakukan hal tersebut, kita harus benar-benar mematuhi peraturan dan ketentuan tertentu:
- Prosesnya harus dimulai dengan mengelompokkan bit-bit yang terletak pada sel yang berdekatan sedemikian rupa sehingga kelompok yang terbentuk berisi jumlah maksimum bit yang dipilih. Artinya untuk K-map n -variabel dengan 2 n sel, cobalah mengelompokkan 2 n sel terlebih dahulu, lalu untuk 2 n -1 sel, selanjutnya untuk 2 n -2 sel, dan seterusnya hingga “grup” tersebut berisi hanya 2 0 sel, yaitu bit terisolasi (jika ada). Perhatikan bahwa jumlah sel dalam grup harus sama dengan bilangan bulat pangkat 2, yaitu 1, 2, 4, 8. . . .
- Prosedur ini harus diterapkan untuk semua sel yang berdekatan pada K-map, meskipun sel tersebut tampak tidak berdekatan—baris atas dianggap berdekatan dengan baris bawah dan kolom paling kanan dianggap berdekatan dengan kolom paling kiri. jika K-map melingkar dari atas ke bawah dan kanan ke kiri. Misalnya, solusi bentuk SOP Kelompok 1 pada Tabel 2.
- Sedikit yang muncul dalam satu grup dapat diulangi di grup lain asalkan hal ini menyebabkan peningkatan ukuran grup yang dihasilkan. Misalnya, sel 5 diulangi di Grup 3 dan 4 dalam solusi bentuk SOP pada Tabel 2 karena menghasilkan pembentukan grup dengan dua sel, bukan grup dengan hanya satu sel.
- Kondisi “Tidak Peduli” harus dipertimbangkan untuk kegiatan pengelompokan jika dan hanya jika kondisi tersebut membantu memperoleh kelompok yang lebih besar. Kalau tidak, mereka akan diabaikan. Di sini istilah "Jangan Peduli" di sel 0 dan 1 dianggap menciptakan bentuk solusi SOP Grup 2 karena menghasilkan grup dengan empat sel, bukan hanya dua.
Meja 2.
| | Solusi Formulir SOP | Solusi Formulir POS |
| Jumlah kelompok yang memiliki 16 sel | 0 | 0 |
| Banyaknya kelompok yang mempunyai 8 sel | 0 | 0 |
| Jumlah kelompok yang memiliki 4 sel (Lampiran Biru pada Gambar 3) | 2 | Grup 1 (Sel 0,2,8,10) | 1 | Grup 1 (Sel 0,1,2,3) |
| Grup 2 (Sel 0,1,4,5) |
| Jumlah grup yang memiliki 2 sel (Lampiran Oranye pada Gambar 3) | 4 | Grup 3 (Sel 5,7) | Grup 4 (Sel 5,13) | 2 | Grup 2 (Sel 1,9) |
| Grup 5 (Sel 10,11) | Grup 6 (Sel 10,14) | Grup 3 (Sel 2,6) |
| Jumlah kelompok yang memiliki 1 sel (Lampiran Hijau pada Gambar 3) | 0 | 2 | Grup 4 (Sel 12) |
| Grup 5 (Sel 15) |
Jadi, untuk contoh yang dipertimbangkan, K-map yang menunjukkan kelompok-kelompok tersebut dapat diperoleh seperti yang diberikan pada Gambar 3 yang informasinya dirangkum dalam Tabel 1.
Gambar 3. K-maps dikelompokkan untuk (a) solusi SOP dan (b) solusi POS
Langkah 4: Ekspresi Logis yang Disederhanakan
Untuk setiap kelompok yang dihasilkan, kita harus mendapatkan ekspresi logis yang sesuai untuk variabel masukan. Hal ini dapat dilakukan dengan mengekspresikan bit-bit yang umum di antara kata-kata kode Gray yang mewakili sel-sel yang terdapat dalam kelompok yang dipertimbangkan. Cara lain untuk mendeskripsikan proses memperoleh ekspresi logika yang disederhanakan untuk suatu grup adalah dengan menghilangkan variabel yang bit-bitnya terkait muncul dalam grup sebagai 0 dan 1.
Terakhir, semua ekspresi logis berdasarkan grup ini perlu digabungkan dengan tepat untuk membentuk persamaan Boolean yang disederhanakan untuk variabel keluaran. Prosedur yang sama harus diulangi untuk setiap variabel keluaran dari masalah yang diberikan.
Misalnya, dalam contoh yang dipertimbangkan, istilah logis untuk Grup 2 dari solusi bentuk SOP diperoleh sebagai A̅C̅. Hal ini karena grup ini memiliki 0 sebagai bit kata kode Gray yang umum baik di sepanjang baris maupun kolomnya, yang disorot pada Gambar 4(a). Ini memberi kita literal A̅ dan C̅.
Demikian pula, dalam kasus solusi bentuk POS Grup 1, kita dapat memperoleh ekspresi logis sebagai A+B. Hal ini karena grup tersebut memiliki kata-kata kode Gray yang umum sebesar 0,0 di sepanjang barisnya saja (tidak ada bit kata-kode yang umum di sepanjang kolomnya) yang sesuai dengan variabel masukan A dan B.
Gambar 4. Teknik penyederhanaan K-map untuk (a) solusi SOP dan (b) solusi POS
Mengikuti proses yang sama, kita dapat memperoleh suku logika yang sesuai dengan masing-masing kelompok untuk akhirnya membentuk ekspresi logika untuk keluaran tertentu, seperti yang ditunjukkan pada Tabel 3.
Tabel 3.
| Solusi Formulir SOP | Solusi Formulir POS |
| Grup | Ekspresi Logis | Grup | Ekspresi Logis |
| Grup 1 | B̅D̅ | Grup 1 | A+B |
| Grup 2 | AC̅ | Grup 2 | B+C+D̅ |
| Kelompok 3 | A̅BD | Kelompok 3 | A+C̅+D |
| Kelompok 4 | SM̅D | Kelompok 4 | A̅+B̅+C+D |
| Grup 5 | AB̅C | Grup 5 | A̅+B̅+C̅+D̅ |
| Kelompok 6 | ACD̅ | | |
| Jadi, Y = B̅D̅ + A̅C̅ + A̅BD + BC̅D + AB̅C + ACD̅ | Jadi, Y = (A+B) (B+C+D̅) (A+C̅+D) (A̅+B̅+C+D) (A̅+B̅+C̅+D̅) |
Langkah 5: Desain Sistem
Setelah memperoleh ekspresi logika yang disederhanakan, kita dapat memutuskan jenis dan jumlah gerbang yang diperlukan untuk mewujudkan logika yang diharapkan untuk setiap bit keluaran, yang selanjutnya menghasilkan desain lengkap dari sistem yang diinginkan.
Dengan demikian, sistem digital yang sesuai dengan bentuk solusi SOP dan POS untuk contoh yang diberikan dapat dirancang menggunakan gerbang dasar seperti NOT, AND, dan OR seperti yang ditunjukkan pada Gambar 5(a) dan 5(b).
Gambar 5. Sistem digital sesuai dengan (a) bentuk solusi SOP dan (b) bentuk solusi POS
.jpeg)
.gif)
