Lecture

Boolean Optimization: MIGs and Majority Gates

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-472: Design technologies for integrated systems

Hardware compilation is the process of transforming specialized hardware description languages into circuit descriptions, which are iteratively refined, detailed and optimized. The course presents algorithms, tools and methods for hardware compilation an ...

Description

This lecture covers the optimization of Boolean functions using Majority-Inverter Graphs (MIGs) and Majority Gates. It explains the technology-independent logic representation in MIGs, the properties of MIGs, MIG Boolean Algebra, algebraic optimization, and exact synthesis of MIGs. The lecture also delves into Boolean rewriting, Majority-n functions, and the transformation of n-argument majority functions into 3-input majorities. It concludes with references on MIGs and their applications in logic optimization.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Giovanni De Micheli

Expertise Design technologies for integrated systems on silicon, such as synthesis, hw/sw codesign and low-power design, as well as systems on heterogeneous platforms including electrical and biological components. Scientific Director of EcoCloud Center at EPFL Directing activities towards creating sustainable computation including AI.Designing energy-savvy data centers and edge devices. More information Please read http://si2.epfl.ch/~demichel/ Giovanni De Micheli is a research scientist in electronics and

Official source

Related concepts (30)

Parity function

In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions. The output of the parity function is the parity bit. The -variable parity function is the Boolean function with the property that if and only if the number of ones in the vector is odd.

And-inverter graph

An and-inverter graph (AIG) is a directed, acyclic graph that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labeled with variable names, and edges optionally containing markers indicating logical negation. This representation of a logic function is rarely structurally efficient for large circuits, but is an efficient representation for manipulation of boolean functions.

Negation normal form

In mathematical logic, a formula is in negation normal form (NNF) if the negation operator (, ) is only applied to variables and the only other allowed Boolean operators are conjunction (, ) and disjunction (, ). Negation normal form is not a canonical form: for example, and are equivalent, and are both in negation normal form. In classical logic and many modal logics, every formula can be brought into this form by replacing implications and equivalences by their definitions, using De Morgan's laws to push negation inwards, and eliminating double negations.

Majority rule

Majority rule is the principle that the group that has the most supporters gets its way. A majority is more than half of the voters involved, and rule by such a majority is thought to be to the benefit of more than rule by less than half (a mere minority) would be. Majority rule is the binary decision rule most often used in decision-making bodies, including many legislatures of democratic nations. Where no one party wins a majority of the seats in a legislature, the majority of legislators that wields power is partly composed of members of other parties in support.

Majority

A majority, also called a simple majority or absolute majority to distinguish it from related terms, is more than half of the total. It is a subset of a set consisting of more than half of the set's elements. For example, if a group consists of 20 individuals, a majority would be 11 or more individuals, while having 10 or fewer individuals would not constitute a majority. "Majority" can be used to specify the voting requirement, as in a "majority vote", which means more than half of the votes cast.

Related lectures (3)

Optimizing Logic Functions

Covers the optimization of logic functions using Karnaugh diagrams and dealing with incomplete defined functions.

Logic Systems: Karnaugh Maps and TTL Gates

Explores Karnaugh maps, TTL gates, analog aspects of digital logic, and prime implicants.

Logic Synthesis: Designing Efficient Digital Circuits Log in to Mediaspace to watch this video