Polynomial Formal Verification (PFV) ensures that a class of circuits can be verified efficiently by calculating polynomial upper bounds for the resource demands of the verification process. In this paper, we address the PFV of Boolean affine spaces represented by a 2-XOR sum of products. We show that time and space resources remain quadratic in the number of input variables during the entire verification process. Specifically, we prove that the dimensions of ROBDDs and QRBDDs representing a 2-affine space are linear. Furthermore, we prove that all ROBDDs generated during the symbolic simulation of the circuit can be computed in linear time. Finally, we provide an overall quadratic upper bound for the formal verification of QRBDD-based circuits. The experimental results confirm the given bounds.

Decentralized applications, the driving force behind the new Web3 paradigm, require continuous access to blockchain data. Their adoption, however, is hindered by the constantly increasing size of blockchains and the sequential scan nature of their read operations, which introduce a clear inefficiency bottleneck. Also, the growing amount of data recorded on the blockchain makes resource-constrained light nodes dependent on untrusted full nodes for fetching information, with a consequent need for query authentication protocols ensuring result integrity. Motivated by these reasons, in this paper we propose the skip index, an indexing data structure that allows users to quickly retrieve information simultaneously from multiple blocks of a blockchain. Our solution is also designed to be used as an authenticated data structure to guarantee the integrity of query results for light nodes. We discuss the theoretical properties of skip indices, propose efficient algorithms for their construction and querying, and detail their computational complexity. Finally, we assess the effectiveness of our proposal through an experimental evaluation on the Ethereum blockchain. As a reference use case, we focus on the popular CryptoKitties application and simulate a scenario where users seek to retrieve the events generated by the service. Our experimental results suggest that the use of skip indices offers a constant multiplicative speedup, thanks to search times that are at most logarithmic within a chosen search window. This allows to reduce the number of visited blocks by up to two orders of magnitude if compared to the naive sequential approach currently in use. • We propose the skip index, a data structure for efficient blockchain data retrieval. • The skip index provides guarantees about the integrity of query results. • We devise efficient algorithms to construct and query skip indices. • Compared to a sequential scan, skip indices offer a constant multiplicative speedup. • Skip indices experimentally provide a speedup of up to two orders of magnitude.

Bi-decomposition rewrites logic functions as the composition of simpler components. It is related to Boolean division, where a given function is rewritten as the product of a divisor and a quotient, but bi-decomposition can be defined for any Boolean operation of two operands. The key questions are how to find a good divisor and then how to compute the quotient. In this article, we select the divisor by approximation of the original function and then characterize by an incompletely specified function the full flexibility of the quotient for each binary operator. We target area-driven exact bi-decomposition, and we apply it to the bi-decomposition of Sum-of-Products (SOP) forms. We report experiments that exhibit significant gains in literals of SOP forms when rewritten as bi-decompositions with respect to the product operator. This suggests the application of this framework to other logic forms and binary operations, both for exact and approximate implementations.

Quantum computing, based on quantum theory, holds great promise as an advanced computational paradigm for achieving fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degrees of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms are theoretically faster than the classical algorithm, while experiments suggest that it is possible to obtain comparable clustering results.

The 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 syn-thesis. 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.

The promise of quantum computation to achieve a speedup over classical computation led to a surge of interest in exploring new quantum algorithms for data analysis problems.Feature Selection, a technique that selects the most relevant features from a dataset, is a critical step in data analysis.With several Quantum Feature Selection techniques proposed in the literature, this study exhibits the potential of quantum algorithms to enhance Feature Selection and other tasks that leverage the variance.This study proposes a novel quantum algorithm for estimating the variance over a set of real data.Importantly, after state preparation, the algorithm's complexity exhibits logarithmic characteristics in both its width and depth.The quantum algorithm applies to the Feature Selection problem by designing a Hybrid Quantum Feature Selection (HQFS) algorithm.This work showcases an implementation of HQFS and assesses it on two synthetic datasets and a real dataset.* This study was carried out within the National Centre on HPC, Big Data and Quantum Computing -SPOKE 10 (Quantum Computing) and received funding from the European Union Next-GenerationEU -National Recovery and Resilience Plan (NRRP) -MISSION 4, COMPONENT 2 -CUP N. I53C22000690001.This manuscript reflects only the authors' views and opinions, neither the European Union nor the European Commission can be considered responsible for them.

