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

Concept# Combinational logic

Summary

In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic ) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has memory while combinational logic does not.
Combinational logic is used in computer circuits to perform Boolean algebra on input signals and on stored data. Practical computer circuits normally contain a mixture of combinational and sequential logic. For example, the part of an arithmetic logic unit, or ALU, that does mathematical calculations is constructed using combinational logic. Other circuits used in computers, such as half adders, full adders, half subtractors, full subtractors, multiplexers, demultiplexers, encoders and decoders are also made by using combi

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 publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

No results

Related publications (3)

Related people

No results

Loading

Loading

Loading

Related concepts (17)

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

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,

Sequential logic

In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history.

Related courses (11)

EE-530: Test of VLSI systems

Test of VLSI Systems covers theoretical knowledge related to the major algorithms used in VLSI test, and design for test techniques. Basic knowledge related to computer-aided design for test techniques, and their integration into a design-flow are presented.

EE-334: Digital systems design

Students will acquire basic knowledge about methodologies and tools for the design, optimization, and verification of custom digital systems/hardware.
They learn how to design synchronous digital circuits on register transfer level, analyse their timing and implement them in VHDL and on FPGAs.

EE-110: Logic systems (for MT)

Ce cours couvre les fondements des systèmes numériques. Sur la base d'algèbre Booléenne et de circuitscombinatoires et séquentiels incluant les machines d'états finis, les methodes d'analyse et de synthèse de systèmelogiques sont étudiées et appliquée

Fengyun Liu, Martin Odersky, Aleksandar Prokopec

Claude Shannon, in his famous thesis (1938), revolutionized circuit design by showing that *Boolean algebra* subsumes all ad-hoc methods that are used in designing switching circuits, or combinational circuits as they are commonly known today. But what is the calculus for sequential circuits? Finite-state machines (FSM) are close, but not quite, as they do not support arbitrary parallel and hierarchical composition like that of Boolean expressions. We propose an abstraction called *implicit state machine* (ISM) that supports parallel and hierarchical composition. We formalize the concept and show that any system of parallel and hierarchical ISMs can be flattened into a single flat FSM without exponential blowup. As one concrete application of implicit state machines, we show that they serve as an attractive abstraction for digital design and logical synthesis.

2020,

We present an algorithm for computing both functional dependency and unateness of combinational and sequential Boolean func- tions represented as logic networks. The algorithm uses SAT-based tech- niques from Combinational Equivalence Checking (CEC) and Automatic Test Pattern Generation (ATPG) to compute the dependency matrix of multi-output Boolean functions. Additionally, the classical dependency definitions are extended to sequential functions and a fast approximation is presented to efficiently yield a sequential dependency matrix. Exten- sive experiments show the applicability of the methods and the improved robustness compared to existing approaches.

Mario Bucev, Simon Guilloud, Viktor Kuncak

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem for two subtheories of Boolean algebra, giving a sound procedure for propositional logical equivalence that is incomplete in general but complete with respect to a subset of Boolean algebra axioms. We first show a new algorithm to produce a normal form for expressions in the theory of ortholattices (OL) in time O(n^2). We also consider an algorithm, recently presented but never evaluated in practice, producing a normal form for a slightly weaker theory, orthocomplemented bisemilattices (OCBSL), in time O(n log(n)^2). For both algorithms, we present an implementation and show efficiency in two domains. First, we evaluate the algorithms on large propositional expressions, specifically combinatorial circuits from a benchmark suite, as well as on large random formulas. Second, we implement and evaluate the algorithms in the Stainless verifier, a tool for verifying the correctness of Scala programs. We used these algorithms as a basis for a new formula simplifier, which is applied before valid verification conditions are saved into a persistent cache. The results show that normalization substantially increases cache hit ratio in large benchmarks.

2022Related lectures (39)