Combinational logic
Encyclopedia
In digital circuit
theory, combinational logic (sometimes also referred to as combinatorial logic) is a type of digital logic which is implemented by boolean circuit
s, 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 do 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, multiplexer
s, demultiplexer
s, encoder
s and decoder
s are also made by using combinational logic.
:
Using sum of products, we take the sum of all logical statements which yield true results. Thus, our result would be:
It could then be simplified using Boolean algebra to:
With the use of minimization, a simplified logical function or circuit may be arrived at, and the logic combinational circuit becomes smaller, and easier to analyse, use, or build.
Digital circuit
Digital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
theory, combinational logic (sometimes also referred to as combinatorial logic) is a type of digital logic which is implemented by boolean circuit
Boolean circuit
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...
s, where the output is a pure function
Pure function
In computer programming, a function may be described as pure if both these statements about the function hold:# The function always evaluates the same result value given the same argument value...
of the present input only. This is in contrast to sequential logic
Sequential logic
In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present input but also on the history of the input. This is in contrast to combinational logic, whose output is a function of, and only of, the present input...
, 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
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
while combinational logic does not.
Combinational logic is used in computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
circuits to do 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
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
, 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, multiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...
s, demultiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...
s, encoder
Encoder
An encoder is a device, circuit, transducer, software program, algorithm or person that converts information from one format or code to another, for the purposes of standardization, speed, secrecy, security, or saving space by shrinking size.-Media:...
s and decoder
Decoder
A decoder is a device which does the reverse operation of an encoder, undoing the encoding so that the original information can be retrieved. The same method used to encode is usually just reversed in order to decode...
s are also made by using combinational logic.
Representation
Combinational logic is used for building circuits where certain outputs are desired, given certain inputs. The construction of combinational logic is generally done using one of two methods: a sum of products, or a product of sums. A sum of products can be easily visualized by looking at a truth tableTruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
:
 |
 |
 |
Result | Logical equivalent Logical equivalence In logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other... |
|---|---|---|---|---|
| F | F | F | F |  |
| F | F | T | F |  |
| F | T | F | F |  |
| F | T | T | F |  |
| T | F | F | T |  |
| T | F | T | F |  |
| T | T | F | F |  |
| T | T | T | T |  |
Using sum of products, we take the sum of all logical statements which yield true results. Thus, our result would be:
It could then be simplified using Boolean algebra to:
Logic formulas minimization
Minimization (simplification) of combinational logic formulas is done using the following rules:
With the use of minimization, a simplified logical function or circuit may be arrived at, and the logic combinational circuit becomes smaller, and easier to analyse, use, or build.
External links
- Combinational Logic & Systems Tutorial Guide by D. Belton, R. Bigwood.