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.

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

The development of cost-effective circuits is primarily a matter of economy. To achieve it, design errors and circuit flaws must be eliminated during the design process. To this end, considerable effort must be put into all phases of the design cycle. Effective CAD tools are essential for the production of high-performance digital systems. This thesis describes a CAD tool called LOVERD, which consists of ATPG, fault simulation, design verification and diagnosis. It uses test patterns, developed to detect single stuck-at faults in the gate-level implementation, to compare the results of the functional level description and its gate-level implementation. Whenever an error is detected, the logic diagnosis tool can be used to provide useful information to designers. It is shown that certain types of design errors in combinational logic circuits can be detected and allocated by LOVERD efficiently.

Power dissipation in modern technologies is an important matter and overheating is a severe concern for both manufacturer (impossibility of introducing new and smaller scale technologies and limited temperature range for operating the product) and customer (power supply, which is especially important for mobile systems). One of the main profits that reversible circuit carries is theoretically the zero power dissipation in the sense that it is independent of underlying technology; irreversibility means heat generation. In the other words, reversible circuits may offer a feasible solution in the future that will aid certain reduction of the power loss. Reversible circuits are circuits that do not lose information during computation. These circuits can create unique output vector from each input vector, and vice versa, that is, there is a one-to-one mapping between the input and the output vectors. Historically, the reversible circuits have been inspired by theoretical research in low power electronics as well as practical progress of bit-manipulation transforms in cryptography and computer graphics. Interest in reversible circuit is also sparked by its applications in several up-to-date technologies, such as Nanotechnology, Quantum Computing, Optical Computing, Quantum Dot Cellular Automata, and Low Power Adiabatic CMOS. However, the most important application of reversible circuits is in Quantum Computing. Logic synthesis methodologies for reversible circuits are very different from those for classical CMOS and other technologies. The dissertation introduces a new concept of reversible logic circuits synthesis based on EXOR-sum of Products-of-EXOR-sums (EPOE). The motivation for this work is to reduce the number of the multiple-controlled Toffoli gates as well as the numbers of their inputs. To achieve these reductions the research generalizes from the existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. The approaches can be applied to reversible and permutative quantum circuits to synthesize both completely and incompletely specified single-output functions as well as multiple-output functions. This dissertation describes the research intended to examine the methods to synthesize reversible circuits based on this new concept. The examinations indicate that the synthesis of reversible logic circuits based on EPOE approach produces circuits with significantly lower quantum costs than the common ESOP approach.

With the advancement of technology, submicron CMOSonly process is available now for Application Specific Integrated Circuits (ASICs). The high integration leads to the need for high pin counts. However voltage supply and ground bounce due to many output drivers switching at the same time is becoming a major problem. In this thesis, a CMOS offchip buffer design which generates ECL logic levels with lower ground bounce noise is described and demonstrated. The technique used in designing this buffer to reduce voltage noise differs from conventional design techniques. Traditionally there are two general methods to reduce ground bounce. One approach tries to reduce the instantaneous current change (di/dt) by increasing (prolonging) the rise and fall time of the signals. The other approach attempts to reduce the parasitic inductance attributed to packaging by using multiple supply pins. Our technique reduces the voltage noise by controlling the instantaneous current change through the reduction of current difference during switching time. Based on this approach, a novel circuit structure is designed. This circuit has a fully symmetrical configuration and is being selfbiased through negative feedback. A current injection technique is also used to increase the stability of the circuit. SPICE simulation of the proposed circuit is performed. Comparison and tradeoffs with other approaches are studied. / Graduation date: 1994

This thesis presents the implementation of some of the basic concepts of digital logic design in a fun and creative way with the help of paper electronics. This involves circuit building on paper using conductive tape or conductive ink and circuit components as electronics craft materials. Paper electronics toolkit called circuit sticker microcontroller which is deployed by a company named Chibitronics and AT89C51 microcontroller were used for the computational functioning of the circuits built on paper. This can be used to teach the fundamentals of digital logic design to the students in their early stage of studies in an attractive way and can help them them gain a better understanding. This thesis can also be helpful in grabbing the attention of high school students and motivate them towards choosing the engineering discipline for their higher studies.

