karnaugh haritası (karnaugh map)

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:

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:

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

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)

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:

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:

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:

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.

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:

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:

• Yarım toplayıcı (half adder)
• Tam toplayıcı (full adder)
• çıkarıcı (subtractor)
• çoğunluk biti (majority bit)
• büyüktür (greater than)