We propose a new three-level XOR-AND-XOR form for autosymmetric functions, called XORAX expression. In general, a Boolean function f over n variables is k-autosymmetric if it can be projected onto a smaller function fk, which depends on n-k variables only. We show that XORAX expressions can ease the reversible synthesis of autosymmetric functions, producing compact reversible networks, without inserting additional new input lines. Autosymmetry occurs especially for functions that exhibit a regular structure, as for instance arithmetic functions. For this reason, compact reversible networks for autosymmetric functions might be interesting for quantum computing. Experimental results validate the proposed approach.

A Reduced Ordered Binary Decision Diagram (ROBDD) is a data structure widely used in an increasing number of fields of Computer Science. In general, ROBDD representations of Boolean functions have a tractable size, polynomial in the number of input variables, for many practical applications. However, the size of a ROBDD, and consequently the complexity of its manipulation, strongly depends on the variable ordering: depending on the initial ordering of the input variables, the size of a ROBDD representation can grow from linear to exponential. In this paper, we study the ROBDD representation of Boolean functions that describe a special class of Boolean affine spaces, which play an important role in some logic synthesis applications. We first discuss how the ROBDD representations of these functions are very sensitive to variable ordering, and then provide an efficient linear time algorithm for computing an optimal variable ordering that always guarantees a ROBDD of size linear in the number of input variables.

With the rapid increasing availability of information and popularization of mobility devices, trajectories have become more complex in their form. Trajectory data is now high dimensional, and often associated with heterogeneous sources of semantic data, that are called Multiple Aspect Trajectories. The high dimensionality and heterogeneity of these data makes classification a very challenging task both in term of accuracy and in terms of efficiency. The present demo offers a tool, called AUTOMATISE, to support the user in the classification task of multiple aspect trajectories, specifically for extracting and visualizing the movelets, the parts of the trajectory that better discriminate a class. The AUTOMATISE integrates into a unique platform the fragmented approaches available in the literature for multiple aspects trajectories and, in general, for multidimensional sequence classification into a unique web-based and python library system. We illustrate the architecture and the use of the tool for offering both movelets visualization and a complete configuration of classification experimental settings.

XOR-AND Graphs (XAGs) are an enrichment of the classical AND-Inverter Graphs (AIGs) with XOR nodes. In particular, XAGs are networks composed by ANDs, XORs, and inverters. Besides several emerging technologies applications, XAGs are often exploited in cryptography-related applications based on the multiplicative complexity of a Boolean function. The multiplicative complexity of a function is the minimum number of AND gates (i.e., multiplications) that are sufficient to represent the function over the basis {AND, XOR, NOT}. In fact, the minimization of the number of AND gates is important for high-level cryptography protocols such as secure multiparty computation, where processing AND gates is more expensive than processing XOR gates. Moreover, it is an indicator of the degree of vulnerability of the circuit, as a small number of AND gates corresponds to a high vulnerability to algebraic attacks. In this paper we study the multiplicative complexity of Boolean functions characterized by two particular regularities, called autosymmetry and D-reducibility. Moreover, we exploit these regularities for decreasing the number of AND nodes in XAGs. The experimental results validate the proposed approaches.

Approximate synthesis is a recent trend in logic synthesis where one changes some outputs of a logic specification, within the error tolerance of a given application, to reduce the complexity of the final implementation. We attack the problem by exploiting the allowed 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 a given target function$f$, within the given error rate threshold if possible. When targeting symmetry, we characterize and compute polynomially the closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original incompletely specified Boolean function, with an unbounded number of errors; then, we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Finally, we present a polynomial heuristic algorithm to compute a D-reducible approximation of an incompletely specified target function, under a bit error metric. Experimental results on classical and new benchmarks confirm the effectiveness of the proposed approaches.

Autosymmetric Boolean functions are “regular functions” that are rather frequent in the set of Boolean functions describing standard circuits. Autosymmetry is typically exploited for improving the synthesis time and the quality of the optimized circuits. This paper studies in not a naive way, for the first time, the autosymmetry of incompletely specified functions, i.e., Boolean functions with don't care conditions. The theory of autosymmetry for completely specified functions is extended to the incompletely specified case and a new heuristic algorithm is provided for the detection of autosymmetry. The experimental results validate the theoretical study and show that the 77 % of the considered benchmarks has an improved autosymmetry degree.

We propose a new heuristic algorithm for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function f, based on a new algebraic criterion for product selection. The basic idea behind the new algorithm is to transform a given irredundant Sum-of-Products (SOP), i.e., a set of products covering the on-set minterms of f, into a disjoint SOP by repeated applications of two transformations. The first transformation selects pairs of suitable overlapping products in the initial SOP and replaces them with pairs of non-overlapping products covering the same minterms. By this step, some products are made disjoint, while keeping the overall number of products in the SOP unchanged. Next, a second transformation returns a completely disjoint SOP. By this second step, the number of products will increase. A set of experiments on a standard collection of combinational benchmarks shows that this new method is efficient and produces better results compared to the current best heuristic, achieving a 34.4% average cost reduction in about the 46% of the benchmarks, with less computation time.

Abstract In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

The multiplicative complexity of a Boolean function is the minimum number of AND gates (i.e., multiplications) that are sufficient to represent the function over the basis {AND, XOR, NOT}. The multiplicative complexity measure plays a crucial role in cryptography-related applications. In fact, the minimization of the number of AND gates is important for high-level cryptography protocols such as secure multiparty computation, where processing AND gates is more expensive than processing XOR gates. Moreover, it is an indicator of the degree of vulnerability of the circuit, as a small number of AND gates corresponds to a high vulnerability to algebraic attacks. In this paper we study a particular structure regularity of Boolean functions, called autosymmetry, and exploit it to decrease the number of ANDs in XOR-AND Graphs (XAGs), i.e., Boolean networks composed by ANDs, XORs, and inverters. The interest in autosymmetric functions is motivated by the fact that a considerable amount of standard Boolean functions of practical interest presents this regularity; indeed, about 24% of the functions in the classical ESPRESSO benchmark suite have at least one autosymmetric output. The experimental results validate the proposed approach.

Bi-decomposition is a design technique widely used to realize logic functions by the composition of simpler components. 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.

Approximate synthesis is a recent trend in logic synthesis that changes some outputs of a logic specification to take advantage of error tolerance of some applications and reduce complexity and consumption of the final implementation. We propose a new approach to approximate synthesis of combinational logic where we derive its closest symmetric approximation, i.e., the symmetric function obtained by injecting the minimum number of errors in the original function. Since BDDs of totally symmetric functions are quite compact, this approach is particularly convenient for BDD-based implementations, such as networks of MUXes directly mapped from BDDs. Our contribution is twofold: first we propose a polynomial algorithm for computing the closest symmetric approximation of an incompletely specified Boolean function with an unbounded number of errors; then we discuss strategies to achieve partial symmetrization of the original specification while satisfying given error bounds. Experimental results on classical and new benchmarks confirm the efficacy of the proposed approach.

A switching lattice is a two-dimensional array of four-terminal switches implemented in its cells. Each switch is linked to the four neighbors and is connected with them when the switch is ON, or is disconnected when the switch is OFF. Recently, with the advent of a variety of emerging nanoscale technologies based on regular arrays of switches, lattices of multi-terminal switches, originally introduced by Akers in 1972, have found a renewed interest. In this paper, the testability under the Cellular Fault Model (CFM) of switching lattices is defined and analyzed. Moreover, some techniques for improving the testability of lattices are discussed and experimentally evaluated.

Projected Sums of Products (PSOPs) are a Generalized Shannon Decomposition (GSD) with remainder that restructures a logic function into three logic blocks corresponding to a logic bi-decomposition plus a reminder generated by a cofactoring function. In this paper we discuss a Boolean synthesis technique for PSOPs, which exploits the fact that the resulting logical structure induces don't care conditions that can be exploited to reduce the problem of area minimization to Boolean relation minimization, with the guarantee that all valid realizations of the circuit are considered. This technique is more general than the algebraic methods investigated so far. Moreover, we characterize the points that are in the remainder with a simple procedure that implies a fast construction of the Boolean relation for important classes of cofactoring functions like the chain of XORs or ANDs. We report experiments confirming the effectiveness in area of the proposed approach based on Boolean relations, with better run times for some cost functions.

A non classical approach to the logic synthesis of Boolean functions based on switching lattices is considered, for which deriving a feasible layout has not been previously studied. The problem presents new interesting combinatorial and algorithmic aspects. Our basic assumptions are that the positions of the switches in the lattice are fixed in the synthesis stage, and the layout for connecting the subsets of switches with the same input literal must be realized in superimposed planes through vias that take the same switch area. The overall goal is to minimize the number of layers needed. Since multiple choices of input literals are possible for each switch, we first study how to assign a single literal to each switch, to minimize the number of lattice portions of adjacent cells associated to the same literal (Problem 1). Then we study how to derive a feasible layout by building connections onto different layers, to minimize the number of layers (Problem 2). Problem 1 is NP-hard. Problem 2 seems to be also intractable, and exhibits limit instances that require an exceedingly number of layers or are even unsolvable. Heuristic algorithms are then developed for both problems and their encouraging performances are proved on a set of known benchmarks.

Switching 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.

Multi-terminal switching lattices are typically exploited for modeling switching nano-crossbar arrays that lead to the design and construction of emerging nanocomputers. In this paper we propose a switching lattice optimization method for a special class of “regular” Boolean functions, called autosymmetric functions. Autosymmetry is a property that is frequent enough within Boolean functions to be interesting in the synthesis process. Each autosymmetric function can be synthesized through a new function (called restriction), depending on less variables and with a smaller on-set, which can be computed in polynomial time. In this paper we describe how to exploit the autosymmetry property of a Boolean function in oder to obtain a smaller lattice representation in a reduced minimization time. The original Boolean function can be constructed through a composition of the restriction with some EXORs of subsets of the input variables. Similarly, the lattice implementation of the function can be constructed using some external lattices for the EXORs, whose outputs will input the lattice implementing the restriction. Finally, the output of the restriction lattice corresponds to the output of the original function. Experimental results show that the total area of the obtained lattices is often significantly reduced. Moreover, in many cases, the computational time necessary to minimize the restriction is smaller than the time necessary to perform the lattice synthesis of the entire function.

Beyond CMOS, new technologies are emerging to extend electronic systems with features unavailable to silicon-based devices. Emerging technologies provide new logic and interconnection structures for computation, storage and communication that may require new design paradigms, and therefore trigger the development of a new generation of design automation tools. In the last decade, several emerging technologies have been proposed and the time has come for studying new ad-hoc techniques and tools for logic synthesis, physical design and testing. The main goal of this project is developing a complete synthesis and optimization methodology for switching nano-crossbar arrays that leads to the design and construction of an emerging nanocomputer. New models for diode, FET, and four-terminal switch based nanoarrays are developed. The proposed methodology implements both arithmetic and memory elements, necessitated by achieving a computer, by considering performance parameters such as area, delay, power dissipation, and reliability. With combination of arithmetic and memory elements a synchronous state machine (SSM), representation of a computer, is realized. The proposed methodology targets variety of emerging technologies including nanowire/nanotube crossbar arrays, magnetic switch-based structures, and crossbar memories. The results of this project will be a foundation of nano-crossbar based circuit design techniques and greatly contribute to the construction of emerging computers beyond CMOS. The topic of this project can be considered under the research area of "Emerging Computing Models" or "Computational Nanoelectronics", more specifically the design, modeling, and simulation of new nanoscale switches beyond CMOS.

