1,721,073 research outputs found
Synthesis of SPP three-level logic networks using affine spaces
No full textRecently defined, three-level logic sum of pseudo-products (SPP) forms are EXOR-AND-OR networks representing Boolean functions, and are much shorter than standard two-level sum of products (SOP) expressions (Luccio and Pagli, 1999). The main disadvantages of SPP networks are their cumbersome theory in the original formulation and their high minimization time. In addition, the current technology cannot efficiently implement the unbounded fanin EXOR gates of SPP expressions. In this paper, we rephrase SPP theory in an algebraic context to obtain an easier description of the networks. We define a new model of SPP networks (k-SPP) with bounded fanin EXOR gates, whose minimization time is strongly reduced and whose minimal forms are still very compact. In the Boolean space {0, 1}n, a k-SPP form contains EXOR gates with at most k literals, where 1 ≤ k ≤ n. The limit case k = n corresponds to SPP networks and k = 1 to SOPs. Finally, we perform an extensive set of experiments on classical benchmarks. In order to validate our approach, the results are compared with those obtained for the major two- and three-level forms using standard metrics
Logic minimization using exclusive OR gates
No full textRecently introduced pseudoproducts and Sum of Pseudoproduct (SPP) forms have made possible to represent Boolean functions with much shorter expressions than standard Sum of Products (SP) forms LP99. A pseudo product is a product (AND) of Exclusive OR (EXOR) factors, and an SPP form is a sum (OR) of pseudoproducts. The synthesis of SPP minimal forms requires greater effort than SP minimization. In this paper we present a new data structure for this problem, leading to an efficient minimization method for SPP forms implemented with an exact algorithm and an heuristic. Experimental results on a classical set of benchmarks show that the new algorithms are fast, and can be applied to “complex” functions with a reasonable running time
SEPP: a New Compact Three-Level Logic Form
No full textCompact area, low delay, and fast synthesis time are important issues in logic circuit design. In order to orchestrate these main goals, this paper proposes a new algebraic three- level expression called sum of extended pseudoproducts (SEPP) with low delay and compact area. These forms are an extension of sum of pseudoproduct (SPP) three-level expressions. The paper proposes an efficient heuristic algorithm that gives compact solutions in a reduced synthesis time. A wide set of experimental results confirms that SEPP forms are often more compact than SPP forms, and their synthesis is always a fast reoptimization phase after SPP minimization
2-SPP: a practical trade-off between SP and SPP synthesis
No full textThe main result of this paper is a new minimization algorithm ad hoc for 2-SPP synthesis, exploiting the peculiar combinatorial properties of 2-SPP forms
Logic Synthesis and Testability of D-Reducible Functions
No full textIn logic synthesis, the “regularity” of a Boolean function can be exploited with the purpose of decreasing the cost of the corresponding algebraic expression or its minimization time. In this paper we study the synthesis of a class of regular Boolean functions called D-reducible. We propose two compact and testable representations of D-reducible non completely specified functions, called DRedSOP and 2DRedSOP. The experimental results show that a large percentage (about 70%) of the benchmark functions have at least a D-reducible output. The gain in area of the synthesized networks for such functions is, on average, 27% for DRedSOPs and 28% for 2DRedSOPs
Computing with nano-crossbar arrays: Logic synthesis and fault tolerance
Full text linkNano-crossbar arrays have emerged as a strong candidate technology to replace CMOS in near future. They are regular and dense structures, and can be fabricated such that each crosspoint can be used as a conventional electronic component such as a diode, a FET, or a switch. This is a unique opportunity that allows us to integrate well developed conventional circuit design techniques into nano-crossbar arrays. Motivated by this, our project aims to develop a complete synthesis and performance optimization methodology for switching nano-crossbar arrays that leads to the design and construction of an emerging nanocomputer. First two work packages of the project are presented in this paper. These packages are on logic synthesis that aims to implement Boolean functions with nano-crossbar arrays with area optimization, and fault tolerance that aims to provide a full methodology in the presence of high fault densities and extreme parametric variations in nano-crossbar architectures
Compact OBDDs for 2D-Reducible Functions
No full textThe “regularity” of a Boolean function can be exploited for decreasing the cost of its representation or its minimization time. In this paper we study a class of regular Boolean functions called 2D-reducible. We prove that 2D-reducible functions are partially symmetric and we exploit this property to propose a variable ordering for their OBDD representations. The detection of such variable ordering is very efficient since it is polynomial in the SOP representation of the Boolean function
The optimization of kEP-SOPs: Computational complexity, approximability and experiments
No full textWe propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NPNP-hard, but can be approximated within a fixed performance guarantee in polynomial time. Moreover, fully testable circuits under the stuck-at-fault model can be derived from kEP-SOPs by adding at most a constant number of multiplexer gates. The experiments show that the computational time is very short and the results are most of the time optimal with respect to the number of products involved. kEP-SOPs also prove experimentally a good starting point for general multilevel logic synthesis
- …