The objective of this thesis is to automate the design of round-robin arbiter logic. The resulting arbitration logic is more than 1.8X times faster than the fastest prior state-of-the-art arbitration logic the author could find reported in the literature. The generated arbiter implemented in a single chip is fast enough in 0.25ьm CMOS technology to achieve terabit switching with a single chip computer network switch. Moreover, this arbiter is applicable to crossbar (Xbar) arbitration logic. The generated Xbar, customized according to user specifications, provides multiple communication paths among masters and slaves. As the number of transistors on a single chip increases rapidly, there is a productivity gap between the number of transistors available in a chip and the number of transistors per hour a chip designer designs. One solution to reduce this productivity gap is to increase the use of Silicon Intellectual Property (SIP) cores. However, a SIP core should be customized before being used in a system different than the one for which it was designed. Thus, to reconfigure the SIP core, either an engineer must spend significant effort altering the core by hand or else an enhanced CAD tool can automatically customize the core according to customer specifications. In this thesis, we present SIP generator tools for arbiter and Xbar generation. First, we introduce a Round-robin Arbiter Generator (RAG). The RAG can generate a hierarchical Bus Arbiter (BA) which is faster than all known previous approaches. RAG can also generate a hierarchical Switch Arbiter (SA) which is faster than all known previous approaches. Using a 0.25ьm TSMC standard cell library from LEDA Systems, we show the arbitration time of a 32x32 SA and demonstrate that our SA meets the time constraint to achieve terabit throughput. Furthermore, using a novel token-passing hierarchical arbitration scheme, our 32x32 SA performs better than the Ping-Pong Arbiter and Programmable Priority Encoder by factors of 1.8X and 2.3X, respectively, with less power dissipation. Finally, we present an Xbar switch Generator (X-Gt) tool that automatically configures a crossbar for a multiprocessor System-on-a-Chip (SoC). An Xbar is generated in Register Transfer Level (RTL) Verilog HDL.

Finding an optimal solution for the logic circuit design problem is challenging and time-consuming especially for complex logic circuits. As the number of logic gates increases the task of designing optimal logic circuits extends beyond human capability. A number of evolutionary algorithms have been invented to tackle a range of optimisation problems, including logic circuit design. This dissertation explores two of these evolutionary algorithms i.e. Gene Expression Programming (GEP) and Multi Expression Programming (MEP) with the aim of integrating their strengths into a new Genetic Programming (GP) algorithm. GEP was invented by Candida Ferreira in 1999 and published in 2001 [8]. The GEP algorithm inherits the advantages of the Genetic Algorithm (GA) and GP, and it uses a simple encoding method to solve complex problems [6, 32]. While GEP emerged as powerful due to its simplicity in implementation and exibility in genetic operations, it is not without weaknesses. Some of these inherent weaknesses are discussed in [1, 6, 21]. Like GEP, MEP is a GP-variant that uses linear chromosomes of xed length [23]. A unique feature of MEP is its ability to store multiple solutions of a problem in a single chromosome. MEP also has an ability to implement code-reuse which is achieved through its representation which allow multiple references to a single sub-structure. This dissertation proposes a new GP algorithm, Improved Gene Expression Programming (IGEP) which im- proves the performance of the traditional GEP by combining the code-reuse capability and simplicity of gene encoding method from MEP and GEP, respectively. The results obtained using the IGEP and the traditional GEP show that the two algorithms are comparable in terms of the success rate when applied on simple problems such as basic logic functions. However, for complex problems such as one-bit Full Adder (FA) and AND-OR Arithmetic Logic Unit (ALU) the IGEP performs better than the traditional GEP due to the code-reuse in IGEP / Mathematical Sciences / M. Sc. (Applied Mathematics)