In this paper we propose a novel approach to the synthesis of minimal-sized lattices, based on the decomposition of logic functions. Since the decomposition allows to obtain circuits with a smaller area, our idea is to decompose Boolean functions with separate lattices, according to the P-circuits decomposition scheme, and then to implement the decomposed blocks with physically separated regions in a single lattice. Experimental results show that about 35% of the considered benchmarks achieve a smaller area when implemented using the proposed decomposition for switching lattices, with an average gain of at least 24%.

In 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, 1}n. The D-reducibility of a function f 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 f onto A, and to compose them in order to construct the lattice for f. The overall lattice area can be further reduced exploiting the peculiar structure of the affine subspaces of {0, 1}n. 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.

Zero-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.

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). Three-level structures have been studied previously, e.g. resulting in ANDOR-AND or AND-OR-XOR implementations. By using the LUT effectively, the composition of the AND-plane can be controlled to implement a PLA which has the optimum phase assignment for 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 flexibility induced by the final 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 published three-level forms, comparing areas and delays. To approximate the possible sharing in the PLA, we mapped the 2m PLA logic using SIS. We focused on experiments with 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.

Autosymmetric functions are particular "regular" Boolean functions that are exploited for logic optimization, since it is possible to reduce the number of variables and the number of points of the original autosymmetric function before its synthesis. In this paper we study this regularity in oder to derive a suitable variable ordering for Biconditional Binary Decision Diagrams (BBDDs). BBDDs are a new version of BDD that have EXOR of two variables (instead of a variable) in the nodes. These diagrams are employed for logic synthesis in new technologies such as silicon nanowires and DG-SiNWFETs. We show that it is possible to find a useful variable ordering for these functions and the experimental results validate our approach showing that in the 97% of the cases we get an ordering that gives a number of nodes that is lower or equal to the one obtained with the standard ordering.

In this paper we study the problem of characterizing and exploiting the complete flexibility of a special logic architecture, called P-circuits, which realize a Boolean function by projecting it onto overlapping subsets given by a generalized Shannon decomposition. P-circuits are used to restructure logic by pushing some signals towards the outputs. The algorithms proposed so far for exploiting the structural flexibility of P-circuits do not guarantee to find the best implementation, because they cast the problem as the minimization of an incompletely specified function. Instead, here we show that to explore all solutions we must set up the problem as the minimization of a Boolean relation, because there are don't care conditions that cannot be expressed by single cubes. Finally we report the results obtained using a minimizer of Boolean relations, which improve in a major way with respect to the previous literature.

We propose an approximate logic synthesis heuristic for synthesizing a 2-SPP circuit under a given error rate threshold. 2-SPP circuits are three-level EXOR-AND-OR forms with EXOR gates restricted to fan-in 2. They represent a direct generalization of SOP forms, obtained generalizing cubes to "2-pseudocubes" where literals in cubes may be replaced by 2-EXOR factors in 2-pseudocubes. We discuss and experimentally evaluate two different measures for the error: the bit threshold and the minterm threshold. The first metric considers the overall number of complemented output bits, while the second metric is related to the number of input vectors on which the output computed by the circuit is different from the exact one on at least one bit. Experimental results confirm the effectiveness of the proposed approach. For an error rate threshold of 1%, our heuristic for approximate 2-SPP synthesis provides an average reduction of the number of 2-pseudocubes in the cover of about 23% for all the considered benchmarks, when we consider the bit threshold error metric. The reduction in the number of 2-pseudocubes is interesting even in the minterm threshold error metric, especially when we perform the resynthesis of the derived approximate versions of the benchmarks: the average gain, without resynthesis is of about 8%, while the average gain with resynthesis becomes 15%.

In this paper, we investigate how to use the complete flexibility of P-circuits, which realize a Boolean function by projecting it onto overlapping subsets given by a generalized Shannon decomposition. It is known how to compute the complete flexibility of P-circuits, but the algorithms proposed so far for its exploitation do not guarantee to find the best implementation, because they cast the problem as the minimization of an incompletely specified function. Instead, here we show that to explore all solutions we must set up the problem as the minimization of a Boolean relation, because there are don't care conditions that cannot be expressed by single cubes. In the experiments we report major improvements with respect to the previously published results.

Ordered 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.

Generalized Shannon decomposition with remainder restructures a logic function into subsets of points defined by the generalized cofactors with a remainder, yielding three logic blocks. EXOR-Projected Sums of Products (EP-SOPs) are an important form of such decomposition. In this paper we propose a Boolean synthesis technique for EP-SOPs, more general than the algebraic methods investigated so far. We exploit the don't care conditions induced by the structure of the implementation, by casting synthesis for minimum area as a problem of Boolean relation minimization that captures all valid implementations of the circuit, obtaining by construction the most compact one. We report experiments confirming the effectiveness in area of the proposed approach based on Boolean relations, with better run times for some cost functions.

In 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.

Boolean functional decomposition techniques built on top of Shannon cofactoring have been discussed in various applications of logic synthesis targeting reductions in area, delay and power. In this paper we investigate a generalization of decomposition based on Shannon cofactoring by means of non-orthonormal projection functions. We provide an approximation algorithm, by showing a constant approximation ratio between its result and the best solution. Experimental results in logic restructuring to reduce area and switching power show significant gains with respect to standard Shannon cofactoring, for even shorter computation time.

We define and study a new class of regular Boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller than n . We show that the D-reducibility property can be efficiently tested, in time polynomial in the representation of f , that is, an initial SOP form of f . A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DredSOP. This form is shown here to be generally smaller than the corresponding minimum SOP form. Our experiments have also shown that a great number of functions of practical importance are indeed D-reducible, thus validating the overall interest of our approach.

In 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.

We investigate restructuring techniques based on decomposition/factorization, with the objective to move critical signals toward the output while minimizing area. A specific application is synthesis for minimum switching activity (or high performance), with minimum area penalty, where decompositions with respect to specific critical variables are needed (the ones of highest switching activity for example). In this paper we describe new types of factorization that extend Shannon cofactoring and are based on projection functions that change the Hamming distance of the original minterms and on appropriate don't care sets, to favor logic minimization of the component blocks. We define two new general forms of decomposition that are special cases of the pattern F = G(H(X),Y). The related implementations, called P-Circuits, show experimentally promising results in area with respect to Shannon cofactoring.

We investigate a form of logic decomposition that generates a 2SPP-P-circuit, which includes two blocks representing the projected subfunctions obtained by Shannon cofactoring with respect to a chosen variable, and a block representing the intersection of the projections. The three blocks are implemented as minimal 2-SPP forms (XOR-ANDOR with XOR restricted to two inputs). The minimization is performed using as don't care set the points in the intersection of the projections. This structure can be used in synthesis for low power or low delay, to move critical signals (e.g., with highest switching activity) toward the outputs with minimum area penalty. We prove an estimate by which the area of a 2SPP-P-circuit has at most twice the terms than its equivalent standard 2-SPP circuit (with no Shannon cofactoring). We also argue that the procedure delivers a circuit (when augmented with a pair of multiplexers) fully testable under the single stuck-at-fault model. We implemented the proposed synthesis procedure and we present encouraging results compared with standard 2-SPPs and SOPs.

This paper introduces a new bounded multi-level algebraic form, called projected sum of products (P-SOP), based on projections of minimal SOP forms onto subsets of the Boolean space. After a standard two-level logic minimization, this technique can be used as a very fast postprocessing step for further minimizing the circuit area, increasing the depth of the network by only a constant value. The proposed synthesis algorithms have been implemented and tested with interesting results, which show how about 75% of standard Espresso benchmarks benefit from this postprocessing phase.

The 2-SPP networks are three-level EXOR-AND-OR forms, with EXOR gates being restricted to fan-in 2. This paper presents a heuristic algorithm for the synthesis of these networks in a form that is fully testable in the stuck-at fault model (SAFM). The algorithm extends the EXPAND-IRREDUNDANT-REDUCE paradigm of ESPRESSO in heuristic mode, and it iterates local minimization and reshape of a solution until no further improvement can be achieved. This heuristic could escape from local minima using a LAST_GASP-like procedure. Moreover, the testability of 2-SPP networks under the SAFM is studied, and the notion of EXOR-irredundancy is introduced to prove that the computed 2-SPP networks are fully testable under the SAFM. Finally, this paper reports a large set of experiments showing high-quality results with affordable run times, handling also examples whose exact solutions could not be computed.

We propose a new algebraic four-level expression called k-EXOR-projected sum of products (kEP-SOP). The optimization of a kEP-SOP is NP NP -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.

During synthesis of circuits for Boolean functions area, delay and testability are optimization goals that often contradict each other. Multi-level circuits are often quite small while circuits with low depth are often larger regarding the area requirements. A different optimization goal is good testability which can usually only be achieved by additional hardware overhead. In this paper we propose a synthesis technique that allows to trade-off between area and delay. Moreover, the resulting circuits are 100% testable under the stuck-at fault model. The proposed approach relies on the combination of 100% testable circuits derived from binary decision diagrams and 2-SPP networks. Full testability under the stuck-at fault model is proven and experimental results show the trade-off between area and depth.

Multi-level logic synthesis yields much more compact expressions of a given Boolean function with respect to standard two-level sum of products (SOP) forms. On the other hand, minimizing an expression with more than two-levels can take a large time. In this paper we introduce a novel algebraic four-level expression, named k-EXOR-projected sum of products (kEP-SOP) form, whose synthesis can be performed in polynomial time with an approximation algorithm starting from a minimal SOP. Our experiments show that the resulting networks can be obtained in very short computational time and often exhibit a high quality. We also study the testability of these networks under the Stuck-at-fault model, and show how fully testable circuits can be generated from them by adding at most a constant number of multiplexer gates.

The paper presents a heuristic algorithm for the minimization of 2-SPP networks, i.e., three-level EXOR-AND-OR forms with EXOR gates restricted to fan-in 2. Previous works had presented exact algorithms for the minimization of unrestricted SPP networks and of 2-SPP networks. The exact minimization procedures were formulated as covering problems as in the minimization of SOP forms and had worst-case exponential complexity. Extending the expand-irredundant-reduce paradigm of the Espresso heuristic, we propose a minimization algorithm for 2-SPP networks that iterates local minimization and reshape of a solution until further improvement. We introduce also the notion of EXOR-irredundant to prove that OR-AND-EXOR irredundant networks are fully testable and guarantee that our algorithm yields OR-AND-EXOR irredundant solutions. We report a large set of experiments showing impressive high-quality results with affordable run times, handling also examples whose exact solutions could not be computed

In this paper we characterize and study a new class of regular Boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in a space of dimension strictly smaller than n. A D-reducible function can be efficiently decomposed, giving rise to a new logic form, that we have called DRedSOP. This form is often smaller than the corresponding minimum SOP form. Experimental evidence shows that such functions are rather common and D-reducibility can be tested very quickly

