1,721,018 research outputs found
Error Resilient OBDDs
No full textOrdered Binary Decision Diagrams (OBDDs) are a widely used data structure for Boolean function manipulation. In particular, OBDDs are commonly used in CAD for the synthesis and verification of integrated circuits. The purpose of this paper is to design an error resilient version of this data structure, i.e., self- repairing OBDDs. We describe some strategies that make reduced OBDDs resilient to errors in the indexes, that are associated to the input variables, or in the edges. The solutions we propose allow to efficiently restore via software the corrupt OBDD without changing the data structure, but rather exploiting its inherent redundancy, as well as the redundancy introduced by its efficient implementations
Projected Don't Cares
No full textIn this paper we define and study the properties of projected don’t cares, a category of don’t cares dynamically built by the minimization algorithm during the synthesis phase. Our target is to exploit projected don’t cares properties in order to obtain more compact networks. In particular, we show the use of projected don’t care conditions in two synthesis techniques, i.e., using a Boolean and an algebraic algorithm. Experimental results show that in the Boolean case 65% of the considered benchmarks achieve more compact area when implemented using projected don’t cares. The benefit in the algebraic approach is reduced (35% of instances benefit from the proposed technique), even if there are examples with an interesting decrease of the area
Compact Quantum Circuits for Dimension Reducible Functions
No full textThe classical synthesis method for quantum oracles generally requires a reversible logic synthesis and a quantum compilation step. In the reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the quantum cost of the final quantum circuit. In this paper, we exploit function regularities for enabling efficient reversible synthesis. In particular, we propose and implement a new method for the quantum synthesis of Dimension reducible Boolean functions. The experimental results validate the proposed approach showing relevant gains in area
Index-resilient Zero-Suppressed BDDs: Definition and Operations
Full text linkZero-Suppressed Binary Decision Diagrams (ZDDs) are widely used data structures for representing and handling combination sets and Boolean functions. In particular, ZDDs are commonly used in CAD for the synthesis and verification of integrated circuits. The purpose of this article is to design an error-resilient version of this data structure: a self-repairing ZDD. More precisely, we design a new ZDD canonical form, called index-resilient reduced ZDD, such that a faulty index can be reconstructed in time O(k), where k is the number of nodes with a corrupted index. Moreover, we propose new versions of the standard algorithms for ZDD manipulation and construction that are error resilient during their execution and produce an index-resilient ZDD as output. The experimental results validate the proposed approach
Minimization of incompletely specified functions as three-level logic via Boolean relations
No full textAbstract—We study three-level implementations where the first two levels represent a standard PLA form with an AND- plane and an OR-plane. This implements a 2m-output SOP. The final stage consists of m two-input programmable LUTs. The PLA outputs are paired so that the LUT outputs implement a set of m given incompletely specified functions (ISFs). Such three-level structures have been studied previously where the final two-input operator was fixed, say an AND or an XOR resulting in an AND-OR-AND implementation or an AND- OR-XOR implementation. By using the LUT effectively, the composition of the AND-plane can be controlled to implement a set of cubes which have the maximum cube sharing. For each output, we characterize the problem of all legal implementations of such a model, by defining Boolean relations that capture all the don’t care conditions induced by any LUT logic. The extra LUT level provides a dimension beyond simple phase assignment. We performed experiments using a Boolean relation minimizer to compare such realizations vs. SOP forms and three-level forms, comparing areas and delays. To approximate the possible sharing in the AND plane, we mapped the 2-m PLA logic using SIS. We focused on two-input Boolean functions not captured by AND- OR-AND or AND-OR-XOR approaches and found good gains in many cases with affordable increases in synthesis runtimes
Complemented circuits
No full textWe study a three-level form, called {\em complemented circuit}, which implements a special type of decomposition of a Boolean function into two logic blocks, e.g., SOP forms, whose outputs feed a two-input Boolean operator or a two-input programmable LUT. Such structures have been studied previously with a final fixed two-input operator, say an AND or an XOR, resulting in an AND-OR-AND implementation or an AND-OR-XOR implementation. We characterize the problem of all legal implementations of such a model, by defining Boolean relations that capture all the don't care conditions induced by the chosen logic structure. For all 10 non-trivial two-input Boolean operators, we performed experiments using a Boolean relation minimizer to compare such realizations vs. SOP forms and other three-level forms, comparing areas and delays
Testability of Switching Lattices in the Stuck at Fault Model
No full textSwitching lattices are two-dimensional arrays of four-terminal switches proposed in a seminal paper by Akers in 1972 to implement Boolean functions. Recently, with the advent of a variety of emerging nanoscale technologies based on regular arrays of switches, synthesis methods targeting lattices of multi-terminal switches have found a renewed interest. In this paper, the testability under the stuck-at-fault model (SAFM) of switching lattices is analyzed, and properties of fully testable lattices are identified and discussed. Experimental results are given to analyze the testability of lattices synthesized with different methods
Exploiting Symmetrization and D-reducibility for Approximate Logic Synthesis
Full text linkApproximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, withinthe error tolerance of a given application, to reduce the complexity of the final implementation. We attack the problem by exploiting theallowed flexibility in order to maximize the regularity of the specified Boolean functions. Specifically, we consider two types of regularity:symmetryandD-reducibility, and contribute two algorithms to find, respectively, a symmetric and a D-reducible approximation of agiven target functionf, within the given error rate threshold if possible. When targeting symmetry, we characterize and computepolynomially the closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors inthe original incompletely specified Boolean function, with an unbounded number of errors; then, we discuss strategies to achievepartial symmetrization of the original specification while satisfying given error bounds. Finally, we present a polynomial heuristicalgorithm to compute a D-reducible approximation of an incompletely specified target function, under a bit error metric. Experimentalresults on classical and new benchmarks confirm the effectiveness of the proposed approaches
Computing the full quotient in bi-decomposition by approximation
Full text linkBi-decomposition is a design technique widely used to realize logic functions by the composition of simpler com- ponents. It can be seen as a form of Boolean division, where a given function is split into a divisor and quotient (and a remainder, if needed). The key questions are how to find a good divisor and then how to compute the quotient. In this paper we choose as divisor an approximation of the given function, and characterize the incompletely specified function which describes the full flexibility for the quotient. We report at the end preliminary experiments for bi-decomposition based on two AND-like operators with a divisor approximation from 1 to 0, and discuss the impact of the approximation error rate on the final area of the components in the case of synthesis by three-level XOR-AND-OR forms
Synthesis on switching lattices of Dimension-reducible Boolean functions
Full text linkIn this paper we study the switching lattice synthesis of a special class of regular Boolean functions called D-reducible functions. D-reducible functions are functions whose points are completely contained in an affine space A strictly smaller than the whole Boolean cube 0, 1n. The D-reducibility of a function can be exploited in the lattice synthesis process: the idea is to independently find lattice implementations for the characteristic function of the subspace A and for the projection of onto A, and to compose them in order to construct the lattice for. The overall lattice area can be further reduced exploiting the peculiar structure of the affine subspaces of 0, 1n. To this aim, we propose a method for implementing compact lattice representations of affine subspaces whose characteristic function is represented by the product of single literals and EXOR factors of two literals. The experimental results validate the proposed approach
- …
