Mantık fonksiyonlarının off kümesinin hızlı sadeleştirme algoritması
Fast minimisation algorithm of off set of logic functions
Yazar: BURAK YILMAZ
Danışman: PROF. DR. ŞİRZAT KAHRAMANLI
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2007
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Algoritmalar = Algorithms ; Küp cebri = Cube algebra

Özet:
Matematikte ifadelerin sadelestirmesini birkaç amacı vardır. Sadelesmisifadeleri anlamak ve yazmak daha kolaydır, aynı zamanda ifade ederken hata yapmasansı daha azdır. En önemlisi ise sadelestirilmis ifadeler genelde uygulama sırasındadaha etkin ve verimlidirler.Sayısal devre ve sistemlerin tasarımı ise bilgisayar mühendisliginin en temel veönemli arastırma konularından biridir. Sayısal devreler ve sistemler tasarlanırkenamaç, hedeflenen islevi yerine getirmek üzere olusturulan ifade ve fonksiyonlarınelektronik devre elemanlarıyla fiziksel olarak meydana getirilmesidir.Bu noktada karsımıza mantıksal sadelestirme kavramı çıkmaktadır. Mantıksal(Boolean) ifadelerin sadelestirilmesi, daha verimli bilgisayar programları, algoritmalarve devrelerin tasarlanmasına imkân saglayacaktır.fadelerin ve degerlerin sadelestirilmesi önemlidir çünkü ayrı parçalardan olusanelektronik devreler bu ifadelere ve degerlere göre seçilen parça ve elemanlarlaolusturulmaktadırlar. Sadelestirilmis ifadeler kullanarak devrenin tasarımındakullanılacak eleman sayısı azalacak böylece tasarımcıya daha ucuz ve daha kolaytasarım yapma imkânı tanıyacaktır.Sayısal tasarımın yaygınlasmaya basladıgı 1950'li yılların basından berimantıksal sadelestirme isleminde kullanılmak üzere pek çok algoritma tasarlanmıs veuygulanmıstır. Karnaugh haritaları, Veitch haritaları, Quine - McCluskey yöntemi, kilikarar agaçları gibi yöntemler yaygın olarak kullanılmaktadır. Yine bu yöntemleri temelalan çesitli kesin (exact) ve sezgisel (heuristic) algoritmalar gelistirilmistir. Buyöntemler genel olarak iki seviyeli mantıksal sadelestirme (two level logicminimization) alarak adlandırılırlar.Bu yöntemler yapıları itibariyle NP-Karmasıklık (Nondeterministic PolinomialComplexity) sınıfına dâhildirler, günümüzde kullanılan daha yeni ve geliskinalgoritmalar ise üstel karmasıklıga sahiptir. Bu durumun sebep oldugu en önemlisorunlardan biri giris ve çıkıs sayıları arttıkça programların çalısma sürelerininuzamasıdır, bu üstel yapıdan dolayı 20 giris ve daha üstü sayıda girise sahipsistemlerin sadelestirilmesi islemi çok uzun süre ve kaynak gerektirmekte hattamasaüstü bilgisayarlarda mümkün olmamaktadır. Bu da tasarımda asılması gerekenbir sınır olarak karsımıza çıkmaktadır.Bu tez çalısmasında sunulan yöntem sayesinde sadelestirme islemleri dahadüsük bir karmasıklık seviyesi olan O(n) seviyesine indirilmistir. Böylece hem dahafazla girise sahip problemler daha rahat çözülmekte hem de islem çok daha hızlıgerçeklestirilmektedir.

Abstract:
n Mathematics, there are some reasons for simplification of, functions andterms. It is easier to understand and express simplified terms are functions and alsoless chance to make mistake while expressing. Most important reason is, thesimplified functions are generally more efective and efficient when applied.The logical circuits and systems design is one of the most important and basicresearch topic in computer science. The scope of designing logical circuits andsystems is to compose the functions and terms phisically by electronic circuits.At this point we have to deal with the logical minimization issiue Minimisation ofBoolean functions gives us the opportunity to make more efficient algorithms,computer programs and logical circuits.t is important to minimise the functions, because the electronic circuits aredeveloped by seperate parts and components, based on the boolean functions. Byusing the minimised functions the number of the components beeing used in circuitwill be reduced and give opportunity to make cheaper and easier designs to thedesigner.Since 1950?s there have been lots of algorithms and methodes developed forlogical minimization. Karnaugh Maps, Veitch Maps, Quine - McCluskey techniqueand binary decision diagrams are most known techniques. And also there are lots ofexact and heuristic algorithms based on those methodes has been developed intime. This algoirthms and methodes are generaly named as two level logicminimization.This methodes are classified as NP- Complexity (Nondeterministic PolinomialComplexity) because of their own nature. The newest methodes are generally inexponantial complexity complexity class, so because of the nature of this complexityclass, some problems occures. When the number of inputs ? outputs incerases over20 the working time increases and and algorithms requires more resources. Thissituation becomes very important problem to solve in design time.n this thesis, the proposed method offers O(n) complexity class. By thismethod it becomes easier and faster to minimize the functions that has more inputsthan 20.