Karnaugh haritası (Karnaugh map)

Yazan: Şadi Evren ŞEKER

Bool cebirinde verilen mantıksal gösterimleri sadeleştirmek için kullanılan haritadır. Buna göre bir mantıksal devrenin eleman sayısını azaltmak için de kullanılabilir. Örneğin 3 girişli (3 adet farklı binary (ikili) giriş değeri (0 veya 1 olabilen)) devrede kullanılan “ve” ve “veya” kapılarının sayısını azaltabiliriz.

Bu yöntemde giriş değerlerinin alabileceği bütün alternatifler bir tablo üzerinde gösterilerek bu alternatiflerden hangilerinde çıkış olması isteniyorsa bu değerlere 1 yazılır. Sonuçta yazılı olan 1 rakamları arasında komşuluk incelemesi yapılarak sadeleştirilirler.

[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/karnaugh.flv /]

Örneğin iki girişi olan bir devredeki girişler A ve B olsun ve istenilen çıkış değeri F aşağıdaki şekilde verilmiş olsun:
F= A’B + AB
Yukarıdaki terime bakıldığında, bool cebirinin temel özellikleri kullanılarak (ortak parantez):
F=(A’+A) B
sonucuna varılabilir. Bu eşitlik de sadeleştirilerek (bir girişin tersiyle veyası 1’dir)
F=B
sonucuna varılabilir. Demek ki ilk verilen eşitlikte A terimleri fazla terimlerdi. Ancak bunu görmek her zaman kolay olmamaktadır. Özellikle de giriş sayıları arttıkça çok sayıda işlem yapmak ve sade hali elde etmek zahmetli olmaktadır. Ve ne kadar sadeleşirse sadeleşsin en sade forma erişilip erişilmediği her zaman muamma olarak kalmaktadır. Kesin ve her durum için geçerli olması açısından bu sadeleştirme işlemi karnough haritaları ile aşağıdaki şekilde yapılabilir:
1) Öncelikle istenilen devrenin doğruluk çizelgesi (truth table) çizilir.

A B F
- - -
0 0 0
0 1 1
1 0 0
1 1 1

yukarıdaki tablo F= A’B+AB eşitliğinin doğruluk çizelgesidir (truth table) . Bu tabloda dikkat edileceği üzere giriş değerleri olan A ve B için alınabilecek bütün alternatifler listelenmiş ve her alternatif için F çıkış değerinin karşılığı yazılmıştır. Yani örneğin tablonun ilk satırı için F= A’B + AB eşitliğinde A yerine 0 ve B yerine 0 yazılarak sonuç hesaplanmış ve tabloya yazılmıştır.

Sonuçta çıkan tabloyu karnough haritası olarak çizecek olursak aşağıdaki şekilde bir tablo bulunur:
2×2 lik karnough haritası

Bu tabloda her hücrenin anlamı doğruluk çizelgesindeki (truth table) bir değere karşılık gelmesidir. Yani doğruluk çizelgesini (truth table) yeniden çizecek olursak bu tablodaki değerlerin karşılığı olan hücre numaraları aşağıdaki şekilde listelenebilir:


A B F Tablo Adresi
- - - -----------
0 0 0 0
0 1 1 1
1 0 0 2
1 1 1 3

Yukarıdaki tabloda, tablo adresleri aslıdan A ve B bitleri ikilik tabanda yanyana yazıldığında elde edilen 2 haneli ikilik tabandaki sayıların 10luk tabandaki karşılıklarıdır. Aşağıda, karnaugh haritasındaki her hücrenin ikili ve onlu tabandaki adresleri verilmiştir:

karnaugh haritası (karnaugh map) 2li tabandaki adresler 2li tabandaki adresler. (bu adresler basitçe satır ve sütun karşılıklarının okunaması ile elde edilir.)

karnaugh haritası (karnaugh map) 10luk tabandaki adresler
10luk tabandaki adresler. (bu adresler basitçe bir önceki tablodaki ikilik sayıların 10luk sisteme çevrilmesi ile elde edilir.)

Dolayısıyla yukarıda bulunan doğruluk çizelgesini yukarıdaki adreslere göre yerleştirmek de mümkündür. Yani doğruluk çizelgesindeki adres değeri 1, haritadaki 1 numaralı adrese şeklinde.

