Publication
Exact Synthesis of Boolean Functions in Majority-of-five Forms
Related publications (51)
Scalable Logic Rewriting Using Don’t Cares
Giovanni De Micheli, Alessandro Tempia Calvino
Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. ...
2024Improving Standard-Cell Design Flow using Factored Form Optimization
Giovanni De Micheli, Alessandro Tempia Calvino
Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals in a factored form correlates strongly with the number of ...
New York2023Three-Input Gates for Logic Synthesis
Giovanni De Micheli, Mathias Soeken, Dewmini Sudara Marakkalage, Eleonora Testa, Heinz Riener
Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition
Giovanni De Micheli, Heinz Riener, Siang-Yun Lee
Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...
IEEE2021A Majority Lemma for Randomised Query Complexity
Mika Tapani Göös, Gilbert Théodore Maystre
We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021Learning from survey propagation: a neural network for MAX-E-3-SAT
Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algo ...
IOP PUBLISHING LTD2021Data Structures and Algorithms for Logic Synthesis in Advanced Technologies
Logic synthesis is a key component of digital design and modern EDA tools; it is thus an essential instrument for the design of leading-edge chips and to push the limits of their performance. In the last decades, the electronic circuits community has evolv ...
EPFL2020Enumerating Optimal Quantum Circuits using Spectral Classification
Giovanni De Micheli, Mathias Soeken, Giulia Meuli
This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean funct ...
IEEE2020Enumerating Optimal Quantum Circuits using Spectral Clasification
Giovanni De Micheli, Mathias Soeken, Giulia Meuli
This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean funct ...
2020Advanced Functional Decomposition Using Majority and Its Applications
Giovanni De Micheli, Mathias Soeken, Zhufei Chu
Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a de ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020