Module 1: Introduction to Logic Circuits

Mazen A. R. Saghir

Department of Electrical and Computer Engineering

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 1 / 86

What is a logic circuit?

011101
x1 001001
100110 y1
x2 Logic Operations 110010
101001 y2
x3

A logic circuit is an electronic circuit that transforms digital input

signals to digital output signals using logic operations.

A digital signal is an electrical signal (e.g. a voltage level) that takes

on discrete values that each can be represented by a numerical digit.
Because electronic circuits can naturally process and store binary
values (e.g. 0V and 3.3V), digital signals are typically represented
using binary digits (0’s and 1’s).

Logic operations manipulate Boolean values (true or false) according

to the rules of Boolean algebra. By using binary digits to represent
Boolean values (e.g. 0 = false; 1 = true), logic circuits can be used to
process digital signals.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 2 / 86
What is a logic circuit? (2)

Digital systems are collections of logic circuits used to perform

arithmetic or control functions. Examples of digital systems include
computers and consumer electronic products (e.g. television sets,
cordless telephones, watches, music/video players, fitness trackers,
etc...).

Because logic circuits process binary digits they are also called
binary circuits. In this course we will use these two terms
interchangeably.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 3 / 86

Binary variables and functions

The simplest logic circuit is a switch, which can be in one of two

possible states: open or closed.
– The state of the switch can be expressed using a binary variable, x.
– If x = 0, the switch is open.
– If x = 1, the switch is closed.

x = 0 x = 1
x = 0 x = 1
(a) Two states of a switch
A switch can be represented by a box S controlled by the binary
(a) Two states of a switch
variable x:
S
S
x

(b) Symbolxfor a switch

(b) Symbol for a switch

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 4 / 86

 1 1 1 1
Binary variables and functions (2)
x L( x )
0 1
A switch can be used in a simple circuit to connect0a battery to a light.
1

S x L( x )
0 0
Battery x Light
1 1

When the (a)switch is open, to

Simple connection the light turns off; when the switch is closed,
a battery
the light turns on. We can express the state of the light as a binary
function L, where L = 0 when x = 0, and L = 1 when x = 1.
S
Power
Thesupply
binary function can
x be expressed
Light as a logic expression:

L(x) = x
(b) Using a ground connection as the return path

Figure 2.2. A light controlled by a switch.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 5 / 86

Two-variable binary functions
A pair of switches controlled by binary variables x1 and x2 can be
connected in series or in parallel, and used to turn a light on or off.

When the switches are connected in series, the light will only turn on
if both switches are closed. In other words, L = 1 only if x1 = 1 and
x2 = 1; otherwise L = 0.
x1 x2 L ( x1 , x2 )
S S 0 0 0
Power x1 x2 Light 0 1 0
supply
1 0 0
1 1 1
(a) The logical AND function (series connection)
We can express the two-variable binary function x1 L(x
x2 1 ,Lx(2x)1 ,as
x2 )a logic
expression using a logical
S AND operator (“·”):0 0 0
x1 0 1 1
L(x1 , x2 ) = x1 · x2 1 0 1
Power
supply S Light 1 1 1
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 6 / 86
Two-variable binary functions (2)
S S x1 x2 L ( x1 , x2 )
Power 0 0 0
x1 x2 Light
When the switches are connected in parallel, the light will 0turn on if
supply 0 1
either one of the switches is closed. In other 1words, 0 L = 10if x1 = 1,
x2 = 1, or x1 = x2 = 1; L = 0 only if x1 = 0 and x12 = 0. 1
(a) The logical AND function (series connection) 1

S x1 x2 L ( x1 , x2 )
x1 0 0 0
0 1 1
Power
supply S Light 1 0 1
1 1 1
x2

We (b)canTheexpress
logical OR function
the (parallel connection)
two-variable x1 x2 L(x
binary function , x2a, xlogic
x3 1 , xL2()x1as 3)
expression OR operator (“+”): 0 0 0 0
Figure using
2.3. Two a logical
basic functions.
0 0 1 0
L(x1 , x2 ) = x1 +0 x2 1 0 0
0 1 1 1
1 0 0 0
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 1 0 1 1 7 / 86
 1 0 0
1 1 1
Multi-variable binary functions
x1 x2 L ( x1 , x2 )
0 0 0
The AND and OR operators are fundamental logic
0 1
functions
1
that can
be combined to generate complex logical expressions
1 0 involving
1
multiple binary variables. 1 1 1

x1 x2 x3 L ( x1 , x2 , x3 )
0 0 0 0
S 0 0 1 0
X1 0 1 0 0
S
0 1 1 1
Power
X3 Light 1 0 0 0
supply S
1 0 1 1
X2 1 1 0 0
1 1 1 1

For example, the above circuit implements a three-variable x1 L( x1 ) binary

Figure 2.4. A series-parallel connection.
0 1
logic function: 1 0
L(x1 , x2 , x3 ) = (x1 + x2 ) · x3
In this circuit, the light turns on (i.e. L(x1 , x2 , x3 ) = 1) if x3 = 1 and
(x1 = 1 or x2 = 1 or (x1 = x2 = 1)).
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 8 / 86
 0 0 1 0
Inversion 0 1 0 0
0 1 1 1
1 0 0
So far we have observed that a positive action can occur0 (e.g. a light
turning on) when a switch is closed. 1But we
0 can1 also wire
1 a circuit so
1 1 0
that a positive action occurs when a switch is open. 0
1 1 1 1
R

Power x L( x )
supply x S Light 0 1
1 0

x L( x )
In the above circuit, L = 1 when x = 0, and L0 = 0 0when x = 1. The
Figure 2.5.LAn
binary function can be expressed
inverting circuit. 1 expression:
as the logic 1

L(x) = x = x 0

The bar over the variable x, or the apostrophe next to it, denotes the
inverse (also called the complement, or logical NOT) operator.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 9 / 86
Inversion (2)

The complement operator can be applied to a single variable or to

more complex logic expressions.

For example, consider the logic function:

f(x1 , x2 ) = x1 + x2

then the complement of f(x1 , x2 ) is:

f(x1 , x2 ) = x1 + x2

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 10 / 86

Truth tables

At any given time, the outcome of a logic function depends on the

valuation of its binary variables. This can be captured using a truth
table that shows the outcome of the logic function for every
combination of its binary variables.

For example, the following truth table shows the outcomes of the
two-variable logical AND and OR functions.

x1 x2 x1 · x2 x1 + x2
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1

AND OR

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 11 / 86

