Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları
| dc.contributor.advisor | Kahramanlı, Şirzat | |
| dc.contributor.author | Başçiftçi, Fatih | |
| dc.date.accessioned | 2017-12-27T13:06:12Z | |
| dc.date.available | 2017-12-27T13:06:12Z | |
| dc.date.issued | 2006 | |
| dc.department | Enstitüler, Fen Bilimleri Enstitüsü, Elektrik Elektronik Mühendisliği Ana Bilim Dalı | en_US |
| dc.description.abstract | 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. | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.citation | Başçiftçi, F. (2006). Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları. Selçuk Üniversitesi, Yayımlanmış doktora tezi, Konya. | en_US |
| dc.identifier.uri | https://hdl.handle.net/20.500.12395/7569 | |
| dc.language.iso | tr | en_US |
| dc.publisher | Selçuk Üniversitesi Fen Bilimleri Enstitüsü | en_US |
| dc.relation.publicationcategory | Tez | en_US |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.selcuk | 20240510_oaig | en_US |
| dc.subject | Boole fonksiyonu | en_US |
| dc.subject | Sadeleştirme | en_US |
| dc.subject | Minimumlaştırma | en_US |
| dc.subject | Boole ifadesi | en_US |
| dc.subject | Asal implikant | en_US |
| dc.subject | Küp cebri | en_US |
| dc.subject | Örtme algoritması | en_US |
| dc.subject | Algoritmaların karmaşıklığı | en_US |
| dc.subject | Off-küme tabanlı minimumlastırma | en_US |
| dc.subject | Doğrudan örtme prensibi | en_US |
| dc.subject | Boole function | en_US |
| dc.subject | Simplification | en_US |
| dc.subject | Minimization | en_US |
| dc.subject | Boole expression | en_US |
| dc.subject | Prime implicant | en_US |
| dc.subject | Cube algebra | en_US |
| dc.subject | Covering algorithm | en_US |
| dc.subject | Complexity of algorithms | en_US |
| dc.subject | Off-set based minimization | en_US |
| dc.subject | Direct-cover principle | en_US |
| dc.title | Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları | en_US |
| dc.title.alternative | Local simplification algorithms for switching functions | en_US |
| dc.type | Doctoral Thesis | en_US |
