Genelleştirilmiş kapı elemanları ile boole fonksiyonlarının indirgenmesi - Yozgat, Uğur (Fen Bilimleri Enstitüsü, 1992)
Boole fonksiyonlarının indirgenmesi 1955 yılından beri Üzerinde çalışılmakta olan ve bugüne kadar çeşitli yöntemlerin geliştirilmiş olduğu bir konudur. Amaç, ver i 1 en bi r f onk si yona eşdeğer, fak at k ar maşı k 1 1 ğı daha az olan bir fonksiyonun bulunmasıdır. Bugüne kadar geliştirilen yöntemler, iki veya daha çok seviyeliye ilişkin, "VE", "VEYA", "TÜVE" ve "TÜVEYA" kapılarına uygun şekilde indirgeme yapmaya dayanmaktadır. Bu çalışmada, verilen bir fonksiyonu, herhangi bir tanım bağıntısı olan genelleştirilmiş Uç girişli kapı elemanlarından minimum sayıda kullanarak gerçek leyen bir yöntem, GÎY < Genelleştirilmiş kapılara göre indirgeme Yöntemi >, geliştirilmiştir. GÎY' nin temeli Hamming farkına dayanır. indirgemede kullanılacak kapının tanım bağıntısının ve türetilebilir fonksiyon larının çarpım terimlerinin Hamming farkları ile verilen fonsiyonun Hamming farkları matrisinden yararlanarak ve klasik indirgeme yöntemi, Qui ne Mc-Cluskey ile bulunan asal bileşenlerin en uygun bir kümesi belirlenir, indirgenmesi istenen fonksiyonun tüm mint er i mi er ini örten en düşük maliyetli bir asal bileşenler kümesi, tablo yöntemiyle seçilerek fonksiyonun indirgenmiş bir biçimine ulaşılır. Ulaşılan sonuç, en kötü şartlarda klasik yöntemin verdiği çarpımlar toplamı şeklindeki birinci tip kanonik açınım olacak, verilen kapı elemanı, "VE" ve/veya "VEYA" olarak kullanılacaktır. Son yılların en güncel konularından biri yük enjeksiyonlu transistor < YET > yapılı, Uç girişli VETUVEYA < VTV > kapısıdır. Bu kapının özelliklerinden yararlanarak, VTV* ye özel çok seviyeli, verilen fonksiyonun SIFIR kümesini indirgeme ve asal bileşen çarpanlarını inceleme yöntemleri ile maliyeti arttıran "+" işleminden bağımsızlık sağlamak amacıyla GÎY' ni kullanan ÖZlY < VTV kapısına ÖZel indirgeme Yöntemi > gel i şti r i 1 mi şti r. Bu çalışmada geliştirilen GÎY ve ÖZtY yöntemleri programlanmış, bulunan sonuçların üstünlükleri ve eksik likleri tartışılmıştır.