Şimdi örnek problem olan F= A’B + AB eşitliğini karnaugh haritası ile çözmek istediğimizi düşünelim. Yapılması gereken basitçe aşağıdaki şekilde olduğu gibi haritasını çizmek ve komşu olan 1 leri işaretlemektir. (daha ileride de anlatılacağı gibi komşuluk aranırken 2’nin üstü olan 2 4 8 16 gibi sayıdaki 1’lerin komşuluğuna bakılır)
F= A’B + AB eşitliği için çözüm haritası
Bu haritada komşu olan 1’ler işaretlendikten sonra ortak ortaya çıkan adanın terimleri okunur. Buna göre bu ada için A değeri değişkenlik göstermektedir. Yani çember içine aldığımız adamız, A 1 iken ve 0 iken geçerlidir. Bu durumda sonuçta A terimi olması beklenemez çünkü A’nın aldığı terimler sonucu etkilememektedir. B terimi incelendiğinde, bu terimin bütün ada için 1 olduğu görülür. Öyleyse sonuç B’dir denilebilir.

Karnaugh haritalarını 2’den fazla giriş için de kullanmak mümkündür. (Şimdiye kadar olanlar 2lik tabandaydı).
Örneğin 3 giriş için aşağıdaki harita kullanılabilir:
3 girişli karnaugh haritası
yukarıdaki şekilde 3 girişli (A,B ve C girişleri için) bir karnaugh haritası verilmiştir. Bu haritada her girişin alabileceği değerler gösterilmiştir. (giriş değerleri ikili tabanda olduğu için 2 alternatif olan 0 veya 1 değerlerini alabilirler) Buna göre üç giriş için 8 (2 üzeri 3) alternatif bulunmaktadır, ve her alternatif tabloda gösterilmiştir.
Yukarıdaki tablo’nun mantıksal değerler için gösterimi aşağıda verilmiştir:
3 girişli karnaugh haritasının mantıksal karşılığı
yukarıdaki şekilde 3 girişli (A,B ve C girişleri için) bir karnaugh haritası verilmiştir. Bu haritada her girişin alabileceği değerler gösterilmiştir. (giriş değerleri ikili tabanda olduğu için 2 alternatif olan 0 veya 1 değerlerini alabilirler bu değerlerin anlamı o girişin kendisinin veya tersinin alınması durumunda 1 çıkacağıdır) Buna göre üç giriş için 8 (2 üzeri 3) alternatif bulunmaktadır, ve her alternatif tabloda gösterilmiştir. Bu hücrelerin her birisinde ilgili girişin karşılığı olan mantıksal önerme yer almaktadır. Örneğin tablonun sol üst köşesinde bütün girişler 0 değerinde olduğu için bu hücrenin 1 olmasını sağlayacak mantıksal önerme mutlaka bütün girişlerin tersinin ve mantıksal bağlacı ile bağlanmış hali olmalıdır.

Aşağıda giriş sayısının 4 olması durumunda karnaugh haritasının mantıksal gösterimleri veirlmiştir:
karnaugh

Aşağıdaki tablo yukarıdaki şekilde düzeltildi. Aşağıdaki tablo hatalı ve yukarıdaki tablo doğrudur. Detay için yorum kısmına bakabilirsiniz. Uyarısı için yekta beye teşekkür ederim.

4 girişli karnaugh haritası

Karnaugh Haritasında asgari terimlerin kullanımı (Minterms)

Karnaugh haritalarında kullanılan ve bir devredeki girdilerin daha hızlı gösterilmesini sağlayan bir notasyondur. Bu yöntem karnaugh haritasındaki her hücreye bir numara verme esasına dayanır. Örneğin aşağıdaki gösterimi ele alalım:

F(A,B,C) = Σ 2, 3,4,6,7

Bu gösterimde anlatılan, karnaugh tablosundaki 4 terimin sonuçta olması gerektiğidir. Bu terimlerin değerleri haritadaki adreslerden elde edilir:

3 girişli karnaugh haritası

Yukarıdaki tablo, ilgili hücrelerin içerdiği satır ve sütun numarasının birleşimidir. Bu tablodaki ikilik tabanda olan sayıları onluk tabana çevirecek olursak:

Bu tabloda verilen sayıları işaretlediğimizde :

ve bu karnaugh haritası üzerinde yakın komşuları eşleştirip sadeleştirme yaptığımızda:

