Genetic data are the most sensitive information for a person, containing many specific features that uniquely determine an individual and also make it possible to trace relationships with other people or evaluate the predisposition to particular diseases.For this reason, any processing of genetic data should be carefully performed and any threat to their privacy properly considered.A very important computation in medical and public health domains involves the evaluation of the edit distance between human genomes, that can eventually lead to a better diagnosis of several diseases.To maintain the privacy of the genetic data, it is possible to apply secure computation protocols and then, in this context, the improvement of the computational performance of such techniques is a key factor for real-world application scenarios.In this paper we focus on the application of the garbling circuit technique for the computation of the edit distance, showing its efficiency.We apply the technique considering four different algorithms and compare their performances to the best previous results found in literature.We show that the Ukkonen algorithm with generalized cut-off is the one that performed better among the considered algorithms, reporting some experimental results obtained considering datasets composed of both randomly generated and real genomic strings.

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.

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.

The perfect phylogeny is a widely used model in phylogenetics, since it provides an effective representation of evolution of binary characters in several contexts, such as for example in haplotype inference. The model, which is conceptually the simplest among those actually used, is based on the in finite sites assumption, that is no character can mutate more than once in the whole tree. Since a large number of biological phenomena cannot be modeled by the perfect phylogeny, it becomes important to find generalizations that retain the computational tractability of the original model, but are more flexible in modeling biological data when the infinite site assumption is violated, e.g. because of back mutations. In this paper, we introduce a new model—called species-driven persistent phylogeny—and we study the relations between three different formulations: perfect phylogeny, persistent phylogeny, galled trees, and species-driven persistent phylogeny. The species-driven persistent phylogeny model is intermediate between the perfect and the persistent phylogeny, since a perfect phylogeny allows no back mutations and a persistent phylogeny allows each character to back mutate only once. We describe an algorithm to compute a species-driven persistent phylogeny and we prove that every matrix admitting a galled-tree also admits a species-driven persistent phylogeny.

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.

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.

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.

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.

In this paper, we present a model to derive statistical properties of digital noise due to logic transitions of gates in a fully CMOS combinational circuit. Switching activity of logic gates in a digital system is a deterministic process, depending on both circuit parameters and input signals. However, the huge number of logic blocks in a complex IC makes digital switching a cognitively stochastic process. For a combinational logic network, we can model digital switching currents as stationary shot noise processes, deriving both their amplitude distributions and their power spectral densities. From the spectra of digital currents, we can also calculate the spectral components and the rms value of disturbances injected into the on-chip power supply lines. The stochastic model for switching currents has been validated by comparing theoretical results with circuit simulations.

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.