Truth tables (2)
A truth table can express the outcome of an arbitrary logic function,
but its size depends on the possible valuations of the function’s
variables.
x1 x2 logic
The truth table for an n-variable x1 · x2 function
x1 + x2 has 2n rows:
0 0 0
– The truth table of the single-variable 0 NOT function has
logic
1 0 1 0 1
2 = 2 rows. 1 0 0 1
– The truth tables of the two-variable
1 1 1 logic1 AND and OR functions have
22 = 4 rows each.
AND OR
– The truth tables of the three-variable logic AND and OR functions have
3
2 = 8 rows each.
x1 x2 x3 x1 · x2 · x3 x1 + x2 + x3
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 12 / 86

Logic gates
We have seen how the AND, OR, and NOT logic functions can be
implemented using switches. Because these are fundamental logic
functions widely used in logic circuits, they are implemented as
microelectronic building blocks called logic gates.

Each logic gate is built from transistors that function as

microelectronic switches. The transistors are wired to provide
a specific logic function.

Logic gates have one or more binary logic inputs, but only one binary
logic output. The output value corresponds to the gate’s logic function.

x1
x2 Logic
f (x1, x2 ,…, xn )
…

Gate
xn

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 13 / 86

 Logic gates (2) x1
x2
x1
Each fundamentalx1logic
 x2 gate is denoted by a x1 unique
 x2   xgraphical
n
symbol
x
that 2is used when representing logic circuits graphically. The graphical
representation of a logic circuitxnis called a schematic
x diagram.
1
x2
x1 AND
(a) gates x1  x2 x1 x1  x2   xn
x2
x2
x1 xn
AND gates: x1  x2 x1  x2   xn
x2 x1
(a) AND gates
x2 xn
x1
x1 + x2 x1 + x2 + + xn
x2 (a) ANDxgates
1
x2
x1 xn
OR gates: x1 + x2 x1 + x2 + + xn
x2 x1
x
x(b) OR gates xn2
1 x1 + x2 x1 + x2 + + xn
x2
(b) OR gates
x xn
Inverter (NOT gate): x
x x
(b) OR gates
(c) NOT gate
gure 2.8.(EECE
M. Saghir The320basic
– Summergates.
2023) Introduction to Logic Circuits(c) NOT gate 14 / 86
Simple logic circuit

The following is a schematic diagram of a simple logic circuit that

implements the binary function: f(x1 , x2 , x3 ) = (x1 + x2 ) · x3
x
1
x
2
f = x + x   x
x 1 2 3
3

The circuit uses a two-input OR gate and a two-input AND gate. More
complex circuits will need more logic gates.
Figure 2.9. The function from Figure 2.4.
The larger the number of logic gates used in a circuit, the more costly
the circuit will be. While this seems obvious, we will later learn that it
is possible for different logic circuits to implement the same binary
logic function. It is therefore important that we design logic circuits
using the smallest number of logic gates.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 15 / 86

Analyzing logic circuits
Logic circuit analysis is the process of determining the behavior, or
function, of a given logic circuit.

One approach is to enumerate all possible combinations of binary

input variables, determine the corresponding circuit output, and
tabulate the results in a truth table.

Example:x1 0  0 1  1 1 1 0 0
A
1 1  0 1 f
x1 0  0 1  1 1 1 0 0
0 0 0  1 AB 1 1  0 1
0  1 0  1 f
x2
0 0 01 B
0  1 0  1
x2
(a) Network that implementsf = x1 + x1  x2
(a) Network that implementsf = x1 + x1  x2
x x f (x , x ) A B
1 x 2x f (1x , x2 )
1 2 1 2 A B
0 0 0 11 1 0
0 1 0
0 01 1 11 11 0 0
1 10 0 00 0 0 0 0
1 11 1 11 0 0 1 1
(b) Truth table
M. Saghir (EECE 320 – Summer 2023) (b) Truth table
Introduction to Logic Circuits 16 / 86
1
 1 1  0 1 f
Analyzing logic0 circuits
1 0  1
(2) 0 0 01 B
x2

(a) Network that implementsf = x1 + x1  x2

Another approach is to use x x
a timing
f (x , x )
diagram, which shows how the
1 2 1 2 A B
circuit’s input, intermediate, and output signals change over time.
0 0 1 1 0
0 1 1 1 0
Below is an idealized timing
1 diagram
0 0 of the0 same
logic circuit.
0
1
It assumes logic gates have 1 1
zero delay. Idealized
timing diagrams
0 1

are suitable for describing(b)the functional

Truth table behavior of a logic circuit.
x 1
1 0

x 1
2 0

1
A
0
1
B
0
1
f
0 Time
(c) Timing diagram

001 1 1100
M. Saghir (EECE 320 – xSummer 2023) Introduction to Logic Circuits 17 / 86
 1 0
0 0 1 x1 x2 x1 · x2 x1 + x2
0 1 1 1 0
Functionally equivalent logic circuits 1 0 0 0 00 0 0 0
1 1 1 0 01 1 0 1
1 0 0 1
The following logic circuits1implement
(b) Truth table
1 1 two1 different
binary functions,
1
f xand
1 0 g. Yet both functions have the same truth table, which indicates
AND OR
the
x 1two circuits are functionally equivalent.
2 0
1
A
0 x1 x2 x3 x1 · x2 · x3 x1 + x2 + x3
0  0 1  1 1 1 0 0
x 1
B1 0 0 A0 0 0
0 1  0  1 f 1 f(x , x ) = x + (x
0
0 0 1 1
· x2 )
1 1 2 1 1
f 0 0 0 0  1 1 B0 0 1
0 0  1 0  1 Time
x2 0 1 1 0 1
(c) Timing diagram
1 0 0 0 1
(a) Network that implementsf = x1 + x1  x2
001 1 11 1 0  00 1 0 1
x x x f (x , x )
1 1 2 11 2 1 A0 B 0 1
1 1  0 1 g(x1 , x2 ) = x1 + x2
010 1 0 0 11 1 11 0 1 g1
x
2 0 1 1 1 0
1 0 0 0 0
(d) 1Network
1 that
1 g
implements = x +x
1 1 2
x1 x2 x1 x1 · x2
0
f = x 1 + ( x1 · x2 ) g = x 1 + x2
0 Truth
Figure (b)
2.10. 0 table
An 1
example of0logic networks. 1 1
x 1 0 1 1 0 1 1
1 0
1 0 0 0 0 0
x 1 1 1 0 1 1 1
2 0

1
M. SaghirA (EECE 320 – Summer 2023) Introduction to Logic Circuits 18 / 86
Functionally equivalent logic circuits (2)

Clearly the logic circuit implementing function g is the least expensive

because it uses fewer logic gates.

In general, we would like to find the least expensive logic circuit that
implements an arbitrary binary logic function. We must therefore
learn techniques for minimizing the complexity of binary logic
expressions, and using the rules of Boolean algebra to manipulate
binary logic expressions.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 19 / 86

