Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları
Yükleniyor...
Dosyalar
Tarih
2006
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Selçuk Üniversitesi Fen Bilimleri Enstitüsü
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Anahtarlama fonksiyonlarinin sadelestirilmesi tasarimcilara daha kisa zaman süresinde ve daha sade lojik devreler tasarlama imkani saglamaktadir. Sadelestirilmis olan bir fonksiyon daha az güç tüketimi, daha az hacim ve daha az maliyet gerektir ir. Bu konu ile ilgili olarak tek ve çok çikisli fonksiyonlarin sadelestirilmesi için çesitli teknikler gelistirilmistir. Bu tekniklerin çogu iki ana asamada gerçeklestirilir. Birinci asamada, asal implikant larin tümü belirlenir. Ikinci adimda fonksiyonu sadelesmis olarak örtecek, esas asal implikant lar kümesi belirlenir. Anahtarlama fonksiyonlarini sadelestirecek algoritmalarin tümü O(2n ) karmasikligina sahiptirler. Arastirmalar göstermistir ki n'in çok yüksek degerlerinde esas asal implikant larin tam kümesini belirleme yöntemi pratik olarak gerçeklestirilemez duruma gelmektedir. Bu yüzden bu doktora tezinde asal implikant larin belli kistaslara cevap verecek alt kümeleri olusturularak, dogrudan örtme (direct cover) prensibine dayanan bir minimumlastirma yöntemi gelistirilmistir. Var olan dogrudan örtme metotlarinda verilen On-küpü içeren yeterli asal implikant lar kümesini bulmak için, bu küp her defasinda bir koordinat için genisletilir. Her genislemenin dogrulugu, k < 2n Off-küplerin hepsi ile genisletilen küp kesistirilerek kontrol edilir. Bir küpün genislemesinin polinominal karmasikliga sahip oldugu dikkate alindiginda, bu yaklasimin toplam karmasikligi O(np )O(2n ) seklinde olmaktadir. Bu polinominal ve üssel (exponansiyel) karmasikligin çarpimidir. Verilen On-küpü içeren asal implikantlarin tam kümesini elde etmek için önerilen metot, bu On-küp tarafindan genisletilen Off-küpleri kullanir. Bu islemin karmasikligi, yaklasik olarak bir koordinat için bir On-küpün genisletilme karmasikligina esdegerdir. Bundan dolayi, verilen On-küpü içeren asal implikantlarin tam kümesinin hesaplama isleminin karmasikligi yaklasik olarak O(np ) kadar azaltilmis olur. Pratik olarak bu yaklasim bir defada islenecek olan asal implikant sayisini yüzlerce ve binlerce defa azaltmaktadir. Bu ise halen problem olan bellek kapasitesi darbogazini kolaylikla asma imkani saglamaktadir. Böylece en çok yirmi degisken siniri da asilmis olmaktadir. Sunulan metot çesitli problemler üzerinde test edilmis ve 48 adet standart MCNC bencmarklari kullanilarak, dünyaca örnek olarak kabul edilmis olan ESPRESSO programi ile karsilastirilmistir. Bu karsilastirmalar sonucunda, fonksiyonlarin %89,6'sinda YMÖA, %10,4'ünde ise esit hizda sadelestirme yapmislardir. KMÖA'sinda ise fonksiyonlarin %12,5'inde esit zamanda, %16,7'sinde Espresso, %70,8'inde ise KMÖA daha hizli sadelestirme yapmistir. Kullandiklari bellek alani bakimindan degerlendirilmesi yapildiginda, ESPRESSO'nun YMÖA'na göre %16,7 fonksiyonda daha iyi oldugu görülmesine ragmen %83,3 fonksiyonda YMÖA daha az bellek alani kullanmistir. KMÖA'sinda ise ESPRESSO %8,3 fonksiyonda iyi olmasina karsin %91,7 fonksiyonda KMÖA daha az bellek alani kullanmistir.
The minimization of Boolean functions allows designers to make use of fewer components, thus reducing the cost of particular system. Most of single output and multiple-outputs Boolean minimization techniques work on a two-step principle, the first step identifies all of the prime implicants (PI?s) and the second step selects the subset of PI?s that covers the function(s) being minimized. All procedures for reducing either two-level or multilevel Boolean networks into prime and irredundant form have O(2n ) complexity. Prime Implicants identification step can be computational impractical as n increases. Thus, in this Phd thesis, subsets of prime implicants that can prove direct cover principle which based on determineted criters use for mimimization method. To find the sufficient set of prime implicants including given On-cube on the existing direct-cover minimization methods, this cube is expanded for one coordinate at a time. The correctness of each expanding is controlled by the way in which the cube being expanded is intersected with all of k<2n Off-cubes. If to take into consideration that the expanding of one cube has a polynomial complexity then the total complexity of this approach can be expressed as O(np )O(2n ) that is the product of polynomial and exponential complexities. To obtain the complete set of prime imp licants including given On-cube, the proposed method uses Off-cubes expanded by this On-cube. The complexity of this operation is approximately equivalent to a complexity of an intersection of one On-cube expanded by existing methods for one coordinate. Therefore, the complexity of the process of calculating of the complete set of prime implicants including given On- cube is reduced approximately to O(np ) times. This presently obtains solving problem of memory capacity that seems as a bottle neck In this way, number of maximum variables limit that is 20, could be exceeded. The method has been tested on several different kinds of problems and on standard MCNC benchmarks results of which were compared with ESPRESSO.
The minimization of Boolean functions allows designers to make use of fewer components, thus reducing the cost of particular system. Most of single output and multiple-outputs Boolean minimization techniques work on a two-step principle, the first step identifies all of the prime implicants (PI?s) and the second step selects the subset of PI?s that covers the function(s) being minimized. All procedures for reducing either two-level or multilevel Boolean networks into prime and irredundant form have O(2n ) complexity. Prime Implicants identification step can be computational impractical as n increases. Thus, in this Phd thesis, subsets of prime implicants that can prove direct cover principle which based on determineted criters use for mimimization method. To find the sufficient set of prime implicants including given On-cube on the existing direct-cover minimization methods, this cube is expanded for one coordinate at a time. The correctness of each expanding is controlled by the way in which the cube being expanded is intersected with all of k<2n Off-cubes. If to take into consideration that the expanding of one cube has a polynomial complexity then the total complexity of this approach can be expressed as O(np )O(2n ) that is the product of polynomial and exponential complexities. To obtain the complete set of prime imp licants including given On-cube, the proposed method uses Off-cubes expanded by this On-cube. The complexity of this operation is approximately equivalent to a complexity of an intersection of one On-cube expanded by existing methods for one coordinate. Therefore, the complexity of the process of calculating of the complete set of prime implicants including given On- cube is reduced approximately to O(np ) times. This presently obtains solving problem of memory capacity that seems as a bottle neck In this way, number of maximum variables limit that is 20, could be exceeded. The method has been tested on several different kinds of problems and on standard MCNC benchmarks results of which were compared with ESPRESSO.
Açıklama
Anahtar Kelimeler
Boole fonksiyonu, Sadeleştirme, Minimumlaştırma, Boole ifadesi, Asal implikant, Küp cebri, Örtme algoritması, Algoritmaların karmaşıklığı, Off-küme tabanlı minimumlastırma, Doğrudan örtme prensibi, Boole function, Simplification, Minimization, Boole expression, Prime implicant, Cube algebra, Covering algorithm, Complexity of algorithms, Off-set based minimization, Direct-cover principle
Kaynak
WoS Q Değeri
Scopus Q Değeri
Cilt
Sayı
Künye
Başçiftçi, F. (2006). Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları. Selçuk Üniversitesi, Yayımlanmış doktora tezi, Konya.
