Çok değerli lojik
Multiple-valued logic
- Tez No: 66858
- 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: 1997
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 120
Özet
ÖZET Bu tezde çok-değerli lojik konusu, cebirsel operatörler, çok-değerli fonksiyonların gerçeklenmesine ilişkin yapılar, PLA yapılan, çok-değerli lojik fonksiyonların indirgenmesine ilişkin algoritmalar açısından incelenmiştir. Çok geniş ölçekli tümleştirilmiş (VLSI) kırmıkların, yaklaşık yüzde 70 'ini işlem blokları arasındaki bağlantılar oluşturmaktadır. Çok-değerli lojiğin sağladığı iki önemli avantaj, daha az sayıda iç bağlantı ve daha az sayıda bacak gerektirmesidir. Bu yüzden, iki değerli lojiğin, çok sayıda iç bağlantı ve/veya bacak gerektirmesi sebebiyle, gerçeklemenin pratik olarak mümkün olmadığı hallerde çözüm sağlayabilmektedir. Bu tezde çok-değerli lojik, ilk olarak cebirsel yönden ele alınmış ve cebirsel alandaki gelişime öncülük ettiği kabul edilen Post 'tan itibaren konu hakkındaki çalışmalar incelenmiş, iki-değerli (Boole cebri) lojik ile benzer ve farklı tarafları ortaya konmuştur. Bu tezde ayrıca, çok-değerli Boole Cebri incelenmiş, Boole fonksiyonlarının kanonik ifadeleri genelleştirilerek, özel noktalar yardımıyla fonksiyonun tek olarak belirlenebileceği gösterilmiştir. Fonksiyonun tek olarak belirlenemediği noktalarda, bu noktalardan geçebilecek fonksiyonların varlığı incelenmiştir. Ayrıca, Boole Cebrinde formülle ifade edilemeyen fonksiyonların, çok-değerli lojik için tanımlanan operatör yardımıyla, formülle ifade edilebileceği gösterilmiştir. Tasarım karmaşıklığının ve test probleminin aşılabilmesi için, VLSI sistemlerde yaygın olarak PLA, ROM, RAM gibi düzenli yapılara sahip devreler toplanılmaktadır. PLA'lar, çok karmaşık çok-değerli lojik devrelerde de kullanılabilirler. Bu konuda birçok çalışma yapılmış ve birçok, çok-değerli PLA (MV-PLA) yapısı önerilmiştir. Bu tezde Sasao'nun, Aşari ve Eswaran'nin önerdiği PLA yapıları incelenmiş. İncelenen PLA yapılan örneklerle açıklanmış ve karşılaştırılmıştır. Çok-değerli lojik fonksiyonların indirgenmesi konusunda birçok çalışma yapılmıştır. Ancak optimal çözümü veren yöntemler için makine zamanı, problemin büyüklüğü ile üstel olarak arttığından optimale yakın çözüm veren sezgisel indirgeme metotları üzerinde durulmuştur. Bu tezde, bu konudaki çalışmaların temelini oluşturan algoritmalar incelenmiş ve karşılaştırılmıştır. Çok-değerli fonksiyonların indirgenmesinde, Boole fonksiyonlarının indirgenmesi için geliştirilmiş algoritmaları da kullanmak mümkündür. Bu amaçla, herhangi bir iki-değerli lojik indirgeyicinin, çok-değerli girişe sahip lojik fonksiyonların indirgenmesinde nasıl kullanılabileceği gösterilmiştir. Bu tezde, bu metodun kullanıldığı, çok-değerli girişe sahip lojik fonksiyonları indirgeyen bir de program yazılmıştır. XI
Özet (Çeviri)
SUMMARY MULTIPLE-VALUED LOGIC The status of two-valued (binary) logic has reached its present level of complexity, sophistication, and application largely because of the continuous development and ability of microelectronics to provide efficient two-state devices and circuits. This acceptance and exploitation of binary logic has been helped by the appearance of appropriate mathematical tools, starting with the very early work of Boole, followed by the subsequent application of Boolean algebra and associated developments. The 1938 work of Shannon is a classic point along this algebraic road. The most pressing problems in present-day binary systems are interconnection problems, both on-chip and between-chip. On chip the difficulties of placement and routing of the digital logic elements which go to make up the complete chip are escalating with increase in capability per chip, and the silicon area used for interconnections may be greater than that used for active logic elements. Similarly, the difficulties of bringing an increasing number of connections off-chip is promoting a new consideration of packaging concepts in an attempt to overcome problems which are becoming mechanically, thermally, and electrically extreme. All these factors point to the attraction of raising the information content per connection from the present lowest-possible (binary) level [5]. The number of digits, d, required to represent a value, N, in base R is given by N=Rd, the use of multiple-valued logic (MVL), with R > 2, can be seen to offer the promise of processing, storing and transmitting data using fewer switching circuits and interconnections than the corresponding binary systems. The practical consequences of this are a more effective utilization of chip area in device manufacture and a reduction in the size and cost of both IC packages and the printed circuit boards they are mounted on, since in both cases it can be common for the interconnections to occupy a greater area than the switching circuits. One equally practical problem, however, is that the increased number of signal levels carried by a single connection is matched by a decrease in the amount of signal degradation due to noise or distortion which may take place before the signal value becomes corrupted, as shown in Figure S-l [3]. The only systems currently available that use multivalued digital signals are the Intel 43203 iAPX-432 and Intel 8087. These systems do not use multivalued logic circuits, but do use a ROM in which each cell stores one of four possible signal values. xuyvfrwA/w^A WvAV WyVftft*- Figure S-l Binary and multiple-valued signals There are a number of drawbacks to multivalued logic which may explain why they have not been used: 1. Tolerances in multivalued circuits are more critical than in binary circuits since multivalued circuits intrinsically have more threshold values than binary circuits. These tighter tolerances cause reduced noise immunity in the multivalued circuits. 2. There is some indication that multivalued circuits are slower than binary circuits. To cope with the tolerance problems, it may be necessary to increase the maximum signal values (voltage or current). Since it may not be practical to increase the circuit drive capability, this increase in signal swing can cause a decrease in operating speed. 3. There is a large capital investment -both in equipment and in human skill- in producing binary circuits. The cost of switching this investment to producing multivalued circuits may exceed the benefits to be obtained from multivalued techniques. These drawbacks indicate that binary logic will probably not be replaced by multivalued logic circuits. However, the possibility still exists that multivalued circuits will be used in specialized situations such as arithmetic processors or in connection with testing [4]. In this thesis, multiple-valued logic is first examined using algebraic aspect. Algebraic developments may be said to stem from the work of Post in 1921. The works following Post's, are considered and the relation between the Boole algebra is introduced. In this thesis, many-valued Boole algebra is also introduced. A new expression for a 4-valued Boolean function is presented. The existence of a Boolean functions which can be formulized by any four points in S2 where S={a,b,0,l} is studied. It's stated that, the functions that are not Boolean can be formulated using literal operator. Also generalized realization topologies for multivalued functions, design steps, the unary and binary operators that provides a powerful approach to multiple-valued logic synthesis are explained with several examples. X11IWhen multiple-valued VLSI (MV-VLSI) is designed, the same problems as in the two-valued systems is encountered. The first problem is the enormous design complexity of VLSI' s. As the number of the elements in a chip increases, design time increases exponentially. Because logic design of multiple-valued systems is usually much more complicated than two-valued systems, this problem is more important in MV-VLSFs. In order to reduce the design time and errors, automatic design is indispensable in MV-VLSI' s. However, even in two-valued systems, automatic design of logic is very difficult. The only two-valued circuits which are successfully designed by a complete automatic systems and whose optimality is guaranteed are programmable logic arrays (PLA's). The second problem is the testability of the VLSI's. In the modern VLSI's, testing cost often dominates the total production cost. In order to overcome the design complexity and testability problems, circuits having regular structure such as PLA's ROM's, and RAM's are extensively used in many of the VLSI's. PLA's can also be used to implement complex MVL circuits. Therefore, PLA's are the most promising vehicle for implementing complex MVL circuits. In this thesis, multiple-valued PLA's are examined. First, the three types of multiple- valued PLA's (MVPLA's) proposed by Sasao are considered [1 1]. 1- 2' p-2- xr x2 - xn- MIN bölgesi MAX bölgesi fb.fi fm-l Figure S-2 p-valued PLA with MIN and MAX array (Type 1 PLA) Type 1 PLA consists of literal generators (which convert multiple- valued signals into two-valued signals), a MIN array, and a MAX array shown in Figure S-2. Type 2 PLA consists of literal generators, an AND array and an OR array, and output encoders (which convert two-values signals into multiple-valued signals). Type 3 PLA consists of a permutation network and 2-bit decoders in addition to the components of Type 2 PLA. Because the AND and OR arrays are the same as those of two-valued PLA's, Type 2 and Type 3 PLA's are easily implemented by (static or XIVdynamic) MOS/CMOS circuits, and they can be designed by various existing PLA tools such as MINI, MINI-H, and ESPRESSO-MV [11,]. Also the PLA' s proposed by Asari and Eswaran are explained [13]. ?.(X.Xa...^)“ Figure S-3 Schematic representation of multiple function circuits The concept of multiple functions literal circuit (MFLC) shown in Figure S-3 was introduced by Asari and Eswaran. It is shown that by using this circuit one can reduce the required size of MVPLA's, particularly in the presence of a large numbers of inputs. Finally, the methods are compared. The minimization of sum-of-products expression in binary logic has received considerable attention for over 30 years. The complexity of the problem has been known for almost as long. The best known algorithm then requires exponential time. This is a real barrier; it precludes the exact minimization of functions with even a moderately low number of inputs. As a result, considerable effort has been devoted to heuristic minimization methods. For examples, among the Berkeley VLSI tools is ESPRESSO-EC [14], a C program that minimizes binary functions by a set of operations on the prime implicants. Recently, there has been considerable interest in multiple-valued PLA's. In this thesis, the three heuristic multiple-valued sum-of-products minimization algorithms proposed by Pomper and Armstrong, Besslich and Dueck and Miller are considered. All three use the direct cover method, which proceeds in two steps: 1) select a minterm 2) select an implicant Pomper and Armstrong introduced in 1981 a direct cover method that finds a near- minimal sum-of-products expression by choosing a random minterm and an implicant covering that minterm which, when subtracted, drives the most numbers of minterms to 0. In 1986, Besslich introduced another direct cover method that seeks to cover the ”most isolated“ minterms first. And in 1987, Dueck and Miller introduced a method which also seeks the most isolated minterm first, but chooses a product term that tends to introduce the fewest discontinuities when subtracted from the function. XVThis three heuristic sum-of-products minimizations algorithms have been compared on the basis of two sets, 7000 random and 7000 random symmetric 4-valued 2- variable functions. The results from both sets are similar. They show that two heuristics, 1) Dueck and Miller, and 2) Besslich, perform about the same, each slightly better than the 3) Pomper and Armstrong heuristics. The extension of Espresso-H to multiple-valued logic functions is presented by Richard Rudell and Sangiovanni-Vincentelli [19]. They report their experience with the program Espresso-MV that implements these extension. In the section about niinimizations algorithms, Espresso-MV algorithm is also explained. Pseudocode for the Espresso-MV algorithm is given. Several techniques can be used to minimize multiple-valued logic functions. Most of them are extensions of two-valued logic minimization. In the last section, a method for using any two-valued logic minimizer (any minimizer constructed only for two-valued logic and which allows a don't-care set) to minimize logic functions with multiple-valued inputs is considered [20]. First, S pi Boolean variables by associating to each multi-valued input v; a variable representing the condition Vj=j, j=l,..., pi is created. The group of Boolean variables associated to a given Vi is called a part. To each part, a don't-care set of the form given in (S.l), specifying that exactly one variable in that part is ”on" at any given time is associated. D= {xjXj | i*j } u { x, x, xn } (S.l) The total don't-care set is the union of those for each part. So, any multi-valued cube can be represented by an equivalent Boolean cube. The set of all such cubes is minimized using the don't-care set. The result may then be converted back into the multi-valued form. The method is efficient and practical, so long as the number of possible values for a given input is not very large. XVI
Benzer Tezler
- Çok değerli lojik fonksiyonlarının indirgenmesi
Minimization of multiple-valued logic functions
RİFAT DEMİRCİOĞLU
Yüksek Lisans
Türkçe
2005
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ.DR. ECE OLCAY GÜNEŞ
- Fuzzy ölçüm metodları
Fuzzy measure methods
SERKAN KARATAŞ
Yüksek Lisans
Türkçe
2004
MatematikGaziosmanpaşa ÜniversitesiMatematik Ana Bilim Dalı
Y.DOÇ.DR. NAİM ÇAĞMAN
- Çok değerli (multivalent) lojik
Multivalent logic
ŞAKİR ALTUNLİ
Yüksek Lisans
Türkçe
2009
MatematikYüzüncü Yıl ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. M. ŞERİF ALDEMİR
- Alternative arithmetic structures using redundant numbers and multi-valued circuit techniques
Yedekli sayılar ve çok değerli devre teknikleri ile geliştirilen alternatif aritmetik yapılar
UĞUR ÇİNİ
Doktora
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. AVNİ MORGÜL
- Lojik analizörler ve 8 kanallı bir analizörün geliştirilmesi
Logic analyzers and development of an 8-channel analyzer
MURAT DEMİRER
Yüksek Lisans
Türkçe
1982
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiEnerji Mühendisliği Ana Bilim Dalı
PROF. DR. YILMAZ TOKAD