Axioms of Boolean algebra

An axiom is a statement (an assumption) taken to be true. Axioms

are often self evident and do not require proofs.

A1 x = 0 if x 6= 1
A1’ x = 1 if x 6= 0
A2 If x = 0, then x = 1
A2’ If x = 1, then x = 0
A3 0·0 = 0
A3’ 1+1 = 1
A4 1·1 = 1
A4’ 0+0 = 0
A5 0·1 = 1·0 = 0
A5’ 1+0 = 0+1 = 1

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 20 / 86

Single-variable theorems

A theorem is a rule expressed by symbols or formulae. Theorems are

not self-evident, but can be proved through reasoning.

The following are Boolean algebra theorems applied to a single

Boolean variable x ∈ {0, 1}, where 0 denotes false and 1
denotes true.
T1 x+0 = x Identities
T1’ x·1 = x
T2 x+1 = 1 Null elements
T2’ x·0 = 0
T3 x+x = x Idempotency
T3’ x·x = x
T4 x=x Involution
T5 x+x =1 Complements
T5’ x·x =0

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 21 / 86

Perfect induction proofs

The single-value theorems can be proven by perfect induction:

Substituting x = 0 and x = 1 in the expressions, and applying the
axioms of Boolean algebra.

Example: Prove Theorem T1, that x + 0 = x.

Proof: Substituting x = 0 results in 0 + 0 = 0, which is true based on

axiom A4’. Similarly, substituting x = 1 results in 1 + 0 = 1, which is
also true based on axiom A5’. Because we have shown that
x + 0 = x is true for both possible values of x, the theorem has been
proven by perfect induction.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 22 / 86

Principle of duality

The dual of a logic expression is another logic expression obtained

by swapping all OR operators (+) with AND operators (·) (and vice
versa), and all 0’s with 1’s (and vice versa). In Boolean algebra, if
a logic statement (e.g. axiom or theorem) is true, its dual will also be
true.
– The Boolean algebra axioms and single-value theorems are organized
in pairs of duals (e.g. A4 and A4’, T3 and T3’, etc...).
– Example: In the statement x + 0 = x (T1), if we replace the OR
operator by an AND operator, and the 0 by a 1, we obtain its dual logic
statement: x · 1 = x (T1’). Both statements are true.

The principle of duality helps us express the same logic function in at

least two different ways. This can help us choose a corresponding
logic circuit implementation that uses the least number of logic gates.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 23 / 86

Two-/three-variable algebraic properties and theorems

T6 x+y = y+x Commutativity

T6’ x·y = y·x
T7 ( x + y) + z = x + (y + z) Associativity
T7’ ( x · y) · z = x · (y · z)
T8 x · y + x · z = x · (y + z) Distributivity
T8’ ( x + y) · ( x + z) = x + (y · z)
T9 x+x·y = x Covering Theorem
T9’ x · ( x + y) = x
T10 x·y+x·y = x Combining Theorem
T10’ ( x + y) · ( x + y) = x
T11 x·y+y·z+x·z = x·y+x·z Consensus Theorem
T11’ ( x + y) · (y + z) · ( x + z) = ( x + y) · ( x + z)
T12 x = x+x+...+x Generalized Idempotency
T12’ x = x·x·...·x
T13 x·y = x+y DeMorgan’s Theorem
T13’ x+y = x·y
T14 F ( x1 , x2 , . . . , xn , +, ·) = F ( x1 , x2 , . . . , xn , ·, +) Generalized DeMorgan’s Theorem

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 24 / 86

Two-/three-variable algebraic properties and theorems (2)
The algebraic properties and theorems can be used to simplify logic
expressions involving two or three binary variables.

The validity of these properties and theorems can be proven by

algebraic manipulation, or by substituting variables with all
combinations of their values (perfect induction).

Example: The following truth table proves the validity of DeMorgan’s

Theorem (T13) by evaluating the left- and right-hand sides (LHS and
RHS) of the property for all combinations of variables x and y.
x y x·y x·y x y x+y
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
| {z } | {z }
LHS RHS

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 25 / 86

Example 1

Prove the following logic equation:

(x1 + x3 ) · (x1 + x3 ) = x1 · x3 + x1 · x3

We will prove the equation algebraically:

– Applying the distributive property (T8) to the left-hand side (LHS):
LHS = (x1 + x3 ) · x1 + (x1 + x3 ) · x3
– Applying T8 again to LHS:
LHS = x1 · x1 + x3 · x1 + x1 · x3 + x3 · x3
– Using the complements theorem (T5’) we know that x1 · x1 = 0 and
x3 · x3 = 0, which yields: LHS = 0 + x3 · x1 + x1 · x3 + 0
– Applying the identities theorem (T1):
LHS = x3 · x1 + x1 · x3
– Finally, using the commutative property (T6 and T6’):
LHS = x1 · x3 + x1 · x3 = RHS.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 26 / 86

Example 2

Prove the following logic equation:

x1 · x3 + x2 · x3 + x1 · x3 + x2 · x3 = x1 · x2 + x1 · x2 + x1 · x2

We will use algebraic manipulations to simplify the LHS and RHS

expressions, and we will compare the results:

LHS = x1 · x3 + x1 · x3 + x2 · x3 + x2 · x3 using T6
= x1 · (x3 + x3 ) + x2 · (x3 + x3 ) using T8
= x1 · 1 + x2 · 1 using T5
= x1 + x2 using T1’

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 27 / 86

Example 2 (continued)

RHS = x1 · x2 + x1 · (x2 + x2 ) using T8

= x1 · x2 + x1 · 1 using T5
= x1 · x2 + x1 using T1’
= x1 · x2 + x1 + x2 using T11
= x2 · (x1 + 1) + x1 using T8
= x2 + x1 using T2 and T1’
= x1 + x2 using T6
Because the LHS and RHS simplify to identical expressions, the
equation has been proven.

This example shows that a Boolean function can be expressed in

different ways. It also demonstrates how algebraic manipulations can
reduce the cost of a logic circuit.
f(x1 , x2 , x3 ) = x1 · x3 + x2 · x3 + x1 · x3 + x2 · x3 original LHS
= x1 · x2 + x1 · x2 + x1 · x2 original RHS
= x1 + x2 simplified
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 28 / 86
Notation and terminology

When operating on single digits, the Boolean + and · operators are

nearly identical to their arithmetic counterparts. The only difference is
that a logical 1 + 1 = 1 (A3’), whereas an arithmetic 1 + 1 = 2.

Because of these similarities the OR and AND operators are often