Sonuç olarak sadeleştirilmiş devre

F(A,B,C) = B + AC’

olarak bulunur.

Bu devre çizildiğinde aşağıdaki şekilde bir sonuç elde edilir:

Yukarıda bahsedilen asgariterimler (minterms) aslında decoder kullanılan bir devre için çok daha hızlı sonuca ulaşılmasını sağlar.

Örnek bir decoder devresinde hangi sonuçların or (veya) kapısı ile bağlanacağını belirler.

Örneğin yukarıdaki verilen asgariterimleri (minterms) ele alalım ve aynı devreyi bir dekoder yardımı ile çizmeye çalışalım:

Yukarıdaki devrede görüldüğü üzere decoder çıkışının asgariterim numaraları alınmıştır. (yani çıkışlardan 0,1,5 boş bırakılmış ve 2,3,4,6,7 bağlanmıştır. )

Bu konu ile ilgili daha fazla bilgi için aşağıdaki örnek problemlerin çözümlerine bakabilirsiniz:

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    evet bu haritalamada komşu olan elemanların alınması için bahsettiğiniz şekilde 11 değeri 10 değerinden önce yazılır bu açıdan haklısınız. Çünkü amaç son satırda 10 değerini alıp bunun birinci satır olan 00 ile komşu olması ve harita üzerinde en yakın elemanların komşuluğunu sağlayarak terim sayısını azaltmaktır.
    Bu hatayı düzeltiyorum ilginiz için teşekkürler.

  2. ibrahim

    burda belirtmek istedigim bi yanlıslık var gibi geldi bana !!
    0011 ve 0010 ıncı kutucuklarda hata oldugunu dusunuyorum dogrularının A’ B’ CD = 0011 DİGERİNİNDE A’B’CD’=0010 seklinde olması gerekiyor gibi geldi yanlıs gördüysem kusura bakmayın ..

  3. Şadi Evren ŞEKER Article Author

    haklısınız yazıdaki 5 boş bırakılmış 4 bağlanmış olmalı. Hatayı düzeltiyorum. İlginiz için teşekkürler

  4. Şadi Evren ŞEKER Article Author

    sorunuzun cevabını anlamak için decoder (kod çözücü) başlıklı yazıyı okuyunuz. Bu yazıda göreceksiniz ki bir decoder devresinin her bacağı, aslında mantıksal olarak bir ihtimale karşılık gelir. Örneğin yukarıdaki son örnekte kullanılan 3×8 decoder devresi, 3 girişe sahiptir (bunlara A,B ve C diyelim) çıkışta ise 8 bacağı bulunur ve bunların her birisi bu 3 girişin farklı alternatiflerini içerir.

    Kısacası komşuluk diye tabir ettiğiniz şey decoder devresindeki seçme işlemidir ve bu da ilgili bacakların seçilmesi ile olur.

    ilgili yazı:

    http://www.bilgisayarkavramlari.com/2007/12/09/kod-cozucu-decoder/

  5. ali berat çetin

    Hocam öncelikle sitenizdeki bilgilerin hepsi çok yararlı ve yerinde. Ben bilgisayar mühendisliği okuyorum. Hazırlık okudum 1 sene . 1-2 Ay sonra bölüme başlamış olacağım. Hiç ders görmemiş olmama rağmen C dilinde iyi bir yol aldığımı düşünüyorum. C de sizin de bileceğiniz üzere çoğu okulda başlangıç algoritma temeli için verilen ödevlerin çoğunu elden geçirdim. Veri yapıları ve sıralama algoritmalarınıda aynı şekilde C ile implement edip hallettim. C ile yine graphics.h kütüphanesi kullanarak yazdığım bir kaç oyunum mevcut. Size teşekkür ediyorum kaynaklarınız için. Birkaç sorum olacak yanıt alabilirsem çok sevinirim.
    İlk olarak C’de ilerlersem piyasadaki rekabette yer edinmem zorlaşır mı?
    Çok saçma gelebilir o yüzden kusura bakmayın. Ama C ile bir bankanın windows applicationu’nu yapabilirmiyiz? . Size başka bir mail adresimden yine mail atmıştım sana sanırım yanlış yere gitti. Bunu sitenizdeki mail kısmından yazıyorum. Sevgiler.

ahmet için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir