The performance of the Svoboda-Nadler-Vora algorithm for exact multiple-output boolean function minimization is studied and compared with a heuristic minimization method. For this purpose, the algorithm has been implemented in optimized ANSI C code. This implementation introduces a new set of procedures to reduce the cost of prime implicant generation. The concept of weight as the number of 1 and don't care neighbors of a state is used to take advantage of the special cases when a state has only one neighbor or no neighbors at all. The cost of prime implicant generation is further reduced by using the fact that the input dependency of any given state is limited by which of its neighbors exist within an output that are 1 's or don't cares. A detailed example illustrates how the heuristic method can fail to find the absolute minimum of a boolean function. / M.S.

No description available.

Lau, Wai Shing. / Thesis submitted in: November 2006. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 85-94). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Field Programmable Gate Arrays --- p.2 / Chapter 1.2 --- FPGA technology mapping problem --- p.3 / Chapter 1.3 --- Motivations --- p.5 / Chapter 1.4 --- Contributions --- p.6 / Chapter 1.5 --- Thesis Organization --- p.9 / Chapter 2 --- Background Study --- p.11 / Chapter 2.1 --- Deterministic approach to technology mapping problem --- p.11 / Chapter 2.1.1 --- FlowMap --- p.12 / Chapter 2.1.2 --- DAOMap --- p.14 / Chapter 2.2 --- Stochastic approach --- p.15 / Chapter 2.2.1 --- Bio-Inspired Methods for Multi-Level Combinational Logic Circuit Design --- p.15 / Chapter 2.2.2 --- A Survey of Combinational Logic Circuit Representations in stochastic algorithms --- p.17 / Chapter 2.3 --- Genetic Parallel Programming --- p.20 / Chapter 2.3.1 --- Accelerating Phenomenon --- p.22 / Chapter 2.4 --- Chapter Summary --- p.23 / Chapter 3 --- A GPP based Logic Circuit Synthesizer --- p.24 / Chapter 3.1 --- Overall system architecture --- p.25 / Chapter 3.2 --- Multi-Logic-Unit Processor --- p.26 / Chapter 3.3 --- The Genotype of a MLP program --- p.28 / Chapter 3.4 --- The Phenotype of a MLP program --- p.31 / Chapter 3.5 --- The Evolution Engine --- p.33 / Chapter 3.5.1 --- The Dual-Phase Approach --- p.33 / Chapter 3.5.2 --- Genetic operators --- p.35 / Chapter 3.6 --- Chapter Summary --- p.38 / Chapter 4 --- MLP in hardware --- p.39 / Chapter 4.1 --- Motivation --- p.39 / Chapter 4.2 --- Hardware Design and Implementation --- p.40 / Chapter 4.3 --- Experimental Settings --- p.43 / Chapter 4.4 --- Experimental Results and Evaluations --- p.46 / Chapter 4.5 --- Chapter Summary --- p.50 / Chapter 5 --- Feasibility Study of Multi MLPs --- p.51 / Chapter 5.1 --- Motivation --- p.52 / Chapter 5.2 --- Overall Architecture --- p.53 / Chapter 5.3 --- Experimental settings --- p.55 / Chapter 5.4 --- Experimental results and evaluations --- p.59 / Chapter 5.5 --- Chapter Summary --- p.59 / Chapter 6 --- A Hybridized GPPLCS --- p.61 / Chapter 6.1 --- Motivation --- p.62 / Chapter 6.2 --- Overall system architecture --- p.62 / Chapter 6.3 --- Experimental settings --- p.64 / Chapter 6.4 --- Experimental results and evaluations --- p.66 / Chapter 6.5 --- Chapter Summary --- p.70 / Chapter 7 --- A Memetic GPPLCS --- p.71 / Chapter 7.1 --- Motivation --- p.72 / Chapter 7.2 --- Overall system architecture --- p.72 / Chapter 7.3 --- Experimental settings --- p.76 / Chapter 7.4 --- Experimental results and evaluations --- p.77 / Chapter 7.5 --- Chapter Summary --- p.80 / Chapter 8 --- Conclusion --- p.82 / Chapter 8.1 --- Future work --- p.83 / Bibliography --- p.85

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / by Ralph Benhart Iverson. / M.S.