called the logic sum and logic product operators, or simply the sum
and product operators, respectively.

We therefore say the following Boolean expression is a sum of three

product terms:

(x1 · x2 · x3 ) + (x1 · x4 ) + (x2 · x3 · x4 )

Similarly, we say the following Boolean expression is a product of

two sum terms:
(x1 + x3 ) · (x2 + x3 + x4 )

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 29 / 86

Operator precedence

The AND, OR, and NOT operators form the basis of all logic
expressions. However, operations must be evaluated in the following
order: NOT, AND, and then OR.

Example: To evaluate x1 · x2 + x1 · x2 , we first find the complements

of x1 and x2 , evaluate the product terms x1 · x2 and x1 · x2 , and then
find the sum of the two product terms.

To simplify the appearance of logic expressions we can also omit the

product operator (·) when there is no ambiguity. The preceding
expression can therefore be expressed as: x1 x2 + x1 x2 .

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 30 / 86

Synthesizing logic circuits

Synthesis is the process of generating a physical logic circuit starting

from a functional description of the circuit. Typically, this involves
three steps:
1. Capture the functionality of the circuit in a truth table.
2. Derive a Boolean function from the truth table.
3. Implement the Boolean function using logic gates.

Example: Design a logic circuit with two binary inputs x1 and x2 such
that the circuit produces a logic 0 when x1 = 1 and x2 = 0, and a
logic 1 otherwise.
1. The following truth table captures the functionality of the circuit:

x1 x2 f ( x1 , x2 )
0 0 1
0 1 1
1 0 0
1 1 1

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 31 / 86

Synthesizing logic circuits (2)

2. We can derive a Boolean function from the truth table by generating

a logical product term for each combination of the input variables for
which f(x1 , x2 ) = 1, and then finding the logical sum of the product
terms.
The first row of the truth table shows that f(x1 , x2 ) = 1 when x1 = 0
AND x2 = 0. This function outcome is produced by the logical product
term x1 x2 . Similarly, the second and fourth rows of the truth table lead
to the terms x1 x2 and x1 x2 , respectively.
We can then express the function as a canonical sum-of-products
logic expression:

f(x1 , x2 ) = x1 x2 + x1 x2 + x1 x2

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 32 / 86

Synthesizing logic circuits (3)

3. We can now implement the corresponding logic circuit using an

appropropriate number of logic gates. A straightforward
implementation of f(x1 , x2 ) uses two inverters, three 2-input AND
gates, and a 3-input OR gate.
x1
x2

(a) Canonical sum-of-products

Note that both the derived function and its circuit implementation are
functionally correct, but are not guaranteed to be optimal.
x1
f
x2

M. Saghir (EECE 320 – Summer 2023) (b) Minimal-cost

Introduction realization
to Logic Circuits 33 / 86
Synthesizing logic circuits (4)

We can optimize the derived function using algebraic manipulations:

f(x1 , x2 ) = x1 · x2 + x1 · x2 + x1 · x2
x1
= x1 · (x2 + x2 ) + x1 · x2 using T8
x2
= x1 · 1 + x1 · x2 using T5
= x1 + x1 · x2 using T1’
= x1 · 1 + x1 · x2 + 1 · x2 using T11
f
= x1 + x2 · (x1 + 1) using T1’ and T8
= x1 + x2 · 1 using T2
= x1 + x2 using T1’

We can now implement (a) theCanonical

optimized function using a corresponding
sum-of-products
logic circuit, which uses only one inverter and a 2-input OR gate:

x1
f
x2

(b) Minimal-cost realization

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 34 / 86
Summary: Synthesizing logic circuits

We can derive a canonical sum-of-products expression of a logic

function from the corresponding truth table by deriving a product term
(AND gate) for each row of the table for which the function equals 1.

Each product term will include a combination of all the function’s input
variables. If a variable xi = 1 in a given row, then xi is used in the
product term. Alternatively, if xi = 0 in the row, xi is used. For
example, if a three-variable function is 1 when x1 = 1, x2 = 0, and
x3 = 1, the corresponding product term will be x1 x2 x3 . The function is
then expressed as the logical sum of the product terms.

Although the canonical sum-of-product expression is logically correct,

it is rarely optimal, and it can be simplified using Boolean algebraic
manipulations to produce a low-cost circuit implementation.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 35 / 86

Minterms
Given a logic function of n variables, a product term in a
sum-of-products expression is said to be a minterm if it includes all
n variables in complemented or uncomplemented form.

Each row of the function’s truth table will have an associated minterm
that includes xi if xi = 1, and xi if xi = 0.

Example: The following truth table for a three-variable logic function

shows the minterm mi associated with every row i.
Row
number x1 x2 x3 Minterm
0 0 0 0 m0 = x 1 x 2 x 3
1 0 0 1 m1 = x 1 x 2 x3
2 0 1 0 m2 = x 1 x2 x 3
3 0 1 1 m3 = x 1 x2 x3
4 1 0 0 m4 = x1 x 2 x 3
5 1 0 1 m5 = x1 x 2 x3
6 1 1 0 m6 = x1 x2 x 3
7 1 1 1 m7 = x1 x2 x3

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 36 / 86

Canonical sum-of-products (SOP) form
The canonical sum-of-products (SOP) representation of a logic
function can be expressed as the logical sum of the minterms for
which the function has a value of 1.

Consider the following truth table for a three-variable logic function:

Row
number x1 x2 x3 f ( x1 , x2 , x3 )
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0

The canonical SOP for this function can be expressed as:

f(x1 , x2 , x3 ) = Σ(m1 , m4 , m5 , m6 ) = Σm(1, 4, 5, 6)
= x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 37 / 86
Using duality to synthesize logic functions

The principle of duality suggests we can synthesize a function f by

considering the rows in the associated truth table for which f = 0.

Consider the following truth table for a three-variable logic function:

Row
number x1 x2 x3 f ( x1 , x2 , x3 )
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0

f(x1 , x2 , x3 ) = m 0 + m 2 + m 3 + m7
f(x1 , x2 , x3 ) = m 0 + m 2 + m 3 + m7
= m 0 · m2 · m 3 · m 7

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 38 / 86

Maxterms

The complements of minterms are called maxterms. Each maxterm

is a logical sum of a function’s variables in some combination of
complemented and uncomplemented form.

The following truth table for a three-variable function shows the

minterms mi and corresponding maxterms Mi = mi associated with
every row i:
Row
number x1 x2 x3 Minterm Maxterm
0 0 0 0 m0 = x 1 x 2 x 3 M0 = x1 + x2 + x3
1 0 0 1 m1 = x 1 x 2 x3 M1 = x1 + x2 + x 3
2 0 1 0 m2 = x 1 x2 x 3 M2 = x1 + x 2 + x3
3 0 1 1 m3 = x 1 x2 x3 M3 = x1 + x 2 + x 3
4 1 0 0 m4 = x1 x 2 x 3 M4 = x 1 + x2 + x3
5 1 0 1 m5 = x1 x 2 x3 M5 = x 1 + x2 + x 3
6 1 1 0 m6 = x1 x2 x 3 M6 = x 1 + x 2 + x3
7 1 1 1 m7 = x1 x2 x3 M7 = x1 + x2 + x3

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 39 / 86

Canonical product-of-sums (POS) form

The canonical product-of-sums (POS) representation of a logic

function can be expressed as the logical product of the maxterms for
which the function has a value of 0.

Row
number x1 x2 x3 f ( x1 , x2 , x3 )
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0

= m0 · m2 · m3 · m7 = M0 · M2 · M3 · M7
f(x1 , x2 , x3 )
= Π(M0 , M2 , M3 , M7 ) = ΠM(0, 2, 3, 7)
= (x1 + x2 + x3 ) · (x1 + x2 + x3 ) · (x1 + x2 + x3 ) · (x1 + x2 + x3 )

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 40 / 86

Which canonical form, SOP or POS?

The choice of canonical form depends on the logic function. If the

truth table has fewer 1 rows than 0 rows, the canonical SOP form may
be easier to process because it will have fewer terms. Conversely, if
the truth table has fewer 0 rows than 1 rows, the canonical POS may
be easier to process.

Keep in mind that neither canonical form will be optimal, and that it is
often possible to use Boolean algebraic transformations and
manipulations to simplify canonical SOP and POS expressions.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 41 / 86

Representing binary inputs as numbers

The n inputs of a digital circuit can be grouped into an n-tuple and

treated as a binary number.

Binary numbers are represented by a sequence of 0’s and 1’s that

conform to a positional number scheme where each bit is scaled by
a corresponding power of two.

If B = bn−1 bn−2 ...b1 b0 is an n-bit binary number, then its value,

V(B), can be found using the following formula:

X1
n−
V(B) = bi × 2i
i=0

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 42 / 86

Representing binary inputs as numbers (2)

For example, the 4-bit binary number 1011 has a value of:

1 × 23 + 0 × 22 + 1 × 21 + 1 × 20 = 8 + 0 + 2 + 1 = 11

We also say that (1011)2 = (11)10 , where 2 and 10 are the number’s
base, or radix. Binary numbers are radix-2 numbers, while decimal
numbers are radix-10 numbers.

For an n-variable logic function each minterm or maxterm is

associated with a corresponding truth table row number. We can
derive the corresponding product or sum terms by converting the row
number to its equivalent n-bit binary value.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 43 / 86

Converting from decimal to binary
Converting a positive decimal number D to an equivalent binary
number B involves repeatedly dividing D by 2 and saving the
remainders, which form the corresponding binary digits ordered from
least to most significant. This continues until the quotient equals zero.
Example: Convert D = 1110 to binary.
– 11/2 = 5 with remainder = 1 (LSB)
– 5/2 = 2 with remainder = 1
– 2/2 = 1 with remainder = 0
– 1/2 = 0 with remainder = 1 (MSB)
– It follows that 1110 = 10112

To represent D in binary, we need at least log2 (D) bits. For example,

representing 1110 in binary requires log2 (11) = 3.46 ≈ 4 bits.
We can also use more bits to represent D by padding zeros to the left
of the binary number (i.e. 1110 = 10112 = 010112 = 0010112 , etc...).
This only works for positive numbers. We will learn how to deal with
negative numbers in Module 7.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 44 / 86
N-bit binary numbers and their decimal equivalents

1-Bit 2-Bit 3-Bit 4-Bit

Binary Binary Binary Binary Decimal
Numbers Numbers Numbers Numbers Equivalent
( x1 ) ( x1 , x2 ) ( x1 , x2 , x3 ) ( x1 , x2 , x3 , x4 )
0 00 000 0000 0
1 01 001 0001 1
10 010 0010 2
11 011 0011 3
100 0100 4
101 0101 5
110 0110 6
111 0111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 45 / 86

Example 3

Find an optimal implementation of the function:

f(x1 , x2 , x3 ) = Σm(2, 3, 4, 6, 7)

We start by expressing the function in its canonical SOP form, and

simplify it using Boolean algebraic transformations.

f = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 canonical SOP
= x1 x2 (x3 + x3 ) + x1 x2 x3 + x1 x2 (x3 + x3 ) T8
= x1 x2 + x1 x2 x3 + x1 x2 T5 and T1’
= x2 (x1 + x1 ) + x1 x2 x3 T8
= x2 + x1 x2 x3 T5 and T1’
= x2 + x1 x2 x3 + x1 x3 T11
= x2 + x1 x3 (x2 + 1) T8
= x2 + x1 x3 T2 and T1’

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 46 / 86

Example 4

Find an optimal implementation of the function:

f(x1 , x2 , x3 ) = ΠM(0, 1, 5)

We start by expressing the function in its canonical POS form, and

simplify it using Boolean algebraic transformations.
f = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 ) canonical POS
= ((x1 + x2 ) + x3 x3 )(x1 + x2 + x3 ) T8’
= (x1 + x2 )(x1 + x2 + x3 ) T5’ and T1
= x2 + (x1 (x1 + x3 )) T8’
= x2 + (x1 x1 + x1 x3 )) T8
= x2 + x1 x3 T5’ and T1

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 47 / 86

NAND and NOR gates

We have seen that AND, OR, and NOT gates can be used to
implement virtually any logic circuit. But there are two other logic
gates that are also useful for implementing logic circuits: NAND
and NOR gates.

NAND gate = NOT(AND) gate = AND gate with a complemented

output. The NAND gate symbol is the same as the AND symbol, but
includes a bubble at the output of the gate to represent inversion
(NOT).
x1
x2
x1
x 1  x 2 x 1  x 2    x n
x2

xn

(a) NAND gates

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 48 / 86

 x1
NAND and NOR gates (2) x2
x1
x 1  x 2 x 1  x 2    x n
x2

n
x
NOR gate = NOT(OR) gate = OR gate with a complemented output.
The NOR gate symbol is the(a)same as the OR symbol, but includes a
NAND gates
bubble at the output of the gate to represent inversion (NOT).
x1
x2
x1
x1 + x2 x 1 + x 2 +  + x n
x2

xn

(b) NOR gates

NAND and NOR gates use fewer transistors than AND and OR gates,
and therefore costFigure
less. 2.20.
It follows that and
NAND a circuit
NOR implemented
gates. using
NAND and NOR gates will cost less than a functionally-equivalent
circuit implemented using AND and OR gates.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 49 / 86

NAND and NOR gates conversions

We have seen that any logic circuit can be expressed in SOP or POS
forms using AND-OR or OR-AND structures, respectively. How can
we transform such circuits to only use NAND or NOR gates?

Physical demonstrations of DeMorgan’s Theorem:

x1
x1 x1
x2 x2
x2

x1 x2 = x1 + x2

x1
x1 x1
x2 x2
x2

x1 + x2 = x1 x2

Figure 2.21. DeMorgan’s

M. Saghir (EECE 320 – Summer 2023) theorem
Introduction to Logic Circuits in terms of logic gates. 50 / 86
Using NAND gates to implement a SOP circuit

Any AND-OR circuit can be implemented as a NAND-NAND circuit

having the same topology.

x1 x1
x2 x2
x3 x3
x4 x4
x5 x5

x1
x2
x3
x4
x5

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 51 / 86

Using NOR gates to implement a POS circuit

Any OR-AND circuit can be implemented as a NOR-NOR circuit

having the same topology.

x1 x1
x2 x2

x3 x3
x4 x4
x5 x5

x1
x2

x3
x4
x5

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 52 / 86

Example 5

Implement the function f(x1 , x2 , x3 ) = Σm(2, 3, 4, 6, 7) using NOR

gates only.

Reformulating f(x1 , x2 , x3 ) = ΠM(0, 1, 5) we can derive the canonical

POS implementation and use Boolean algebraic transformations to
obtain a simplified POS implementation f = (x1 + x2 )(x2 + x3 ).

x1

x2 f

x3

POS implementation

x1
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 53 / 86
Example 5 (continued)
x 3

POS implementation
The OR-AND circuit can be easily transformed to a NOR-NOR circuit.

x1

x2 f

x3

NOR implementation

Notice
Figurehow
2.24theNOR-gate
NOT gate realization
used to invert x3 in
of the the POS
function in circuit
Example was2.4.
also
converted to a NOR gate: x3 = (x3 + x3 ) (T3).

More generally, NOR and NAND gates whose inputs are tied together
(to a single signal) become inverters: xi + xi + · · · + xi =
xi xi . . . xi = xi due to idempotency (T3 and T3’).

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 54 / 86

Example 6 x2 f

x3

Implement f(x1 , x2 , x3 ) = Σm(2, 3, 4, 6, 7) using NAND gates only.

(b) NOR implementation
Starting from the canonical SOP implementation and using Boolean
Figure 2.24 NOR-gate realization of the function in Example 2.4.
algebraic transformations we obtain a simplified SOP implementation
f = x2 + x1 x3 .

x2

f
x1

x3

(a) SOP implementation

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 55 / 86

 Figure 2.24 NOR-gate realization of the function in Example 2.4.
Example 6 (continued)

x2
An AND-OR circuit can be easily transformed to a NAND-NAND
f
x 1 we handle x2 , which is connected to the OR gate
circuit. But, how do
directly?
x3
We simply invert it twice: x2 = x2 (T4). We use a NAND gate to invert
x2 once, and we use the bubble needed to invert x2 a second time, at
(a) SOP implementation
the input of the OR gate, to transform the OR gate to a NAND gate.

x2

f
x1

x3

(b) NAND implementation

NAND-gate
Figure 2.25Introduction
M. Saghir (EECE 320 – Summer 2023)
realization of the function in Example 2.3.56 / 86
to Logic Circuits
Multilevel logic circuits

So far we have seen how to convert simple circuits expressed in SOP

or POS forms to NAND-NAND or NOR-NOR equivalents. However,
we may need to convert more complex circuits that consist of multiple
logic stages. These circuits are called multilevel circuits.

We use the same bubble-pushing approach to convert multilevel

circuits. We can start from either input or output end and move toward
the other end.

If we are converting to a NAND circuit we add a bubble to the output

of each AND gate, or we add bubbles to the inputs of each OR gate.
If these conversions result in a bubble at one end of a wire, another
bubble must also be added to the other end. We can now replace all
gates with NAND gates, which can also be used to invert input or
output signals as needed.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 57 / 86

 January 9, 2008 11:37 vra_29532_ch04 Sheet number 35 Page number 201 black
Multilevel logic circuits (2)
4.7 Analysis of Multilevel Circuits
The following example shows how a multilevel circuit can be entirely
4.7 Analysis of Multilevel Circuits
x1
implemented using NAND gates:
x 12
x3
x2
x 34 f

x 45 f
x6
x5
x7
x6
(a) Circuit with
x AND and OR gates
7

(a) Circuit with AND and OR gates

x1

x 12
x3
x2
x 34 f

x 45 f
x6
x5
x7
x6
(b) Inversions xneeded to convert to NANDs
M. Saghir (EECE 320 – Summer 2023) Introduction7 to Logic Circuits 58 / 86
 x4 f
Multilevel logic circuits (3)
x5
x6
x7

The following is the (b) Inversions needed to convert to NANDs

complete NAND-gate implementation:

x1

x2
x3

x4 f

x5

x6
x7

(c) NAND-gate circuit

Figure 4.27 Conversion to a NAND-gate circuit.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 59 / 86

 Multilevel logic circuits (4)

If we are converting
vra_29532_ch04
to a NOR circuit we add
Sheet number 36 Page number 202
a bubble to the output of
black
each OR gate, or we add bubbles to the inputs of each AND gate. If
these conversions result in a bubble at one end of a wire, another
bubble must also be added to the other end. We can now replace all
gates with NOR
•
gates, which can also be used to invert input or
CHAPTER 4 Optimized Implementation of Logic Functions
output signals as needed.
x1

x2
x3

x4 f

x5
x6
x7

(a) Inversions needed to convert to NORs

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 60 / 86
 x5
Multilevel logic
x6 circuits (5)
x7

The following is the(a)complete

Inversions needed to convert to NORs
NOR-gate implementation:

x1
x2

x3

x4

x5
x6
x7

(b) NOR-gate circuit

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 61 / 86

3.61a. The truth table for this function is similar to the OR function except that f = 0
XOR gate
both inputs are 1. Because of this similarity, the function is called Exclusive-OR, wh
commonly abbreviated as XOR. The graphical symbol for a gate that implements X
given in part (b) of the figure.

The exclusive-OR (XOR) gate is another useful logic gate widely

used in digital arithmetic circuits. The following are its truth table and
logic gatex 1symbol:
x2 f = x ⊕ x
1 2

x1 0x2 0 f = x1 ⊕0x2
0 00 1 0 1 x1
0 11 0 1 1 f = x ⊕ x2
x2 1
1 10 1 1 0
1 1 0
(a) Truth table (b) Graphical symbol

We can use the truth table to derive the canonical SOP representation
of the 2-input
x
XOR logic function: f(x1 , x2 ) = x1 x2 + x1 x2 .
1
x
2

f = x
1 ⊕ x2
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 62 / 86
008 11:37 vra_29532_ch04 Sheet number 32 Page number 198 black
XOR gate (2)
The 2-input XOR function can be implemented using standard logic
198 •
gatesC HorA PNAND
TER 4
gates only: Implementation of Logic Functions
Optimized

x1

x1 ⊕ x2

x2

(a) Sum-of-products implementation

N
a
x1

N ⊕ N

x1 ⊕ x2
b
N

x2
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 63 / 86
XOR gate (3)

The NAND gate implementation can be further optimized:

a = x1 · x 2 b = x2 · x 1
= x 1 + x2 = x 2 + x1 T13 (DeMorgan’s Theorem)
= x 1 + x2 · 1 = x 2 + x1 · 1 T1’ (Identities)
= x 1 + x2 · ( x1 + 1) = x 2 + x1 · ( x2 + 1) T2 (Null elements)
= x 1 + x1 x2 + x2 = x 2 + x1 x2 + x1 T8 (Distributivity)
= x 1 + x1 x2 = x 2 + x1 x2 T11 (Consensus Theorem)
= x1 · ( x1 · x2 ) = x2 · ( x1 · x2 ) T13 (DeMorgan’s Theorem)

g = x1 · x2

a = x1 · g b = x2 · g

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 64 / 86

XOR gate (4)

The optimized XOR circuit uses four NAND gates only:

N
a

g N ⊕ N

N
b

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 65 / 86

XNOR gate
The inverse of the XOR function is called exclusive-NOR (XNOR).
The following are its truth table and logic gate symbol:
x1 x2 f = x1 x2 Logic-gate-xnor-us.png (PNG Image, 640 × 282 pixels) https://upload.wikimedia.org/wikipedia/commons/9/9b/Logic-gate-xnor-...

0 0 1
0 1 0
1 0 0
1 1 1

We can use the truth table to derive the canonical SOP

representation of the 2-input XNOR logic function:

f(x1 , x2 ) = x1 x2 = x1 x2 + x1 x2
1 of 1 7/9/17, 12:35 AM

Sometimes the XNOR function is expressed simply as: f = x1 ⊕ x2 ,

and we can use DeMorgan’s Theorem to derive the XNOR canonical
SOP expression from its XOR dual.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 66 / 86
XNOR gate (2)

Like the XOR function, the XNOR funtion can be implemented using
standard gates or NAND gates. It also can be implemented using
NOR gates (starting from a POS expression), and it can be optimized
to use only four NOR gates:
2000px-XNOR_using_NOR.svg.png (PNG Image, 2000 × 594 pixels) - ... https://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/XNOR_us...

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 67 / 86

 Multiplexer circuits

A multiplexer is a useful logic circuit widely used in digital systems. It

nics.org Digital Electronics Module 4
behaves like a data selector switch. Depending on the position of the
ctors and Multiplexers
switch only one data source can be connected to the output.

n Module 4.2
ction, you should be able to:
a Select and Multiplexer

on of Data Select and Fig. 4.2.1 Mechanical

2-to-1 switch 8-to-1 switch
Selector switches
A multiplexer
ct (Multiplexer) Circuits. circuit has n data inputs, 1 output, and log2 (n) selector
A simple way to connect multiple sources of
n is a power-of-two.
inputs. Typicallyinformation The binary
in analogue electronic systems value
is by of the selector
(sel) determines which
using data input
mechanical gets connected
switches, such as to the output. The
those
on of Multi-Bit illustrated
Multiplexers. output
multiplexer in Fig.
will have the4.2.1.
same In value
exampleas(a)the
a single
data input it is
pole double throw switch is used to select either
connected to: input A or input B to be connected to output X.
ulation.
shows a=rotary
Example (b)output (sel) switch that
inputselector
Datasheets. can multiplex any one of eight inputs to a single
output.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 68 / 86
2-to-1 multiplexer circuit
A 2-to-1 multiplexer circuit has two inputs, x1 and x2 , one output, f,
and log2 (2) = 1 selector input, s.

We can describe the behavior of the multiplexer using a truth table:

s x1 x2 f (s, x1 , x2 )
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

We can then derive the corresponding canonical SOP expression:

f(s, x1 , x2 ) = sx1 x2 + sx1 x2 + sx1 x2 + sx1 x2

M. Saghir (EECE 320 – Summer 2023)
s f (s, x , x )
1 2
Introduction to Logic Circuits 69 / 86
 s x1 x2 f (s , x1 , x2 )
2-to-1 multiplexer circuit (continued)
0 0 0 0

0 0 1 0
We can now apply Boolean agebraic transformations
0 1 0 1 to simplify the
expression: 0 1 1 1
f(s, x1 , x2 ) = sx1 x2 + sx1 x2 + sx1 x1 20 +0 sx1 x2 0 canonical SOP
= sx1 (x2 + x2 ) + sx2 (x11 0+1 x1 ) 1 T8
= sx1 + sx2 T5 and T1’
1 1 0 0

1 1 1 1
Finally we can implement the corresponding logic circuit using basic
logic gates: (a) Truth table

x1 s

f x1 0
f
s x2 1
x2

(b) Circuit (c) Graphical symbo

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 70 / 86
 010 1
Multiplexer
0 1 1 symbol
1 and wide multiplexers
100 0
101 1
110 0
The multiplexer
111 1 (mux for short) is such a widely used circuit, it has its
own graphic symbol.
(a)Truth table
s0
s s1 s1 s0 f
w0 00 0 0 w0
x1 w1 01 w1
f 0 f 0 1
f w2 10 w2
1 0
x2 1 w3 11
1 1 w3

(b) Circuit 2-to-1 mux

(c) Graphical 4-to-1 symbol
symbol (a) Graphic mux (b) Truth table

A 4-to-1s multiplexer
f (s, x1, x2) has four datas0inputs, one output, and log2 (4) = 2
selector0 inputs.
x1 An 8-to-1 multiplexer has eight data
w0 inputs, one
s1
output,1and xlog 2 2 (8) = 3 selector inputs. And so on...
w1
(d) More compact truth-table representation

gure
M. 2.28. Implementation
Saghir (EECE 320 – Summer 2023)of a multiplexer.
Introduction to Logic Circuits 71 / 86
Computer-aided design (CAD) tools and systems

Designing and optimizing logic circuits manually is only practical for

