Lojik devre tasarımı algoritmaları
Başlık çevirisi mevcut değil.
- Tez No: 55616
- Danışmanlar: PROF.DR. AHMET DERVİŞOĞLU
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1996
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 102
Özet
ÖZET Bu tezde lojik tasarım algoritmaları incelenmiştir. İncelenen algoritmaların eksik yönleri saptanmış ve bu eksik yönleri içermeyen daha hızlı algoritmalar geliştirilmiştir. İkinci bölümde çok etkili bir PLA indirgeme programı olan ESPRESSO-IF yi oluşturan algoritmalar incelenmiş ve bu algoritmalar Borland C++ derleyicisi ile kodlanarak verilen örnekleri, kabul edilebilir makine zamanı içerisinde indirgeyebÜen optimale oldukça yakın sonuç veren bir program elde edilmiştir. Geliştirilen program kısmen belirli birden çok Boole fonksiyonlarım ortak indirgeyebilmektedir. Bu program MOP programı ile karşılaştinlmışür. Bunun yanında tamamen belirli Boole fonksiyonlarım teker teker indirgeyebilen bir program olan SIMPLIFY programı da geliştirilerek SOP programı ile karşdaştmîmıştır. Bu programların test sonuçlan sonuç bölümünde verilmiştir. Bu testlerden ESPRESSO-IF nin genelde MOP[33] programından daha yavaş indirgeme yapabildiği fakat optimale daha yakın olduğu görülmektedir. Üçüncü bölümde sonlu durumlu ardışıl makineler için iki ayrı durum indirgeme yöntemi geliştirilmiştir. Bu yöntemler son yıllarda yayınlanan ( Puri[23] ve Rho[25] ) makaleîerdeki yöntemlerden daha üstündür. Geliştirilen yöntemlerdeki aşamalar çok açıktır ve programlamaya çok elverişlidir. Bu yöntemlerden birincisi Borland Pascal derleyicisi ile kodlanmış ve SRP programı ile sonuç bölümünde karşüaştırıîmışür. Bu çalışmada geliştirilen durum indirgeme yönteminin literatürde verilen en önemli algoritmalardan çok hızlı ve üstün olduğu açıkça görülmektedir.
Özet (Çeviri)
SUMMARY LOGIC DESIGN ALGORITHMS In this thesis reduction of Boolean functions and state minimization of incompletely specified sequential machines are concerned. In Chapter 2 the notation and theoretical foundations for logic function manipulation are given. First unate functions and basic results concerning them are introduced. The unate recursive paradigm is presented and illustrated with the SIMPLIFY algorithm. Although not part of ESPRESSO-H, SIMPLIFY provides a very fast heuristic method for logic minimization and is effective for single-output functions in applications where computation time is more important. In this chapter each of the algorithms of ESPRESSO-H is described in detail along with supporting theorems. In addition, the algorithms are outlined as structured procedures which can be found in the figures throughout the chapter. ESPRESSO-H and SIMPLIFY have been implemented in C++ programming language and tested on many examples. The results of these tests are reported and summarized in conclusion. In Chapter 3, new exact algorithms for state minimization of Finite State Machines are (FSM) presented. First method generates maximal compatibles and prime compatibles and then tries to find a closed cover which consists of minimal number of prime compatibles. To do this, combinations of the prime compatibles are obtained and checked for closure property. However not all combinations are checked for closure property. Using upper and lower bounds on the number of states in minimized machine, much of these combinations are eleminated. Moreover in some cases minimal closed cover İs directly determined with a little effort if lower and upper bounds are equal. DUROP has been implemented in Pascal programming language using this method. This program is tested on many examples and results are disscussed in conclusion. Second method also uses lower and upper bounds but unlike previously developed methods. It starts with generating closed sets composed of compatible pairs. Covering condition is then ensured and minimal closed cover is obtained. The main features of the method described here are first, the generation of prime compatibles is avoided, second tight lower and upper bounds are determined and third efficient, fast, adaptive algorithms are employed. In fact this method is very suitable for programming, requires less memory and the computer program based on this method much faster than existing methods. VIThe design of a digital system can be viewed as a sequence of transformations of a design representations at different levels of abstraction. The behavioral specifications of the system are described first by a functional representation. For example, Hardware Description Languages such as ISP, IDL, AHPL, VHDL are used. The functional representation is transformed into logic description, consisting of a net-list of logic gates, including storage gates, that can be visualized by a logic schematic diagram. Subsequently logic synthesis is performed, which transforms and minimizes the representation, achieving a technology-independent set of logical expressions. The next step is to specify an electrical representation, according to an implementation technology, which is eventually transformed into a geometric layout of the integrated circuit implementing the given functionality. Programmable Logic Arrays (PLÂ) have been shown to be very effective for designing both combinational and sequential circuits[3]. Read Only Memories (ROM) can be used to realize a logic function whose entries are stored in the memory locations corresponding to appropriate addresses. Read Only Memories are two-dimensional arrays and are implemented in several technologies. The implementation of a Boolean logic function by means of a ROM yields a very structured design, which can be easily modified. Moreover, the speed of operation can be fast and easily determined for the set of combinational logic functions requiring the same address space. A ROM implementation of a Boolean function is not effective in terms of silicon area. A ROM implementation of a n-input function requires 2“ memory cells. In addition, a combinational function may not require the entire address space of a ROM because the function is not specified for some input combinations. Programmable Logic Arrays allow for more efficient use of silicon area by representing a set of logic functions in a compressed yet regular form. A PLA implements two stage combinational logic (e.g. OR of ANDs) through an adjacent pair of rectangular arrays. Each position of the array is programmed by presence or absence of a device. The functionality of a PLA can be represented by a 0-1 matrix, and the design and optimization of a PLA can be carried out directly in terms of this functional representation. PLAs are attractive building blocks of a structured design methodology. Many industrial VLSI circuits, such as the Intel 8086, the Motorola 68000, the Hewlett- Packard 32-bit and the Bell Mac-32 micro-processors, use PLAs as building blocks. Finite State Machines are implemented by a combinational and storage components. A regular array can implement effectively the FSM combinational component. In particular, PLA-based Finite State Machines can be designed efficiently, because the properties of two-level combinational functions are well understood. PLAs and memory elements can be seen as primitives of a general digital design methodology. Boolean function can be described by a logic cover. When designing a PLA implementation of a Boolean function, the logic cover is represented by a pair of matrices, called input and output matrices. VIIThe input and output matrices shown on the left and right below, * 0 * * * 0 * * * 0 1 * * * * 1 0 1 0 1 0 0 0 0 0 0 1 0 have a corresponding PLA implementation shown in Figure S-l In the 1950s, the early years of digital design, logic gates were expensive. It was therefore important to develop techniques that produced, for a given logic function, an implementation with a smaller number of devices (gates and basic components of gates such as diodes and resistors). At that time, the simplification of logic functions became a very attractive area of research. Karnaugh maps were used to manually minimize simple combinational two-level logic functions [3]. Later on, more sophisticated techniques were introduced by Quine and McCluskey to obtain a two-level implementation of a given combinational logic function with the minimum number of gates. These techniques involved two steps: Î. Generation of all prime implicants, 2. Extraction of a minimum prime cover. i j 1 1 1 & 1 j 1 j 3jS j 3jS j [ 1 si n n n j i. ys j j ÎE U 5E- 31 H 35 3r HHHHimmy r t t Figure S-l PLA Implementation Even though the generation of all prime implicants has become more efficient, it can be shown that the number of prime implicants of a logic function with n-input variables can VIIIbe as large as 37n. In addition, the second step, in general implemented with a branch- and-bound technique, involves the solution of a minimum covering problem that is known to belong to the class of NP-complete problems. This leaves Utile hope of finding an efficient exact algorithm, i.e., a minimum covering algorithm whose running time is bounded by a polynomial in the number of elements in the covering problem. Since the number of elements in the covering problem may be proportional to the exponential of the number of input variables of the logic function, the use of these techniques is totally impractical even for medium sized problems (10-15 variables). In the late 1960s and early 1970s, the cost of logic gates was reduced so that logic minimization was not as essential as before and hand-simplification was enough to produce satisfactory designs. In the late 1970s, the advent of LSI made regular structures such as PLAs very desirable for the implementation of logic functions, because of the reduction in the design time they offered. Two-level logic minimization has again become an important tool in the design environment. The minimization of product terms obtained by logic minimization has a direct impact on the physical area required since each product term is implemented as a row of the PLA. Logic design for VLSI often involves logic functions with more than 30 inputs and outputs and with more than 100 product terms, for which exact minimization is impratical The need for optimization in such cases has motivated various approaches to the problem. More recently, heuristic approaches have found wide application in the design of practical PLAs. The earliest and most successful of these methods led to the program MINI developed at IBM in the middle 1970s. Since exact minimization is impratical, ESPRESSO-II depends upon MINI-style iterative improvements to achive confidence in the optimality of the final result. Robustness is a result of efficient heuristic algorithms, as well as special case handling. Since many of the algorithms employed have worst-case exponential complexity, their success in practice ultimately rests upon the exploitation of special properties of the logic functions encountered in actual applications. The sequence of operations carried out by ESPRESSO-H is outlined below. ESPRESSO-H: 1. Complement ( Compute the complement of the PLA and the don't-care set, i.e., compute the off-set ). 2. Expand ( Expand each implicant into a prime and remove covered imphcants ). 3. Essential Primes ( Extract the essential primes and put them in the don't-care set ). IX4. irredundant Cover ( Find a minimal (optionally minimum) irredundant cover ). 5. Reduce ( Reduce each implicant to a minimum essentia! implicant ). 6. Iterate 2, 4, and 5 until no improvement. 7. Lastgasp ( Try reduce, expand and irredundant cover one last time using a different strategy. If successful, continue the iteration ). 8. Makesparse ( Include the essential primes back into the cover and make the PLA structure as sparse as possible ). Although most of these procedures have a counterpart in MINI, the algorithms employed in ESPRESSO-0 are new and quite different. Efficient Boolean manipulation achived through the ”unate recursive paradigm", which is employed in complementation, tautology and other algorithms. In the expansion step, the notion of blocking and covering matrices, which allow for efficient and strategic selection of prime implicants are introduced. Irredundant cover uses a logic expressions which gives the condition under which a given subset of cubes forms a cover, facilitating the intelligent choice of a minimal set. Finally, the procedure LASTGASP allows us to guarantee at least a weak form of optimality for the final result: no single prime can be added to cover in such a way that two primes can then be eliminated.
Benzer Tezler
- İkili karar diyagramları yardımıyla lojik devre tasarımı
Logic design with binary decision diagrams
UTKU ÖZCAN
Yüksek Lisans
Türkçe
2001
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. AHMET DERVİŞOĞLU
- Yeni ve gelişmekte olan yarı iletken cihazlar için teknoloji gerçeklemesi, modelleme, devre tasarımı ve simülasyonu: Organik ince film transistör ve dört-uçlu anahtar cihazları
Technology implementation, modeling, circuit design and simulation for emerging semiconductor devices: Organic thin film transistor and four-terminal switch devices
NİHAT AKKAN
Doktora
Türkçe
2022
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HERMAN SEDEF
DOÇ. DR. MUSTAFA ALTUN
- Elektronik devrelerin evrimsel algoritmalarla tasarımı
Design of electronic circuits via evolutionary algorithms
MUSTAFA ÇAKIR
Yüksek Lisans
Türkçe
2007
Elektrik ve Elektronik MühendisliğiMustafa Kemal ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ERSİN ÖZDEMİR
- Reliability and computing techniques for nano switching arrays
Nano anahtarlamalı dizinler için güvenilirlik ve hesaplama teknikleri
ONUR TUNALI
Yüksek Lisans
İngilizce
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiNanobilim ve Nanomühendislik Ana Bilim Dalı
YRD. DOÇ. DR. MUSTAFA ALTUN
- Elde seçmeli toplayıcıya dayalı yüksek performanslı karma toplayıcı devrelerin tasarımı
High performance hybrid adders design based carry select adder
ÖZLEM BATUR
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET SERTBAŞ