Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites.

The Transduction Method is a powerful way to design logic circuits, utilizing already existing circuits. A set of permissible functions (SPF) plays an essential role in such circuit transformation/reduction, and is computed at each point (connection or gate output). Currently, two types of SPFs have been used: the maximum SPFs (MSPFs) and compatible SPFs (CSPFs). At each point, the MSPF is literally the set of all PF's, and CSPF is a subset of the MSPF. When CSPFs are calculated, priorities are first assigned to all gates in the circuit. Based on the priorities, it is decided which subset is to be selected as the CSPF. The quality of the results depends on the priorities. In this paper, the concept of super-sets of permissible functions (SSPFs) is introduced to reduce the effect of the priorities that CSPFs depend on. In order to loosen the dependency, each SSPF is computed to contain CSPFs which are candidates to be selected. The experimental results show that the SSPF-based Transduction Method has intermediate reduction capability and takes an intermediate computation time between the MSPF-based and CSPF-based ones. The capability and the time are considered as an acceptably good trade-off. In addition, without any transformations, since SSPFs are the maximum super-set, SSPFs are applicable for analyzing the maximum performance of the CSPF-based transformation, for comparison with the MSPF-based one. Theoretically, the number of connectable gate pairs detected by the MSPFs is 100%. According to the experimental results obtained using SSPFs, on average, 99% are detectable by SSPFs and 1% are detectable only by using the MSPFs. The results show that by using CSPFs, 72% of connectable gate pairs are detectable with any priority assignment and 99% (SSPFs capability) are detectable on average even when the best priorities are assigned. According to the experimental results of CSPF calculation with five priorities, 82% to 93% are practically detectable on average. This is the first quantitative analysis realized by SSPFs which compares the CSPF-based and MSPF-based Transduction Methods with respect to the coverage of PF's.

In this paper, we will discuss circuit minimization techniques based on the multiple output capability of FPGA blocks. Since previous methods only consider two independent output functions, we will discuss a more complicated case when the two functions are mutually related. We also discuss a method to maximize flexibility of a specified cell output in the given FPGA block. If a set of possible functions for a cell which will not change the FPGA output function is large, we call that the flexibility of this cell is high. The concept of Sets of Pairs of Functions to be Distinguished (SPFDs) introduced by Yamashita et al. is a powerful tool to minimize a given FPGA circuits. In this paper, an extension of the concept, Priority based SPFDs (PSPFDs) is introduced to maximize the flexibility of output functions realized by such internal cells. By using PSPFDs for our new method, we can utilize the multiple output capability very well. Combination with the previous methods with PSPFDs is also shown to be important. We have implemented these methods and applied them to MCNC benchmarks mapped into 5-variable function blocks. To make a comparison with other methods, we have implemented methods using well-known merging algorithms utilizing the same multiple output capability. Experimental results show that our methods can reduce the number of blocks in the initial circuits by 40% on average. This reduction ratio is 16% higher than that of previous methods.

The logic optimization based on redundancy addition and removal is one of methods which can deal with large-scale logic circuits. In this logic optimization a few redundant elements are added to a logic circuit, and then many other redundant elements which are generated by the redundancy addition are identified and removed. In this paper an optimization method based on redundancy addition and removal using implication relations is proposed. The advantage of the proposed method is to identify removable redundant elements with short time, because the proposed method directly identifies redundant elements using implication relations from two illegal signal assignments which are produced by redundancy addition. The experimental results compared this method with another method show that this method is faster than the another method without declining the optimization ability.

Our basic idea of generating random benchmark circuits, i.e., not generating them directly but applying random transformations to initial circuits was presented at DAC'94. In this paper we make the two major improvements towards the goal of random benchmarking: i.e., increasing the generality, the naturality, the security of random circuits: One is controlling fan-ins of logic gates in the random circuits, and the other is producing the initial circuit also at random but under some control of its on-set size and complexity. Experimental data claiming merits of those improvements are also given.

Over the last decade, research in the automatic synthesis and optimization of combinational logic has matured significantly; more recently, research has focused on sequential logic. Many of the paradigms for combinational logic have been extended and applied in the sequential domain. In addition, promising new directions for future research are being explored. In this paper, we survey some of the results of combinational synthesis and some recent results for sequential synthesis and then use these to view possible avenues for future sequential synthesis research. In particular we look at two related questions: deriving a set of permissible behaviors and using a minimizer to select the best behavior according to some optimization criteria. We examine these two issues in increasingly complex situations starting with a single-output function, and proceeding to a single multiple-output function, a network of single-output functions, a network of multiple-output functions, and then similar questions where function" is replaced by a finite state machine (FSM). We end with a discussion of a network of finite state machines and the problem of deriving the set of permissible FSM's and choosing a representative minimum one.

This paper presents a novel and successful logic synthesis method for optimizing ternary logic functions of any given number of input variables. A new optimization algorithm to synthesize and minimize an arbitrary ternary logic function of n-input variables can always lead this function to optimal or very close to optimal solution, where [n (n1)/2]1 searches are necessary to achieve the optimal solution. Therefore, the complexity number of this algorithm has been greatly reduced from O(3n) into O(n2). The advantages of this synthesis and optimization algorithm are: (1) Very easy logic synthesis method. (2) Algorithm complexity is O(n2). (3) Optimal solution can be obtained in very short time. (4) The method can solve the interconnection problems (interconnection delay) of VLSI and ULSI processors, where very fast and parallel operations can be achieved. A transformation method between operational and polynomial domains of ternary logic functions of n-input variables is also discussed. This transformation method is very effective and simple. Design of the circuits of GF(3) operators, addition and multiplication mod-3, have been proposed, where these circuits are composed of Josephson junction devices. The simulation results of these circuits and examples show the following advantages: very good performances, very low power consumption, and ultra high speed switching operation.

In this paper we propose a new timing optimization technique for multi-level networks by restructuring multiple nodes simultaneously. Multi-output subcircuits on critical paths are extracted and resynthesized so that the delays of the paths are reduced. The complete design space of the subcircuits is captured by Boolean relations, which allow us to perform more powerful resynthesis than previous approaches using don't cares. Experimental results are reported to show the effectiveness of the proposed technique.

Boolean unification is an algorithm to obtain the general solution of a given Boolean equation. Since a general solution provides a way to represent a complete don't care set, Boolean unification can be a powerful technique when applied to logic synthesis. In this paper we present various applications of Boolean unification to combinational logic synthesis. Three topics of combinational logic synthesis: redesign, multi-level logic minimization and minimization of Boolean relations are discussed. All these problems can be uniformly formalized as Boolean equations. Experimental results are also reported.