Structural Rewriting in XOR-Majority Graphs

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.

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

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

We present LISA, a proof system and proof assistant for constructing proofs in schematic first-order logic and axiomatic set theory. The logical kernel of the system is a proof checker for first-order logic with equality and schematic predicate and fun ...

Approximate logic synthesis techniques have become popular in error-resilient systems, where accuracy requirements can be traded for improved energy efficiency. Many of these techniques operate on a circuit by substituting or removing some of its portions ...

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates r ...

Emerging reconfigurable nanotechnologies allow the implementation of self-dual functions with a fewer number of transistors as compared to traditional CMOS technologies. To achieve better area results for Reconfigurable Field-Effect Transistors (RFET)-base ...

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

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

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

Given a set of logic primitives and a Boolean function, exact synthesis finds the optimum representation (e.g., depth or size) of the function in terms of the primitives. Due to its high computational complexity, the use of exact synthesis is limite ...

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

Hard-wired carry chains in FPGAs are designed to improve efficiency of important arithmetic primitives. Although they are proven to be effective for arithmetic-rich functions, there are very few studies on the optimization opportunities of carry chains for ...

Binary logic operations are the building blocks of computing machines. In this paper, we present a new programmable binary logic gate based on programmable multistable mechanisms (PMM), which are multistable structures whose stability behavior depends on m ...

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Staging has proved a successful technique for programmatically removing code abstractions, thereby allowing for faster program execution while retaining a high-level interface for the programmer. Unfortunately, techniques based on staging suffer from a num ...

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional logic systems. Also, the B ...

We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on lookup-table (urn networks, which play a key role in conventional logic synthesis. Establishing a connection between LUT ...

The failure detector approach for solving distributed computing problems has been celebrated for its modularity. This approach allows the construction of algorithms using abstract failure detection mechanisms, defined by axiomatic properties, as building b ...

A Majority-Inverter Graph (MIG) is a recently introduced logic representation form whose algebraic and Boolean properties allow for efficient logic optimization. In particular, when considering logic depth reduction, MIG algorithms obtained signific ...

Structural Rewriting in XOR-Majority Graphs

Chat with Graph Search

Scalable Logic Rewriting Using Don’t Cares

Orthologic with Axioms

LISA – A Modern Proof System

A Formal Framework for Maximum Error Estimation in Approximate Logic Synthesis

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Further Results on Efficient Implementations of Block Cipher Linear Layers

Preserving Self-Duality During Logic Synthesis for Emerging Reconfigurable Nanotechnologies

Three-Input Gates for Logic Synthesis

Exact Synthesis of Majority-Inverter Graphs and Its Applications

Data Structures and Algorithms for Logic Synthesis in Advanced Technologies

A Novel Basis for Logic Rewriting

Advanced Functional Decomposition Using Majority and Its Applications

Improving Circuit Mapping Performance Through MIG-based Synthesis for Carry Chains

Programmable Logic Gates Based On Tunable Multistable Mechanisms

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Quoted Staged Rewriting: A Practical Approach to Library-Defined Optimizations

A Sound and Complete Axiomatization of Majority-n Logic

LUT-Based Hierarchical Reversible Logic Synthesis

Never Say Never Probabilistic & Temporal Failure Detectors

Optimizing Majority-Inverter Graphs with Functional Hashing