Minimization of Boolean functions is a subject studied since 1955, and various methods have been developed in the literature. In this thesis, the purpose is to obtain a simpler expression for a given function; the simplicity being measured with respect to generalized building blocks other than the classical ones such as AND, OR, NAND etc. gates. The complexity is taken as the total gate cost required to realize the function, and it is assumed that complements of input variables exist. In this study, a method called MRG ( Method of Reduction according to Generalized Gates with 3- inputs ), which realizes a given function by using minimal number of generalized gate elements with 3-inputs having any defining relation, is developed. Basic definitions and concepts used in MRG are examined in the second section. In MRG, under worst conditions, the reduction is made according to AND - OR logic, reaching a result in the form of sum of product terms. Therefore, if a a complete set can be obtained from the gate function gf : S -» S of the given gate element, minimization of the given function reduces to two level AND - OR reduction where each gate is obtained from the genera lized function. One of the key concepts of reduction method based on the Hamming distance. The Hamming distance d(a,b) between the two elements a,b of {0,l>n can be defined as follows: d(a,b) - £ (at © b ) where a = (a,...,a ), b = (b,...,b), a.,b. e {0,1} Vi __ O n o nit and © is the modulo-2 sum or EXCLUSIVE-OR operation. (vi) Hamming distances between the min terms of the given gate function to be used in the reduction ar& calculated and placed as the first element of the usubla functions array UF(.). In order to find out elements of usable functions array by appling logic 1, logic O values to one or more inputs or by connecting gate inputs to each other. For examle "+" operation can be realized with a gate element having a usable function array in which the Hamming distances portion is in the form of i 1 1 2 >. Then the usable function array is modified at each step according to the fallowing two rules; Rule-1 : Generated functions which realize "." and "'" operations are saved but not included in the usable functions array. Rule- 2 : At each step the generated function is compared with the elements of usable functions array; if a situation is detected where Hamming differences portions are the same and the number of product variable of the generated function is greater, then the ones with larger number of variables is placed in the array, if not, the newly generated function is placed to the end of the usable functions array. Hamming distances between the min terms of the function proposed to be reduced are calculated and a matrix of distances MD(. ) is formed. MD kl d d d d"di2d13. 2122 23 Ik' d. d1J 2J d. d. d... d.. *- a* J2 j3 jj j,k.i = 1,2,...,t the of it. e d = d(m,m ), t is the function proposed to be r -educed and m, i. th min t er m V (vii) Based on the above concepts, the following method, which depends on usable functions of the gate element and the matrix of distances, is developed. Method: Given a function f s Sn-» S to be realized and the generalized gate function gf : S -» S, the following steps applied. 1) Usable functions array and the matrix of distances is formed. 2) First element of usuable functions array is selected. 3) Realizability of the element according to minterms of f in Hamming distances portion is investigated by using matrix of differences.. Minterms forming Hamming distances portion are determined and inserted in minterms array M(. ). 4) The minterms placed in M(. ) at each step are then inserted into a final array RC(.) which also contains information about the variables. 5) These operations are applied to all elements of the usuable functions array. 6) Minterms which do not enter RC(.) are appended to it. 7) The product terms in RC(.) are reduced by Quine Mc-Cluskey algorithm to obtain the minimal network. Minterms of given function are reduced according to Quine Mc-Cluskey algorithm and reserved in QC(.) array. Gate costs of elements in RC(. ) and QC(. ) array are calculated. High cost terms of the arrays which are covered by others are eliminated and the remaining ones are written into the prime implicants array PI (. ). (viii) A subs» t of prime implicants with minimum gate cost covering all min terms of f is obtained by using Karnaugh Map, and written in the selected prime implicants array SPI(.). Then the reduced function is equal to the sum of prime implicants in SPI (. ). Details of MRB are given in the third section, the algorithm of the Program-MRG, developed in this thesis, in the fifth section, the application results and program list in appendices A and B. One of the current research topics in recent years is the 3-input NORAND gate with CHINT structure. The charge-injection transistor ( CHINT ) or negative resistance field-effect transistor ( NERFET ) are two modes of operation of a three- terminal heterostructure device. The concept of real -space- tran fer describes the process in which electrons in a narrow semiconductor layer, accelerated by an electric field parallel to the layer, acquire high average energy ( become "hot" ) and then spill over an energy barrier into the adjacent layers. Recently, significient progress has been achieved at Bell Laboratories in the implementation of CHINT devices. The nature of hot- electron injection in CHINT allows the implementation of novel circuit elements. One of the realized new circuit elements is NORAND gate having an output function as follows: gf = x x x + xxk ** 12 8 12 8 Compared to all existing logic families, the NORAND offers a considerable economy in the layout of basic functional elements. Moreover, it promises faster operation of these elements, since the entire function is implemented within one gate delay of a high-speed transistor. MRG developed in the third section can also be used by taking the NORAND as a generalized gate. (ix) In the fourth section, SRM ( Special Reduction Method using NORANO gates ) is described. The method was developed by using the properties of NORAND gate, for obtaining reduced functions which are realized by circuits with less complexity but a greater number of levels. SRM guarantees better results than MRG, giving the same circuit at the worst case. All submethods, mentioned in this section, have the same aim of realizing the reduced form of f independent of "+" operation, which would increase the cost, or to produce a reduced form which needs no "+" operation. It should be noted that the realization cost of "-*-" operation is two, because two NORAND gates connected properly produce the "+" operation. Threee submethods are explained in the fourth section; (i) Multilevel reduction in accordance with gates, (ii) Reduction of the off -set min terms of f, (iii) Trying to find out, if they exists, selected prime implicants whose product terms are complements of each other. The algorithm of Program- SRM developed by using the characteristics of NORAND gate is given in the fifth section, and the application results' and program list in appendices A and B. As seen from the examples and implementations, the methods proposed reduce considerably the complexity and the number of operations for realizing a given function. In cases where reduction should be made by using only given gate elements, the cost may increase if "+" and "." operations cannot be realized in one level, and if the reduced form of the function necessitates the use of "+! and "." operations. The cost can be reduced by using AND - OR gate elements, if they are available. It has been observed that SRM gives outstanding results and reduces the cost to a great extend in cases where min terms are not in neighbour relationship as required by conventional methods. In other cases SRM gives still better results. Finally, it should be observed that the approach used here can be extended to gate elements having more than three inputs.
Minimization of boolean function realization with generalized gates
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1992
Keywords: Boolean fonksiyonları; Kapı elemanı; İndirgeme; Boolean functions; Gate element; Reduction