Anahtarlama fonksiyonları için yerel basitleştirme algoritmaları
Local simplification algorithms for switching functions
- Tez No: 183202
- Danışmanlar: DOÇ.DR. ŞİRZAT KAHRAMANLI
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2006
- Dil: Türkçe
- Üniversite: Selçuk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 151
Özet
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
Özet (Çeviri)
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
Benzer Tezler
- Yeni Cami'nin akustik açıdan performans değerlendirmesi
Evaluation of the acoustical performance of the New Mosque
EVREN YILDIRIM
Yüksek Lisans
Türkçe
2003
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. SEVTAP YILMAZ DEMİRKALE
- GSM transmisyon donanımları gözetim ve denetim arayüzü
Supervision of the base station subsystem transmission equipments on the GSM
NEVİN BASIM
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF.DR. EMRE HARMANCI
- Optimal integration of dg units into unbalanced distribution networks
Dengesiz elektrik dağıtım şebekelerinde dağıtık üretim birimlerinin optimal entgrasyonu
MOHAMMED BAMATRAF
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYDOĞAN ÖZDEMİR
PROF. DR. OĞUZHAN CEYLAN
- A New cryptanalysis method of cellular automata based encryption systems
Hücresel otomata tabanlı şifreleme sistemleri için yeni bir şifre analiz yöntemi
ALİ MURAT APOHAN
Doktora
İngilizce
2000
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. M. ERTUĞRUL ÇELEBİ
- Çok-hızlı ISDN'de geniş bantlı çağırma kurma servisi ve LAN uygulamaları
Multirate ISDN wideband call processing and LAN applications
KENAN ŞAHİN
Yüksek Lisans
Türkçe
2000
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. GÜNSEL DURUSOY