Tez No	İndirme	Tez Künye	Durumu
183202		Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları / Local simplification algorithms for switching functions Yazar:FATİH BAŞÇİFTÇİ Danışman: DOÇ.DR. ŞİRZAT KAHRAMANLI Yer Bilgisi: Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik-Elektronik Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora Türkçe 2006 151 s.
Anahtarlama fonksiyonlarinin sadelestirilmesi tasarimcilara daha kisa zamansüresinde ve daha sade lojik devreler tasarlama imkani saglamaktadir. Sadelestirilmisolan 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 çesitliteknikler gelistirilmistir. Bu tekniklerin çogu iki ana asamada gerçeklestirilir. Birinciasamada, asal implikant larin tümü belirlenir. Ikinci adimda fonksiyonu sadelesmisolarak örtecek, esas asal implikant lar kümesi belirlenir. Anahtarlama fonksiyonlarinisadelestirecek algoritmalarin tümü O(2n ) karmasikligina sahiptirler. Arastirmalargöstermistir ki n'in çok yüksek degerlerinde esas asal implikant larin tam kümesinibelirleme yöntemi pratik olarak gerçeklestirilemez duruma gelmektedir. Bu yüzdenbu doktora tezinde asal implikant larin belli kistaslara cevap verecek alt kümeleriolusturularak, dogrudan örtme (direct cover) prensibine dayanan birminimumlastirma yöntemi gelistirilmistir.Var olan dogrudan örtme metotlarinda verilen On-küpü içeren yeterli asalimplikant lar kümesini bulmak için, bu küp her defasinda bir koordinat içingenisletilir. Her genislemenin dogrulugu, k < 2n Off-küplerin hepsi ile genisletilenküp kesistirilerek kontrol edilir. Bir küpün genislemesinin polinominal karmasikligasahip 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 isleminkarmasikligi, yaklasik olarak bir koordinat için bir On-küpün genisletilmekarmasikligina esdegerdir. Bundan dolayi, verilen On-küpü içeren asal implikantlarintam kümesinin hesaplama isleminin karmasikligi yaklasik olarak O(np ) kadarazaltilmis olur. Pratik olarak bu yaklasim bir defada islenecek olan asal implikantsayisini yüzlerce ve binlerce defa azaltmaktadir. Bu ise halen problem olan bellekkapasitesi darbogazini kolaylikla asma imkani saglamaktadir. Böylece en çok yirmidegisken siniri da asilmis olmaktadir.Sunulan metot çesitli problemler üzerinde test edilmis ve 48 adet standartMCNC bencmarklari kullanilarak, dünyaca örnek olarak kabul edilmis olanESPRESSO programi ile karsilastirilmistir. Bu karsilastirmalar sonucunda,fonksiyonlarin %89,6'sinda YMÖA, %10,4'ünde ise esit hizda sadelestirmeyapmislardir. KMÖA'sinda ise fonksiyonlarin %12,5'inde esit zamanda, %16,7'sindeEspresso, %70,8'inde ise KMÖA daha hizli sadelestirme yapmistir. Kullandiklaribellek alani bakimindan degerlendirilmesi yapildiginda, ESPRESSO'nun YMÖA'nagöre %16,7 fonksiyonda daha iyi oldugu görülmesine ragmen %83,3 fonksiyondaYMÖA daha az bellek alani kullanmistir. KMÖA'sinda ise ESPRESSO %8,3fonksiyonda iyi olmasina karsin %91,7 fonksiyonda KMÖA daha az bellek alanikullanmistir.Anahtar Kelimeler-Boole fonksiyonu, sadelestirme, minimumlastirma, Booleifadesi, asal implikant, küp cebri, örtme algoritmasi, algoritmalarin karmasikligi,Off-küme tabanli minimumlastirma, dogrudan örtme prensibi.iv
The minimization of Boolean functions allows designers to make use of fewercomponents, thus reducing the cost of particular system. Most of single output andmultiple-outputs Boolean minimization techniques work on a two-step principle, thefirst step identifies all of the prime implicants (PI?s) and the second step selects thesubset of PI?s that covers the function(s) being minimized. All procedures forreducing either two-level or multilevel Boolean networks into prime and irredundantform have O(2n ) complexity. Prime Implicants identification step can becomputational impractical as n increases. Thus, in this Phd thesis, subsets of primeimplicants that can prove direct cover principle which based on determineted critersuse for mimimization method. To find the sufficient set of prime implicantsincluding given On-cube on the existing direct-cover minimization methods, thiscube is expanded for one coordinate at a time. The correctness of each expanding iscontrolled by the way in which the cube being expanded is intersected with all ofk<2n Off-cubes. If to take into consideration that the expanding of one cube has apolynomial complexity then the total complexity of this approach can be expressedas O(np )O(2n ) that is the product of polynomial and exponential complexities. Toobtain the complete set of prime imp licants including given On-cube, the proposedmethod uses Off-cubes expanded by this On-cube. The complexity of this operationis approximately equivalent to a complexity of an intersection of one On-cubeexpanded by existing methods for one coordinate. Therefore, the complexity of theprocess of calculating of the complete set of prime implicants including given On-cube is reduced approximately to O(np ) times. This presently obtains solvingproblem of memory capacity that seems as a bottle neck In this way, number ofmaximum variables limit that is 20, could be exceeded.The method has been tested on several different kinds of problems and onstandard MCNC benchmarks results of which were compared with ESPRESSO.Keywords-Boole function, simplification, minimization, Boole expression, primeimplicant, cube algebra, covering algorithm, complexity of algorithms, Off-set basedminimization, direct-cover principle.iv