As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing. One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a reversible form. In this thesis, we present and implement a pair of algorithms that extend the best published solution to these problems by taking advantage of Product-Sum EXOR (PSE) gates, the reversible generalization of inhibition gates, which we have introduced in previous work [1,2]. We show that these gates, combined with our novel synthesis algorithms, result in much lower quantum costs over a wide variety of functions as compared to our competitors, especially on incompletely specified functions. Furthermore, this solution has applications for milti-valued and multi-output functions.

The Programmable Logic Devices, PLO, have caused a major impact in logic design of digital systems in this decade. For instance, a twenty pin PLO device can replace from three hundreds to six hundreds Transistor Transistor Logic gates, which people have designed with since the 60s. Therefore, by using PLD devices, designers can squeeze more features, reduce chip counts, reduce power consumption, and enhance the reliability of the digital systems. This thesis covers the most important aspects of logic design using PLD devices. They are Logic Minimization and State Assignment. In addition, the thesis also covers a seldomly used but very useful design style, Self-Synchronized Circuits. The thesis introduces a new method to minimize Two-Level Boolean Functions using Graph Coloring Algorithms and the result is very encouraging. The raw speed of the coloring algorithms is as fast as the Espresso, the industry standard minimizer from Berkeley, and the solution is equally good. The thesis also introduces a rule-based state assignment method which gives equal or better solutions than STASH (an Intel Automatic CAD tool) by as much as twenty percent. One of the problems with Self-Synchronized circuits is that it takes many extra components to implement the circuit. The thesis shows how it can be designed using PLD devices and also suggests the idea of a Clock Chip to reduce the chip count to make the design style more attractive.

Various tree and Directed Acyclic Graph structures have been used for representation and manipulation of switching functions. Among these structures the Binary Decision DiagramJilave been the most widely used in logic synthesis. A BDD is a binary tree graph that represents the recursive execution of Shannon's expansion. A FDD is a directed function graph that represents the recursive execution of Reed Muller expansion. A family of decision diagrams for representation of Boolean function is introduced in this thesis. This family of Kronecker Functional Decision Diagrams (KFDD) includes the Binary Decision Diagrams (BDD) and Functional Decision Diagrams (FDD) as subsets. Due to this property, KFDDs can provide a more compact representation of the functions than either of the two above-mentioned decision diagrams. The new notion of permuted KFDD is introduced to generate a compact circuit in FPGAs to represent a switching function. A permuted tree search is a free search method which is not limited by the order of variable and the expansion tree as in the cases of KFDD, BDD and FDD. A family of decision diagrams and the theory developed for them are presented in this thesis. The family of permuted Kronecker Functional Decision Diagrams includes BODs and FDDs as subsets is incorporated into program RESPER. Due to this property, permuted KFDD can provide a more compact circuit realization in the multilevel circuit. The circuit obtained can be realized directly with FPGAs like AT 6000 series from Atmel. This algorithm is implemented on several MCNC benchmarks, the results compared with previous programs, TECHMAP and REMIT, are very encouraging. The main achievement of this thesis is the creation of the algorithm which applies a permuted tree search method combined with Davio Expansion and generates Directed Acyclic Graph which is next mapped to a compact circuit realization.

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than the minimal form of KRM expansion. • It is a sub-class of the Generalized Reed-Muller Expansion, thus has better testibility than other AND/EXOR circuits. Those design methods of easily testable GRM circuit networks[ 6] [35] can also be used for this new circuit form. • The exact solution to the minimization of this new expansion provides a upperbound for the minimization of ORM expansion. In this thesis, we prove that to calculate a PMPRM expansion from one of its adjacent polarity expansion , only one EXOR operation is needed. By calculating the adjacent polarity expansions one-by-one and searching all the PMPRM forms the minimum one can be found. A speedup approach allows us to find the exact minimum PMPRM without calculating all forms. The algorithm is explained by minimizing the 3-variable functions and is demonstrated by flow graphs. With the introduction of termwise complementary expansion diagram, a computerized algorithm for the calculation of any ORM expansion is presented. The exact minimum ORM form can be obtained by an exhaustive search through all ORM forms. A heuristic minimization algorithm, which is designed to decrease the time complexity of the exact one, is also presented in this thesis. Instead of depending on the number of input variables, the computation time of this quasi-minimum algorithm depends mainly on the complexity of the input functions, thus can solve much larger problems. The exact minimization algorithm for PMPRM and the quasi-minimum ORM minimization algorithm have been implemented in C programs and a set of benchmark functions has been tested. The results are compared to those from [16], [36], and Espresso's. In most cases our program gives the same or better solutions.