simple circuits. Complex digital circuits (e.g. microprocessors,
arithmetic circuits, control circuits, etc...) are best designed with the
help of computer-aided design (CAD) tools that use powerful
algorithms to synthesize, optimize, and implement a design.

Designing a complex digital circuit involves a sequence of steps that

are each supported by a specialized CAD tool.
– Each tool is a software program that solves a specific problem at a
specific stage of the design process.
– CAD tools could be provided separately by different vendors, or they
could be integrated into a CAD system developed by a single vendor.
– CAD tools could be open-source and publically available, or proprietary
and commercially available. CAD tools may even be developed by
some companies for their own, in-house use.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 72 / 86

CAD system design stages

Design Entry. The first step is to specify (or describe) a design for
the CAD system. Two main approaches: Schematic capture or
hardware description language (HDL).

Schematic Capture. A graphical editor and a library of logic gate

symbols are used to describe a circuit’s hardware structure. Gates
can also be connected graphically inside the editor. Schematic
capture is practical only for small or simple designs.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 73 / 86

CAD system design stages (2)

Hardware Description Languages. Large or complex designs can

be described using a text-based hardware description language
(HDL) the same way a programming language is used to describe
a computer program. The two main HDLs in use today are Verilog
and VHDL. Both are IEEE standards, and both are supported by most
CAD tool vendors. This makes designs described in a HDL highly
portable across CAD tools and systems.

Logic Synthesis. Once a design has been entered, the next step is
to generate (or synthesize) the logic circuits that implement the
design. Schematic diagrams or HDL code are first compiled into
a tool-specific format called a netlist that is easy to manipulate
algorithmically. The tool then applies a number of optimizations to
reduce design complexity and ensure an efficient (e.g. minimum-cost)
circuit implementation.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 74 / 86

CAD system design stages (3)

Functional Simulation. Once a design has been synthesized, it

must be tested for correct functionality. This is done using a logic
simulator that shows how a synthesized circuit’s outputs change
when its inputs change. A test program called a test bench is used to
generate input stimuli patterns, and the simulator is used to compute
the corresponding circuit outputs. Test inputs and circuit outputs are
often displayed as waveforms that designers can inspect visually.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 75 / 86

CAD system design stages (4)

Physical Design. Once a design has been synthesized and

validated, it can be implemented in a suitable hardware technology
(e.g. standard logic chips, programmable logic devices, etc...). Each
technology provides its own set of hardware primitives and primitive
connectivity schemes.

Physical design includes technology mapping, which maps and

partitions synthesized logic circuits across hardware primitives. It also
includes placement and routing, which binds design components to
specific hardware primitives, and ensures the primitives are properly
interconnected to provide the required functionality.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 76 / 86

CAD system design stages (5)

Timing Simulation. Logic gates are physical devices with inherent

propagation delays. Signals traveling along interconnection wires also
experience delays. Timing simulations use delay models of hardware
primitives and interconnection networks to estimate the delays within
a circuit after it has been placed and routed. Timing simulations verify
that delays within a circuit are below some target latency bound,
ensuring the circuit will meet its performance target.

Chip Configuration. If the target hardware technology is a

programmable logic device, the last design step is to configure, or
program, the device. This involves loading the device configuration
memory with an appropriate bit stream that specifies the functionality
and connectivity of its on-chip hardware primitives.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 77 / 86

CAD system design flow 2.10 Introduction to Verilog 69

Design conception

DESIGN ENTRY

Schematic capture Verilog

Synthesis

Functional simulation

No
Design correct?

Yes

Physical design

Timing simulation

No
Timing requirements met?

Yes

Chip configuration

Figure 2.35 A typical CAD system.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 78 / 86
Introduction to Verilog

Verilog = VERIfication of LOGic.

Verilog was developed in the 1980’s by Gateway Design Automation,

which was later acquired by Cadence Design Systems. The language
was developed for logic verification and its syntax is influence by the
C programming language.

Verilog was made public (i.e. open-sourced) in 1990, and it was

standardized by the IEEE in 1995 as standard 1364-1995. An
enhanced version of Verilog was standardized in 2001 as IEEE
1364-2001. The language was initially used for digital system
simulation and validation.

Today Verilog is a common design entry method for logic synthesis

tools. It is widely supported by CAD system vendors, particularly
those targeting programmable logic devices.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 79 / 86

A simple Verilog code example

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 80 / 86

Verilog code organization
Modeling a digital circuit in Verilog involves describing its interface
and structure or functional behavior.

A Verilog model is implemented as a module whose interface is

specified by a list of ports. The model’s structure or functional
behavior are defined in the module body.
module module_name [( port { , port })];
// module declarations
// module statements
endmodule

In the code example, the module is called mux2to1 and it takes three
inputs parameters: x1, x2, and s, and one output parameter: f.
– The Verilog keywords input and output specify the direction of each
port. The keyword wire also specifies the type of each port, namely a
circuit element that caries digital signal values.
– Variables and signals of type wire can be assigned the values 0 or 1,
and can be processed as Booleans.
M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 81 / 86
Verilog structural model

A Verilog structural model describes the physical organization of the

modeled system.
– It could use multiple instances of builtin structural primitives such as
and, or, and not modules.
– It could also use multiple instances of other, user-defined modules to
implement a hierarchical design.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 82 / 86

Verilog behavioral model

Here is a behavioral model of the same circuit:

In the code example, a continuous assignment statement was

used with the builtin Boolean logic operators ~, &, and | to model the
mux circuit. Verilog also supports other Boolean operators like xor (^).
In the code example, the logic operators are applied to the input port
nets directly, and the result of the logic expression is assigned to the
output port.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 83 / 86

Verilog conventions

Identifiers
– An identifier is a name assigned to a Verilog object (e.g. module, port,
wire, etc...)
– Verilog is case sensitive; identifiers decoder1, Decoder1, and
DECODER1 refer different objects.
– Identifiers must begin with a letter, and may only consist of letters,
digits, or the underscore symbol ( ).
– Identifiers may not include any white space.

Files
– It is common to assign a Verilog file the same name as its
corresponding module and store it with a *.v suffix. For example, the
Verilog code for the multiplexer can be saved in a file called mux2to1.v.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 84 / 86

Another Verilog code example

Let us develop a behavioral Verilog model for the following circuit:

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 85 / 86

Another Verilog code example (2)

Unlike other programming languages, Verilog statements within a

module are concurrent, just like actual hardware. The continuous
assignment statements can be assumed to execute in parallel, and
the order they appear in the code is not important.

Each continuous assignment statement is evaluated (by the simulator)

each time a signal on the right hand side of the assignment changes.

M. Saghir (EECE 320 – Summer 2023) Introduction to Logic Circuits 86 / 86