ANAHTARLAMA FONKSİYONLARI İÇİN YENİ YAKIN MİNİMUM SADELEŞTİRME ALGORİTMASI
ANAHTARLAMA FONKSİYONLARI İÇİN YENİ YAKIN MİNİMUM SADELEŞTİRME ALGORİTMASI
Yazar: Başçiftçi, Fatih; Kahramanlı, Şirzat
Dergi: Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, Vol. 25 No. 1, 2013
Anahtar kelimeler: Anahtarlama fonksiyonu, sadeleştirme, asal çarpım terim, Off-küme tabanlı minimumlaştırma, doğrudan örtme prensibi.

Anahtarlama fonksiyonlarının sadeleştirilmesi tasarımcılara daha kısa zaman süresinde, daha sade lojik devrelertasarlama imkanı sağlamaktadır. Sadeleştirilmiş olan bir fonksiyon daha az güç tüketimi, daha az hacim ve dahaaz maliyet gerektirir. Bu konu ile ilgili olarak geliştirilen yöntemlerin çoğu iki ana adımda gerçekleştirilir.Birinci adımda, asal çarpım terimlerinin tümü belirlenir. İkinci adımda fonksiyonu sadeleşmiş olarak örtecek,esas asal çarpım terimler kümesi belirlenir. Anahtarlama fonksiyonlarını sadeleştirecek algoritmaların tümüO(2n) karmaşıklığına sahiptirler. Araştırmalar göstermiştir ki n’in çok yüksek değerlerinde esas asal çarpımterimlerin tam kümesini belirleme yöntemi pratik olarak gerçekleştirilemez duruma gelmektedir. Bu yüzden buçalışmada, asal çarpım terimlerin belli kıstaslara cevap verecek alt kümeleri oluşturularak, doğrudan örtmeprensibine dayanan yakın minimum sadeleştirme algoritması geliştirilmiştir. Geliştirilen algoritma çeşitli problemlerüzerinde test edilmiş ve dünyaca örnek olarak kabul edilen ESPRESSO algoritması ile karşılaştırılmıştır.Karşılaştırma kıstasları olarak algoritmaların; çözüm sonucunda buldukları çarpım terimlerinin toplamifadelerinin sayısı, çözüme ulaşma süreleri ve çözüme ulaşırken kullandıkları bellek kapasitesi alınmıştır.Karşılaştırma sonuçlarına göre geliştirilen algoritmanın başarılı sonuçlar verdiği görülmüştür.

Anahtarlama fonksiyonlarının sadeleştirilmesi tasarımcılara daha kısa zaman süresinde, daha sade lojik devrelertasarlama imkanı sağlamaktadır. Sadeleştirilmiş olan bir fonksiyon daha az güç tüketimi, daha az hacim ve dahaaz maliyet gerektirir. Bu konu ile ilgili olarak geliştirilen yöntemlerin çoğu iki ana adımda gerçekleştirilir.Birinci adımda, asal çarpım terimlerinin tümü belirlenir. İkinci adımda fonksiyonu sadeleşmiş olarak örtecek,esas asal çarpım terimler kümesi belirlenir. Anahtarlama fonksiyonlarını sadeleştirecek algoritmaların tümüO(2n) karmaşıklığına sahiptirler. Araştırmalar göstermiştir ki n’in çok yüksek değerlerinde esas asal çarpımterimlerin tam kümesini belirleme yöntemi pratik olarak gerçekleştirilemez duruma gelmektedir. Bu yüzden buçalışmada, asal çarpım terimlerin belli kıstaslara cevap verecek alt kümeleri oluşturularak, doğrudan örtmeprensibine dayanan yakın minimum sadeleştirme algoritması geliştirilmiştir. Geliştirilen algoritma çeşitli problemlerüzerinde test edilmiş ve dünyaca örnek olarak kabul edilen ESPRESSO algoritması ile karşılaştırılmıştır.Karşılaştırma kıstasları olarak algoritmaların; çözüm sonucunda buldukları çarpım terimlerinin toplamifadelerinin sayısı, çözüme ulaşma süreleri ve çözüme ulaşırken kullandıkları bellek kapasitesi alınmıştır.Karşılaştırma sonuçlarına göre geliştirilen algoritmanın başarılı sonuçlar verdiği görülmüştür.