Browse By

Boole Fonksiyonlarının Minimizasyonu

İlk yazımızda sadece 0 ve 1 değerleri alabilen fonksiyonlara Boole Fonksiyonları denildiğinden bahsetmiştik. Boole fonksiyonları çok sayıda bit ile ifade edilebilir, bu yazıda Boole fonksiyonlarının minimize edilmesi yani daha az değişken ile ifade edilmesi için uygulanan adımları işleyeceğiz.

Boole fonksiyonlarının değişken sayısının azaltılması için çeşitli yöntemler kullanılmaktadır. Bunlara örnek olarak Karnough tablosunu, Mc Cluskey yöntemini gösterebiliriz. Bundan önce fonksiyonların minimizasyonunu anlamak için onların hypercube (hiperküp) tasviri önemlidir.

14881368_10154695307579581_249777509_o

Değişken sayısına göre şekil karmaşıklığı artmaktadır.

4 değişkenli fonksiyonlar için hypercube tasviri aşağıdaki şekilde yapılır;

14923982_10154695307834581_638560162_o

Hypercubede katmanlar 1 bitlik değişime göre oluşturulur. Örneğin yukarıdaki çizimde 0 birinci katmandır ve ikinci katman olan 1, 2, 4 ve 8’ e 0’dan (0000) sadece 1 bit değişim ile geçilir.

14876357_10154695307664581_27245610_o

y = ab’c’ v a’d

4 bitlik Boole fonksiyonlarının minimizasyonu için en uygun yöntem Karnough tablosuna yerleştirip sadeleştirmektir. Ama Değişken sayısı arttığında bu tabloyu oluşturmak çok fazla zaman alacaktır.

Diğer yöntem için aşağıdaki fonksiyonun minimizasyonunu ele alalım;

14876144_10154695581829581_2124682507_o

Fonksiyon 9 durum ile ifade edilmiş, her durum 4 bit olduğundan bu fonksiyonun karmaşıklığı 36’dır ve 36 karmaşıklı fonksiyonda işlem yapmak zordur bu nedenle minimize edilmeli. İlk olarak verilen  1’li durumlar hypercubedeki 1 bitlik değişime göre katmanlar halinde sıralanır.

0000                                                                        14876283_10154695307734581_486387304_o                  0001                                                                                           0100                                                                                          0011                                                                                       0101                                                                                         1100                                                                                           1011                1110                                                                                          1111

Boole fonksiyonlarının minimizasyonu aralıklar yardımı ile gerçekleştirilir. Bu şekilde verilen fonksiyonlar için işlem 2 aşamalıdır.

  1. Verilen durumları ifade eden maksimum aralıkların belirlenmesi.
  2. Implicant tablosu oluşturularak fazlalıkların çıkarılması.

Katmanlar yazıldıktan sonra komşu katmanlar yukarıdan aşağıya doğru (1. Katmanla 2. Katman , 2. İle 3. Katman, 3. İle 4. Katman , 4. Katman ile 5. Katman şeklinde) karşılaştırılarak 1 bitlik değişim olan noktalara “_ ” yazılır. Daha sonra aynı ifade ile temsil edebilecek olanlar tek bir ifade ile gösterilir, bu maksimum aralıkların bulunması işlemidir.

14881353_10154695307344581_819221349_o

Aralıkların bulunması ile karmaşıklık 36 dan 20 ye (20 bit) inmiş oldu. İkinci aşamada Implicant tablosunu oluşturuyoruz. Tablonun sol tarafına satır başlarına aralıklar,  üst tarafına sütun başlarına ise fonksiyonda verilen 1’li durumlar yerleştirilir. Satırdaki aralık değeri ile ifade edilebilecek (yani “_ “ olan yerlere 0 veya 1 yazılarak oluşturulabilecek durumlar (sütunlar)) durumlar 1 değeri alır.

14875989_10154695307484581_753710455_o

Tabloyu doldurduktan sonra tüm kapsamalarını bulmamız gerekiyor. Tüm kapsamaları bulmak için Patrick yöntemini kullandığımızdan daha önce bahsetmiştik. İşlemleri kolaylaştırması için satırları a, b, c gibi isimlendiriyoruz.  Patrick yöntemi ile tüm kapsamaları hesapladıktan sonra bizim için uygun olan (en az bit sayısına sahip olan) minimum kapsamayı seçiyoruz.

14859421_10154695646044581_24384325_o

Minimum kapsama (seçtiğimiz abef kapsaması) ile fonksiyon 11 bit ile ifade edilebildi. Yani fonksiyonun karmaşıklığı 36’dan 11’e indirgenmiş oldu.

Umarım anlaşılır olmuştur =)

 

2 thoughts on “Boole Fonksiyonlarının Minimizasyonu”

  1. Ravachol says:

    Patrick yöntemini neden kullanıyoruz? minimum kapsamayı normal yoldan bulsak daha rahat olmaz mı?

    1. Mrs.BytE says:

      Patrick yöntemi minimum kapsamayı bulmak için değil, mümkün tüm kapsamaları bulmak için kullanılan yöntemdir. İşlem adımı daha az olduğu için burada onu tercih ettik isterseniz minimum kapsamayı bulma yöntemleriyle de yapabilirsiniz.

Bir cevap yazın

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

%d blogcu bunu beğendi: