Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Binary decision diagram

Related publications (24)

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

IEEE2023

Automatic Uniform Quantum State Preparation Using Decision Diagrams

Giovanni De Micheli, Mathias Soeken, Heinz Riener, Fereshte Mozafari Ghoraba

Most quantum algorithms assume some specific initial state in superposition of basis states before performing the desired application-specific computations. The preparation of such states itself requires a computation performed by a quantum circuit. In thi ...

IEEE COMPUTER SOC2020

Extending Boolean Methods for Scalable Logic Synthesis

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Eleonora Testa, Luca Gaetano Amarù

In recent years, Boolean methods in logic synthesis have been drawing the attention of EDA researchers due to the continuous push to advance quality of results. Boolean methods require high computational cost, as they rely on complete functional properties ...

2020

The Complexity of Self-Dual Monotone 7-Input Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa, Winston Jason Haaswijk

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 i ...

2019

Logic Optimization of Majority-Inverter Graphs

Giovanni De Micheli, Mathias Soeken, Heinz Riener, Eleonora Testa, Luca Gaetano Amarù, Winston Jason Haaswijk

Majority-inverter graphs (MIGs) are a multi-level logic representation of Boolean functions with remarkable algebraic and Boolean properties that enable efficient logic optimizations beyond the capabilities of conventional logic representations. In this pa ...

VDE Verlag2019

Mapping Monotone Boolean Functions into Majority

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa, Winston Jason Haaswijk

We consider the problem of decomposing monotone Boolean functions into majority-of-three operations, with a particular focus on decomposing the majority-n function. When targeting monotone Boolean functions, Shannon's expansion can be expressed by a single ...

2018

Coordinate Descent with Bandit Sampling

Patrick Thiran, Laura Elisa Celis, Farnood Salehi

Coordinate descent methods usually minimize a cost function by updating a random decision variable (corresponding to one coordinate) at a time. Ideally, we would update the decision variable that yields the largest decrease in the cost function. However, f ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

Improvements to Boolean resynthesis

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù

In electronic design automation Boolean resynthesis techniques are increasingly used to improve the quality of results where algebraic methods hit local minima Boolean methods rely on complete functional properties of a logic circuit, preferably including ...

IEEE2018

Exact Synthesis of Majority-Inverter Graphs and Its Applications

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Mathias Soeken, Luca Gaetano Amarù

We propose effective algorithms for exact synthesis of Boolean logic networks using satisfiability modulo theories (SMT) solvers. Since exact synthesis is a difficult problem, it can only be applied efficiently to very small functions, having up to 6 varia ...

Ieee-Inst Electrical Electronics Engineers Inc2017

Exploiting Satisfiability Solvers for Efficient Logic Synthesis

Ana Petkovska

Logic synthesis is an important part of electronic design automation (EDA) flows, which enable the implementation of digital systems. As the design size and complexity increase, the data structures and algorithms for logic synthesis must adapt and improve ...

EPFL2017

Classifying Functions with Exact Synthesis

Giovanni De Micheli, Mathias Soeken, Eleonora Testa, Winston Jason Haaswijk

Due to recent advances, constraint solvers have become efficient tools for synthesizing optimum Boolean circuits. We take advantage of this by showing how SAT based exact synthesis may be used as a method for finding minimum length Boolean chains. As oppos ...

IEEE2017

Approximate BDD Optimization with Prioritized epsilon-Preferred Evolutionary Algorithm

Mathias Soeken

Approximate computing has gained high attention in various applications that can benefit from a reduction in costs by lowering the accuracy. In this paper we present an optimization approach for functional approximation of Binary Decision Diagrams (BDDs) w ...

Assoc Computing Machinery2016

Inversion optimization in majority-inverter graphs

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa

Many emerging nanotechnologies realize majority gates as primitive building blocks and they benefit from a majority-based synthesis. Recently, Majority-Inverter Graphs (MIGs) have been introduced to abstract these new technologies. We present optimi ...

Ieee2016

Reversible Logic Synthesis via Biconditional Binary Decision Diagrams

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Reversible logic synthesis is an emerging research area to aid the circuit implementation for multiple nano-scale technologies with bounded fan-out. Due to the inherent com- plexity of this problem, several heuristics are proposed in the literature. Among ...

2015

Majority logic synthesis

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

A method for optimizing an implementation of a logic circuit, comprising steps of providing an interpretation of the logic circuit in terms of 3 Boolean variable majority operators M, with each of the majority operators being a function of a plurality of v ...

2015

NEM Relay Design with Biconditional Binary Decision Diagrams

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Winston Jason Haaswijk

In this paper, we present an improved design flow for nanoelectromechanical (NEM) relay-based combinational logic circuits. Six-terminal NEM relays can be programmed to act as 2-to-1 multiplexers. We can therefore use NEM relays to implement arbitrary comb ...

IEEE2015

Biconditional Binary Decision Diagrams: A Novel Canonical Logic Representation Form

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

In this paper, we present biconditional binary deci- sion diagrams (BBDDs), a novel canonical representation form for Boolean functions. BBDDs are binary decision diagrams where the branching condition, and its associated logic expansion, is biconditional ...

2014

An Efficient Manipulation Package for Biconditional Binary Decision Diagrams

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Biconditional Binary Decision Diagrams (BBDDs) are a novel class of binary decision diagrams where the branching condition, and its associated logic expansion, is biconditional on two variables. Reduced and ordered BBDDs are remarkably compact and unique f ...

IEEE2014

Parallel symbolic execution on cluster of commodity hardware

George Candea, Cristian Zamfir, Stefan Bucur

A symbolic execution task is dynamically divided among multiple computing nodes. Each of the multiple computing nodes explores a different portion of a same symbolic execution tree independently of other computing nodes. Workload status updates are receive ...

2014

Biconditional BDD: A Novel Canonical BDD for Logic Synthesis targeting XOR-rich Functions

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

We present a novel class of decision diagrams, called Biconditional Binary Decision Diagrams (BBDDs), that enable efficient logic synthesis for XOR-rich functions. BBDDs are binary decision diagrams where the Shannon’s expansion is replaced by the bicondit ...

2013