**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Three-Input Gates for Logic Synthesis

Giovanni De Micheli, Dewmini Sudara Marakkalage, Heinz Riener, Mathias Soeken, Eleonora Testa

*IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, *2021

Journal paper

Journal paper

Abstract

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 primarily on graphs with 2-input nodes such as AND and OR gates, the recently proposed paradigm of Majority-Inverter Graphs (MIGs) instead uses the 3-input Majority gate as the node function. As this technique proved to be a success, it is natural to ask: are there other 3-input gates better suited for logic synthesis? Motivated by this question, we investigate the relative advantages of 3-input gates as constituents of logic networks. We consider representative gates from each of the ten nondegenerate 3-input NPN classes and study how powerful they are at representing Boolean functions. Using SAT-based exact synthesis, we evaluate each 3-input gate using the minimum number of such gates (together with inverters) needed to synthesize all 4-input Boolean functions and a subset of frequent 5-input and 6-input Boolean functions. We show that the logic gate Dot(x,y, z) := x circle plus (z boolean OR xy) outperforms the rest in terms of expressive power. We further confirm this observation by showing that Dot-Inverter Graph representations are more than 14% smaller as compared to MIG representations of EPFL benchmarks.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related concepts (6)

Logic gate

A logic gate is an idealized or physical device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output.
Depending on the

Paradigm

In science and philosophy, a paradigm (ˈpærədaɪm ) is a distinct set of concepts or thought patterns, including theories, research methods, postulates, and standards for what constitute legitimate co

Boolean algebra

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false,

Related publications

No results