<p>Linköpings Universitet och Acreo AB i Norrköping bedriver ett forskningssamarbete rörande organisk elektrokemisk elektronik och det man kallar papperselektronik. Målet på Acreo är att kunna trycka denna typ av elektronik med snabba trycktekniker så som offset- eller flexotryck. Idag görs de flesta demonstratorer och prototyper, baserade på denna typ av elektrokemisk elektronik, med manuella och subtraktiva mönstringsmetoder. Det skulle vara intressant att hitta fler verktyg och automatiserade tekniker som kan underlätta detta arbete. Målet med detta examensarbete har varit att utvärdera vilken potential bläckstråleteknik respektive screentryck har som tillverkningsmetoder för organiska elektrokemiska elektroniksystem samt att jämföra de båda teknikernas för- och nackdelar. Vad gäller bläckstråletekniken, så ingick även i uppgiften att modifiera en bläckstråleskrivare avsedd för kontor/hemmabruk för att möjliggöra tryckning av de två grundläggande materialen inom organisk elektrokemisk elektronik - den konjugerade polymeren PEDOT och en elektrolyt.</p><p>I denna uppsats rapporteras om hur en procedur för produktion av elektrokemisk elektronik har utvecklats. Världens första elektrokemiska transistor som producerats helt med bläckstråleteknik presenteras tillsammans med fullt fungerande implementeringar i logiska kretsar. Karaktärisering av filmer, komponenter och kretsar som producerats med bläckstråle- och screentrycksteknik har legat till grund för den utvärdering och jämförelse som har gjorts av teknikerna. Resultaten ser lovande ut och kan motivera vidare utveckling av bläckstrålesystem för produktion av prototyper och mindre serier. En kombination av de båda nämnda teknikerna är också ett tänkbart alternativ för småskalig tillverkning.</p> / <p>Linköping University and the research institute Acreo AB in Norrköping are in collaboration conducting research on organic electrochemical electronic devices. Acreo is pushing the development of high-speed reel-to-reel printing of this type of electronics. Today, most demonstrators and prototypes are made using manual, subtractive patterning methods. More tools, simplifying this work, are of interest. The purpose of this thesis work was to evaluate the potential of both inkjet and screen printing as manufacturing tools of electrochemical devices and to conduct a comparative study of these two additive patterning technologies. The work on inkjet printing included the modification of a commercially available desktop inkjet printer in order to print the conjugated polymer PEDOT and an electrolyte solution - these are the two basic components of organic electrochemical devices. For screen printing, existing equipment at Acreo AB was employed for device production.</p><p>In this report the successful development of a simple system and procedure for the inkjet printing of organic electrochemical devices is described. The first all-inkjet printed electrochemical transistor (ECT) and fully functional implementations of these ECTs in printed electrochemical logical circuits are presented.</p><p>The characterization of inkjet and screen printed devices has, along with an evaluation of how suitable the two printing procedures are for prototype production, been the foundation of the comparison of the two printing technologies.</p><p>The results are promising and should encourage further effort to develop a more complete and easily controlled inkjet system for this application. At this stage of development, a combination of the two technologies seems like an efficient approach.</p>

A new circuit technique called Folded Source Coupled Logic (FSCL) has been developed to implement the digital section of mixed-signal IC applications. This FSCL circuit technique offers the advantage of low overlap current spikes during the switching transitions of conventional CMOS gates. This overlap current spike has become one of the major obstacles in improving the accuracy and performance of mixed-signal IC applications. Using simple circuits, FSCL logic family can be interfaced with the existing CMOS family. Thus it can nearly eliminate the power noise issue in the mixed-signal IC design. In this thesis, design of a sinc3 decimation filter using the FSCL technique for a 2nd order delta-sigma modulator has been presented. Simulation results show that this particular decimation filter, using the newly developed FSCL technique, improves the performance of the mixed-signal system. / Graduation date: 1994