K-Map (Karnaugh-Map)

Peta Karnaugh, juga dikenal sebagai K-peta, adalah metode untuk menyederhanakan aljabar boolean ekspresi. Maurice Karnaugh diperkenalkan pada tahun 1953 sebagai penyempurnaan dari Edward Veitch 1952 diagram Veitch 's. Peta Karnaugh mengurangi kebutuhan untuk perhitungan luas dengan mengambil keuntungan dari kemampuan pengenalan pola manusia '. Hal ini juga memungkinkan identifikasi cepat dan penghapusan potensi kondisi ras .

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 dari 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. Sebuah ekspresi sum-of-produk selalu dapat diimplementasikan dengan menggunakan gerbang AND makan menjadi gerbang OR , dan ekspresi produk-of-jumlah mengarah ke gerbang OR makan gerbang AND. ^[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. 

Contoh 

Peta Karnaugh digunakan untuk memfasilitasi penyederhanaan aljabar Boolean fungsi. Sebagai contoh, perhatikan fungsi Boolean dijelaskan sebagai berikut tabel kebenaran .

tabel kebenaran dari fungsi

	SEBUAH	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 $$ {\ displaystyle A} . $$ {\ displaystyle B} . $$ {\ displaystyle C} . $$ {\ displaystyle D} , Dan invers mereka.

• $$ {\ displaystyle f (A, B, C, D) = \ sum _ {} M_ {i}, i \ di \ {6,8,9,10,11,12,13,14 \}} dimana $$ {\ displaystyle M_ {i}} adalah minterm untuk memetakan (yaitu, baris yang memiliki output 1 dalam tabel kebenaran).
• $$ {\ displaystyle f (A, B, C, D) = \ prod _ {} M_ {i}, i \ di \ {0,1,2,3,4,5,7,15 \}} dimana $$ {\ displaystyle M_ {i}} adalah maxterms untuk memetakan (yaitu, baris yang memiliki keluaran 0 di tabel kebenaran).

Peta Karnaugh 

K-peta yang digambar pada torus, dan di pesawat. Sel-sel dot-tanda yang berdekatan.

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 - sebuah 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. Sebagai contoh, $$ {\ displaystyle AD} berarti sel yang meliputi area 2x2 mana $$ {\ displaystyle A} dan $$ {\ displaystyle D} adalah benar, yaitu sel-sel nomor 13, 9, 15, 11 dalam diagram di atas. Di samping itu, $$ {\ displaystyle A {\ overline {D}}} berarti sel-sel di mana $$ {\ displaystyle A} adalah benar dan $$ {\ displaystyle D} adalah palsu (yaitu, $$ {\ displaystyle {\ overline {D}}} adalah 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. Karena itu, $$ {\ displaystyle 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-seperti $$ {\ displaystyle {\ overline {B}} \, {\ overline {D}}} , Yang meliputi empat sudut.

Solusi [ sunting ]

Diagram menunjukkan dua K-peta. K-peta untuk fungsi f (A, B, C, D) ditampilkan sebagai persegi panjang berwarna yang sesuai dengan minterms. Wilayah coklat tumpang tindih merah 2 × 2 persegi dan hijau 4 × 1 persegi panjang. K-peta untuk kebalikan dari f ditampilkan sebagai persegi panjang abu-abu, yang sesuai dengan maxterms.

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. Demikian, $$ {\ displaystyle {\ overline {C}}} harus dimasukkan.
• Perubahan D, sehingga dikecualikan.

Dengan demikian minterm pertama di Boolean sum-of-produk ekspresi $$ {\ displaystyle 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 $$ {\ displaystyle A {\ overline {B}}} . Perhatikan bahwa hal itu dapat diterima bahwa pengelompokan hijau tumpang tindih dengan yang merah.

Dengan cara yang sama, pengelompokan biru memberikan istilah $$ {\ displaystyle BC {\ overline {D}}} .

Solusi dari setiap kelompok digabungkan: bentuk normal dari rangkaian tersebut adalah $$ {\ displaystyle A {\ overline {C}} + A {\ overline {B}} + BC {\ overline {D}}} .

Sehingga peta Karnaugh telah membimbing penyederhanaan

$$ {\ displaystyle {\ begin {selaras} f (A, B, C, D) = {} & {\ overline {A}} BC {\ 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 {selaras}}}

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.

Inverse 

Kebalikan dari fungsi diselesaikan dengan cara yang sama dengan mengelompokkan 0s gantinya.

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

• coklat: $$ {\ displaystyle {\ overline {A}} \, {\ overline {B}}}
• emas: $$ {\ displaystyle {\ overline {A}} \, {\ overline {C}}}
• biru: $$ {\ displaystyle BCD}

Ini menghasilkan terbalik:

$$ {\ displaystyle {\ overline {f (A, B, C, D)}} = {\ overline {A}} \, {\ overline {B}} + {\ overline {A}} \, {\ overline { C}} + BCD}

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

$$ {\ displaystyle {\ begin {selaras} {\ overline {\ overline {f (A, B, C, D)}}} & = {\ overline {{\ overline {A}} \, {\ overline {B} } + {\ overline {A}} \, {\ overline {C}} + BCD}} \\ f (A, B, C, D) & = {\ overline {{\ overline {A}} \, { \ overline {B}} + {\ overline {A}} \, {\ overline {C}} + BCD}} \\ f (A, B, C, D) & = \ kiri (A + B \ right) \ kiri (A + C \ right) \ kiri ({\ overline {B}} + {\ overline {C}} + {\ overline {D}} \ right) \ end {selaras}}}

Jangan peduli [ sunting ]

Nilai f (A, B, C, D) untuk ABCD = 1111 diganti dengan "tidak peduli". Ini menghilangkan istilah hijau sepenuhnya dan memungkinkan istilah merah menjadi lebih besar. Hal ini juga memungkinkan jangka terbalik biru bergeser dan menjadi lebih besar

Peta Karnaugh juga memungkinkan mudah minimizations fungsi yang kebenarannya tabel termasuk " tidak peduli " kondisi. A "tidak peduli" kondisi adalah kombinasi dari input yang desainer tidak peduli apa output adalah. Oleh karena itu, "tidak peduli" kondisi baik dapat dimasukkan dalam atau dikeluarkan dari kelompok persegi panjang, yang mana membuatnya lebih besar. Mereka biasanya ditunjukkan pada peta dengan sedikit atau X.

Contoh di sebelah kanan adalah sama seperti contoh di atas tetapi dengan nilai f (1,1,1,1) diganti dengan "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:

$$ {\ displaystyle f (A, B, C, D) = A + BC {\ overline {D}}}

Perhatikan bahwa istilah pertama hanya $$ {\ displaystyle A} , tidak $$ {\ displaystyle A {\ overline {C}}} . Dalam hal ini, tidak peduli telah menjatuhkan istilah (persegi panjang hijau); disederhanakan lain (yang merah); dan dihapus bahaya ras (menghapus istilah kuning seperti yang ditunjukkan pada bagian berikut tentang bahaya ras).

Kasus terbalik disederhanakan sebagai berikut:

$$ {\ displaystyle {\ overline {f (A, B, C, D)}} = {\ overline {A}} \, {\ overline {B}} + {\ overline {A}} \, {\ overline { C}} + {\ overline {A}}} D

Bahaya ras 

Eliminasi 

Peta Karnaugh berguna untuk mendeteksi dan menghilangkan kondisi ras . Bahaya ras sangat mudah dikenali dengan menggunakan peta Karnaugh, karena kondisi lomba mungkin ada ketika bergerak antara setiap pasangan yang berdekatan, namun menguraikan, daerah dibatasi pada peta. Namun, karena sifat dari Gray coding, yang berdekatan memiliki definisi khusus dijelaskan di atas - kami bahkan pindah torus, bukan persegi panjang, membungkus di sekitar bagian atas, bawah, dan sisi.

• Dalam contoh di atas , kondisi lomba potensial ada ketika C adalah 1 dan D adalah 0, A adalah 1, dan perubahan B dari 1 ke 0 (bergerak dari keadaan biru untuk 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 keadaan biru untuk negara red). Dalam hal ini glitch membungkus di sekitar dari atas peta ke bawah.

bahaya ras yang hadir dalam diagram ini.

Atas diagram dengan istilah konsensus ditambahkan untuk menghindari bahaya balapan.

Apakah gangguan akan benar-benar terjadi tergantung pada sifat fisik pelaksanaan, dan apakah kita perlu khawatir tentang hal itu tergantung pada aplikasi. Dalam logika clock, itu sudah cukup bahwa logika mengendap pada nilai yang diinginkan dalam waktu untuk memenuhi batas waktu waktu. Dalam contoh kita, kita tidak mempertimbangkan logika clock.

Dalam kasus kami, istilah tambahan $$ {\ displaystyle A {\ overline {D}}} akan menghilangkan potensi bahaya ras, menjembatani antara negara-negara keluaran hijau dan biru atau biru dan merah negara keluaran: ini ditampilkan sebagai daerah kuning (yang membungkus di sekitar dari bawah ke atas bagian kanan) dalam diagram yang berdekatan.

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

Demikian pula, istilah tambahan $$ {\ displaystyle {\ overline {A}}} D harus ditambahkan ke terbalik untuk menghilangkan bahaya ras lain yang potensial. Menerapkan hukum De Morgan menciptakan produk lain dari jumlah ekspresi untuk f, tetapi dengan faktor baru $$ {\ displaystyle \ kiri (A + {\ overline {D}} \ right)} .

2-variabel contoh peta [ sunting ]

Berikut ini adalah semua mungkin 2-variabel, 2 × 2 peta Karnaugh. Terdaftar dengan masing-masing adalah minterm sebagai fungsi $$ {\ displaystyle \ sum m ()} dan ras bahaya bebas (lihat sebelumnya bagian ) persamaan minimum. Sebuah minterm didefinisikan sebagai ungkapan yang memberikan bentuk yang paling minim ekspresi variabel dipetakan. Semua horisontal dan vertikal blok yang saling berhubungan yang mungkin dapat dibentuk. blok ini harus dari ukuran kekuatan dari 2 (1, 2, 4, 8, 16, 32, ...). Ekspresi ini membuat pemetaan logis minimal logika ekspresi variabel minimal untuk ekspresi biner untuk dipetakan. Berikut adalah semua blok dengan satu bidang.

Sebuah blok dapat dilanjutkan di bawah, atas, kiri, atau kanan grafik. Yang bahkan dapat membungkus melampaui tepi grafik untuk variabel minimisasi. Hal ini karena masing-masing variabel logika sesuai dengan setiap kolom vertikal dan baris horizontal. Sebuah visualisasi dari k-peta dapat dianggap silinder. Bidang di tepi di kiri dan kanan yang berdekatan, dan bagian atas dan bawah yang berdekatan. K-Maps untuk 4 variabel harus digambarkan sebagai donat atau torus bentuk. Empat sudut alun-alun yang ditarik oleh k-peta yang berdekatan. Masih peta yang lebih kompleks yang dibutuhkan untuk 5 variabel dan banyak lagi.

• 

  $$ {\ displaystyle \ sum _ {}} m (0); K = 0
• 

  $$ {\ displaystyle \ sum _ {}} m (1); K = A 'B'
• 

  $$ {\ displaystyle \ sum _ {}} m (2); K = AB '
• 

  $$ {\ displaystyle \ sum _ {}} m (3); K = A 'B
• 

  $$ {\ displaystyle \ sum _ {}} m (4); K = AB
• 

  $$ {\ displaystyle \ sum _ {}} m (1,2); K = B '
• 

  $$ {\ displaystyle \ sum _ {}} m (1,3); K = A '
• 

  $$ {\ displaystyle \ sum _ {}} m (1,4); K = A 'B' + AB
• 

  $$ {\ displaystyle \ sum _ {}} m (2,3); K = AB '+ A' B
• 

  $$ {\ displaystyle \ sum _ {}} m (2,4); K = A
• 

  $$ {\ displaystyle \ sum _ {}} m (3,4); K = B
• 

  $$ {\ displaystyle \ sum _ {}} m (1,2,3); K = A '+B'
• 

  $$ {\ displaystyle \ sum _ {}} m (1,2,4); K = A + B '
• 

  $$ {\ displaystyle \ sum _ {}} m (1,3,4); K = A '+ B
• 

  $$ {\ displaystyle \ sum _ {}} m (2,3,4); K = A + B
• 

  $$ {\ displaystyle \ sum _ {}} m (1,2,3,4); K = 1