Peta Karnaugh, juga dikenal sebagai K-peta, adalah metode untuk menyederhanakan ekspresi aljabar boolean. Maurice Karnaugh diperkenalkan pada tahun 1953 sebagai penyempurnaan dari 1.952 diagram Veitch Edward Veitch ini. Peta Karnaugh mengurangi kebutuhan untuk perhitungan luas dengan mengambil keuntungan dari kemampuan pengenalan pola manusia '. Hal ini juga memungkinkan identifikasi cepat dan penghapusan kondisi ras potensial.
Hasil boolean yang diperlukan ditransfer dari tabel kebenaran ke grid dua dimensi di mana sel-sel yang diperintahkan dalam kode Gray, dan setiap posisi sel merupakan satu kombinasi dari kondisi input, sementara setiap nilai sel mewakili nilai output yang sesuai. kelompok optimal 1s atau 0s diidentifikasi, yang merupakan syarat dari bentuk kanonik logika dalam tabel kebenaran yang asli. [1] Istilah-istilah ini dapat digunakan untuk menulis ekspresi boolean minimal mewakili logika yang diperlukan.
peta Karnaugh digunakan untuk menyederhanakan persyaratan logika dunia nyata sehingga mereka dapat diimplementasikan dengan menggunakan jumlah minimum gerbang logika fisik. Sebesar-of-produk ekspresi selalu dapat diimplementasikan dengan menggunakan gerbang AND makan ke sebuah gerbang OR, dan ekspresi produk-of-jumlah mengarah ke gerbang OR makan sebuah gerbang. [2] peta Karnaugh juga dapat digunakan untuk menyederhanakan ekspresi logika dalam desain software. kondisi Boolean, seperti yang digunakan misalnya dalam pernyataan bersyarat, bisa menjadi sangat rumit, yang membuat kode sulit untuk membaca dan untuk mempertahankan. Setelah diminimalkan, kanonik sum-of-produk dan produk-of-jumlah ekspresi dapat diimplementasikan secara langsung menggunakan AND dan OR operator logika.
tabel kebenaran dari fungsi
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
Berikut adalah dua notasi yang berbeda menggambarkan fungsi yang sama dalam aljabar Boolean unsimplified, menggunakan variabel Boolean A, B, C, D, dan invers mereka.
f (A, B, C, D) = \ sum _ {} m_i, i \ di \ {6, 8, 9, 10, 11, 12, 13, 14 \} di mana m_i adalah minterm untuk memetakan (yaitu, baris yang memiliki output 1 dalam tabel kebenaran).
f (A, B, C, D) = \ prod _ {} M_i, i \ di \ {0, 1, 2, 3, 4, 5, 7, 15 \} di mana M_i adalah maxterms untuk memetakan (yaitu, baris yang memiliki keluaran 0 di tabel kebenaran).
konstruksi K-peta. Alih-alih mengandung nilai-nilai output, diagram ini menunjukkan jumlah output, oleh karena itu tidak peta Karnaugh.
Dalam tiga dimensi, satu dapat menekuk persegi panjang ke torus.
Dalam contoh di atas, empat variabel input dapat dikombinasikan dalam 16 cara yang berbeda, sehingga tabel kebenaran memiliki 16 baris, dan peta Karnaugh memiliki 16 posisi. Peta Karnaugh karena itu diatur dalam 4 × 4 kotak.
Baris dan kolom indeks (ditampilkan di bagian atas, dan di sisi kiri dari peta Karnaugh) yang diperintahkan dalam kode Gray daripada urutan numerik biner. Kode Gray memastikan bahwa hanya satu perubahan variabel antara setiap pasangan sel yang berdekatan. Setiap sel dari peta Karnaugh selesai berisi digit biner yang mewakili output fungsi untuk kombinasi input.
Setelah peta Karnaugh telah dibangun, digunakan untuk menemukan salah satu bentuk yang paling sederhana - bentuk kanonik - untuk informasi dalam tabel kebenaran. 1s berdekatan di peta Karnaugh merupakan peluang untuk menyederhanakan ekspresi. Minterm ( 'istilah minimal') untuk ekspresi akhir ditemukan oleh mengelilingi kelompok 1s di peta. kelompok minterm harus persegi panjang dan harus memiliki luas yang merupakan kekuatan dua (yaitu, 1, 2, 4, 8 ...). persegi panjang minterm harus sebesar mungkin tanpa mengandung 0s apapun. Kelompok mungkin tumpang tindih untuk membuat masing-masing lebih besar. Pengelompokan optimal dalam contoh di bawah ini ditandai dengan garis hijau, merah dan biru, dan kelompok merah dan hijau tumpang tindih. Kelompok merah adalah 2 × 2 persegi, kelompok hijau adalah 4 × 1 persegi panjang, dan daerah tumpang tindih ditunjukkan dalam coklat.
Sel-sel yang sering dilambangkan dengan singkatan yang menggambarkan nilai logis dari input bahwa sel mencakup. Misalnya, AD akan berarti sel yang meliputi area 2x2 di mana A dan D adalah benar, yaitu sel-sel nomor 13, 9, 15, 11 dalam diagram di atas. Di sisi lain, A \ overline {D} berarti sel-sel di mana A adalah benar dan D adalah palsu (yaitu, \ overline {D} benar).
grid toroidally terhubung, yang berarti bahwa kelompok persegi panjang bisa membungkus seluruh tepi (lihat gambar). Sel di sebelah kanan ekstrim sebenarnya 'berdekatan' untuk orang-orang di paling kiri; sama, sehingga orang-orang di bagian paling atas dan orang-orang di bagian bawah. Oleh karena itu, A \ overline {D} bisa menjadi valid jangka itu termasuk sel 12 dan 8 di atas, dan membungkus ke bawah untuk memasukkan sel 10 dan 14-sebagaimana adanya \ overline {B} \, \ overline {D} , yang meliputi empat sudut.
Setelah peta Karnaugh telah dibangun dan 1s yang berdekatan dihubungkan oleh kotak persegi panjang dan persegi, minterm aljabar dapat ditemukan dengan memeriksa yang variabel tetap sama dalam setiap kotak.
Untuk pengelompokan merah:
A adalah sama dan sama dengan 1 seluruh kotak, oleh karena itu harus dimasukkan dalam aljabar representasi dari minterm merah.
B tidak mempertahankan negara yang sama (itu bergeser dari 1 ke 0), dan karenanya harus dikeluarkan.
C tidak berubah. Itu selalu 0, sehingga yang melengkapi, TIDAK-C, harus dimasukkan. Dengan demikian, \ overline {C} harus dimasukkan.
Perubahan D, sehingga dikecualikan.
Dengan demikian minterm pertama di Boolean sum-of-produk ekspresi adalah A \ overline {C}.
Untuk pengelompokan hijau, A dan B mempertahankan negara yang sama, sementara C dan D perubahan. B adalah 0 dan harus menegasikan sebelum dapat disertakan. Oleh karena itu istilah kedua adalah Sebuah \ overline {B}. Catatan itu baik-baik saja bahwa pengelompokan hijau tumpang tindih dengan yang merah.
Dengan cara yang sama, pengelompokan biru memberikan istilah BC \ overline {D}.
Solusi dari setiap kelompok digabungkan: bentuk normal dari rangkaian tersebut adalah A \ overline {C} + A \ overline {B} + BC \ overline {D}.
Sehingga peta Karnaugh telah membimbing penyederhanaan
\ Begin {menyelaraskan}
f (A, B, C, D) = {} & \ overline {A} SM \ overline {D} + A \ overline {B} \, \ overline {C} \, \ overline {D} + A \ overline {B} \, \ overline {C} D + A \ overline {B} C \ overline {D} + {} \\
& A \ overline {B} CD + AB \ overline {C} \, \ overline {D} + AB \ overline {C} D + ABC \ overline {D} \\
= {} & A \ overline {C} + A \ overline {B} + BC \ overline {D}
\ End {menyelaraskan}
Hal ini juga akan mungkin untuk mendapatkan penyederhanaan ini dengan hati-hati menerapkan aksioma aljabar boolean, tapi waktu yang dibutuhkan untuk melakukan itu tumbuh secara eksponensial dengan jumlah istilah.
0 komentar:
Posting Komentar