In this paper, the authors introduce a new algebraic form for Boolean function representation, called EXOR-projected sum of products (EP-SOP), resulting in a four level network that can be easily implemented in practice. The authors prove that deriving an optimal EP-SOP from an optimal sum of products (SOP) form is a hard problem (NPNP-hard); nevertheless the authors propose a very efficient approximation algorithm, which returns in polynomial time an EP-SOP form whose cost is guaranteed to be near the optimum. Experimental evidence shows that for about 35% of the classical synthesis benchmarks the EP-SOP networks have a smaller area and delay with respect to the optimal SOPs (sometimes gaining even 40-50% of the area). Since the computational times required are extremely short, the authors recommend the use of the proposed approach as a postprocessing step after SOP minimization

Full testability is a desirable property for a minimal logic network. The classical minimal two-level sum of products (SOP) networks are fully testable in some standard fault models. In this paper, the authors investigate the testability of recently introduced three-level logic forms sum of pseudoproducts (SPP), which allow the representation of Boolean functions with much shorter expressions than two-level forms. The authors study their testability under static fault models (FMs), i.e., the stuck-at-fault model (SAFM) and the cellular fault model (CFM). For SPP networks, several minimal forms can be considered. While full testability can be proven in the SAFM for some forms, SPP networks in the CFM are shown to contain redundancies. Finally, the authors propose a method for transforming nontestable networks into testable ones. In the SAFM, the resulting irredundant networks are still minimal. The experimental results are given to demonstrate the efficiency of the approach

We exploit the "regularity" of Boolean functions with the purpose of decreasing the time for constructing minimal three-level expressions, in the sum of pseudoproducts (SPP) form recently developed. The regularity of a Boolean function f of n variables can be expressed by an autosymmetry degree k (with 0 /spl les/ k /spl les/ n). k = 0 means no regularity, that is we are not able to provide any advantage over standard synthesis. For k /spl ges/ 1 the function f is said to be autosymmetric, and a new function f/sub k/ depending on n - k variables only, called the restriction of f, is identified in time polynomial in the number of points of f. The relation between f and f/sub k/ is discussed in depth to show how a minimal SPP form for f can be build in linear time from a minimal SPP form for f/sub k/. The concept of autosymmetry is then extended to functions with don't care conditions, and the SPP minimization technique is duly extended to such functions. A large set of experimental results is presented, showing that 61% of the outputs for the functions in the classical ESPRESSO benchmark suite are autosymmetric. The minimization time for such functions is critically reduced, and cases otherwise intractable are solved. The quality of the corresponding circuits, measured with some well established cost functions, is also improved. Finally, we discuss the role and meaning of autosymmetric functions, and why a great amount of functions of practical interest fall in this class.

Sum of Pseudoproducts (SPP) is a three level logic synthesis technique developed in recent years. In this framework we exploit the "regularity" of Boolean functions to decrease minimization time. Our main results are: 1) the regularity of a Boolean function f of n variables is expressed by its autosymmetry degree k (with 0 ≤ k ≤ n), where k = 0 means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for k ≥ 1 the function is autosymmetric, and a new function fk is identified in polynomial time; fk is "equivalent" to, but smaller than f, and depends on n-k variables only; 3) given a minimal SPP form for fk a minimal SPP form for f is built in linear time; 4) experimental results show that 61% of the functions in the classical Espresso benchmark suite are autosymmetric, and the SPP minimization time for them is critically reduced; we can also solve cases otherwise practically intractable. We finally discuss the role and meaning of autosymmetry.

In this paper, we prove that bent functions can be precisely characterized in terms of a special class of strongly regular graphs, thus providing a positive answer to a question raised in the paper by A. Bernasconi and B. Codenotti (1999).

Several problems in digital logic can be conveniently approached in the spectral domain. In this paper we show that the Walsh spectrum of Boolean functions can be analyzed by looking at algebraic properties of a class of Cayley graphs associated with Boolean functions. We use this idea to investigate the Walsh spectrum of certain special functions.