ENGI 3861 Digital Logic

II. COMBINATIONAL LOGIC DESIGN

Combinational Logic output of digital system is only dependent
on current inputs (i.e., no memory)

(a) Boolean Algebra

- developed by George Boole in 1850s

- algebra defined on a set of 2 elements, {0, 1}, with binary
operators multiply (AND), add (OR), and invert (NOT):

XY X AND Y

X+Y X OR Y
__
X' or X NOT (X)

- Boolean algebra theorems:

One Variable Theorems
Label

+
Identities
X1 =X
X+0 =X
Null elements
X0 =0
X+1 =1
Idempotency
XX =X
X+X =X
Complements
XX' =0 X+X' =1
Involution
(X')' =X
Two/Three Variable Theorems
Commutativity
XY =YX
X+Y =Y+X
Associativity
(XY)Z =X(YZ)
(X+Y)+Z =X+(Y+Z)
Distributivity
(X+Y)(X+Z) =X+YZ XY+XZ =X(Y+Z)
DeMorgans
(XY)' =X'+Y' (X+Y)' =X'Y'

Combinational Logic Design - 1
ENGI 3861 Digital Logic
- duality:
to get + column from column (and vice versa),
swap + with operators and swap 0s and 1s

e.g., Prove that X +XY =X.







e.g., Prove distributivity for using other theorems.








- two/three variable theorems can be generalized to n variables

for example, DeMorgans theorem

(A+B+C+D+)' =A'B'C'D'

(ABCD)' =A'+B'+C'+D'

Note: will often leave out operator for convenience.

- literal primed or unprimed variable

Combinational Logic Design - 2
ENGI 3861 Digital Logic
- more on DeMorgans:


AND +NOT NAND






by DeMorgans


NOTs +OR


NAND




- similarly, for NOR can show:






e.g., Given F =X'YZ' +X'Y'Z, find F' using DeMorgans.

F' =


Combinational Logic Design - 3
ENGI 3861 Digital Logic
- generalized DeMorgan to get F', given F:

take dual of function F and complement literals

e.g., Given F =X'YZ' +X'Y'Z, dual is

F
dual
= (X'+Y+Z')( X'+Y'+Z)

F' =(X+Y'+Z)( X+Y+Z') as expected.


Canonical Sum-of-Products and Product-of-Sums Forms


XYZ Minterm Maxterm
000 m
0
= M
0
=
001 m
1
= M
1
=
010 m
2
= M
2
=
011 m
3
= M
3
=
100 m
4
= M
4
=
101 m
5
= M
5
=
110 m
6
= M
6
=
111 m
7
= M
7
=


e.g.,
XYZ F
000 0
001 1
010 0
011 0
100 1
101 0
110 0
111 1








Combinational Logic Design - 4
ENGI 3861 Digital Logic













- canonical sum of products (SOP) form of Boolean function F
sum of minterms corresponding to F =1
(also called "standard sum of products")

- canonical product of sums (POS) form of Boolean function F
product of maxterms corresponding to F =0
(also called "standard product of sums")

- sometimes minterm list or maxterm list notation is used:

F =m
1
+m
4
+m
7

=E
XYZ
(1, 4, 7)

and F =M
0
M
2
M
3
M
5
M
6

=H
XYZ
(0, 2, 3, 5, 6)

- SOP and POS forms can usually be simplified to minimize
literals no longer canonical

e.g., simplified SOP: F
1
=Y' +XY +X'YZ'
simplified POS: F
2
=X(Y'+Z)(X'+Y+Z')
Combinational Logic Design - 5
ENGI 3861 Digital Logic
(b) Realization of Circuits

Design Objectives

(1) minimum number of gates
(2) minimum number of inputs to a gate
(3) minimum propagation time through circuit
(4) minimum number of interconnections


Boolean Function Input

e.g., F =Y' +XY +X'YZ'












- SOP form leads to 2 levels of logic:
AND-OR logic AND gates followed by OR gates
(ignoring NOTs and assuming that any number of
inputs to a gate is allowed)
- similarly, POS form leads to 2 levels of logic:
OR-AND logic OR gates followed by AND gates
(ignoring NOTs and assuming that any number of
inputs to a gate is allowed)
Combinational Logic Design - 6
ENGI 3861 Digital Logic
Truth Table to Gates

e.g., (same as previous example)

XYZ F
000 1
001 1
010 1
011 0
100 1
101 1
110 1
111 1










SOP: F =




















Combinational Logic Design - 7
ENGI 3861 Digital Logic

Note: using canonical SOP directly to gates often takes many gates
and gates are large (in this example, 7 input OR gate!)

large gates can be built using smaller gates

e.g.,










6 2-input ORs 1 7-input OR, but 3 layers of logic gates
longer propagation delay circuit slower

- in order to minimize circuit, desirable to simplify canonical SOP

- from canonical SOP, using Boolean algebra:

F =



=

=

=

= (reduced SOP form)
Combinational Logic Design - 8
ENGI 3861 Digital Logic
a lot of work and difficult to know exactly what steps to
take

not guaranteed to find mimimal circuit

for this example, F =X +Y' +Z'
(easily derived using canonical POS form)

some standard reduction/minimization/simplification
methods exist such as Karnaugh maps for small
functions and software packages such as Espresso for
larger functions

- any logic function can be implemented using AND, OR, and
NOT gates (by starting with SOP or POS forms), but CMOS
technology lends itself to efficient implementation of
NANDs and NORs

any logic function can be implemented with exclusively
NAND (or NOR) gates

OR 2 NOTs +NAND NOR +NOT




AND NAND +NOT 2 NOTs +NOR




NOT NAND NOR
Combinational Logic Design - 9
ENGI 3861 Digital Logic
e.g.,
















- similarly all NOR circuit can be derived (most easily for OR-
AND circuit)
______________________

Example: Implementing a circuit using NANDs/NORs/NOTs














Combinational Logic Design - 10
ENGI 3861 Digital Logic





better




final circuit:












(c) Logic Minimization

- as we have seen, can use Boolean algebra theorems to reduce
number and size of gates in a circuit
logic minimization or logic simplification

- also, there are sophisticated computer tools for minimization,
such as the Espresso algorithm, which can find minimal or
near-minimal circuit for most expressions with dozens of
inputs and hundreds of product terms

- generally assume that X' is readily available and to use X' at gate
input has no more cost that using X
Combinational Logic Design - 11
ENGI 3861 Digital Logic
Karnaugh Maps

- good systematic visual method for minimizing 3 and 4 input
Boolean functions

3 input map

YZ
F:







e.g.,

(1) K-map of F:








1
0
10 11 01 00
X
Note: adjacent
columns differ
in only 1 bit
m
0
m
1
m
3
m
2

adjacent
squares differ
in only 1 bit
m
4
m
5
m
7
m
6

YZ
01 11 10
0
1
00
0 0 1
1 1 0
1
0
X
Combinational Logic Design - 12
ENGI 3861 Digital Logic
(2) K-map of F:

YZ














(3) K-map of F:











1
0
10 11 01 00
X
0 0 1 0
1 0 1 1
YZ
01 11 10
0
1
00
0 1 1
1 1 1
0
0
X
Combinational Logic Design - 13
ENGI 3861 Digital Logic
- for 3 input K-map:
1 square term with 3 literals
2 squares term with 2 literals
4 squares term with 1 literal


4 input map

F:
00
01
10
11
m
10
m
11

m
14
m
15
m
13
m
12

10 11 01
YZ
00 WX
m
9
m
8

m
6
m
7
m
5

m
2
m
3
m
1

m
4

m
0










again adjacent squares only differ in 1 bit

e.g.,

(1) K-map of F:




F =




01
00
10
11
10 11 01
YZ
00 WX
0
1
0 1
0 1
1
1
1 0 1
1 0 1
1
1
Combinational Logic Design - 14
ENGI 3861 Digital Logic
(2) K-map of F:

10
11
01
00
10 11 01
YZ
00 WX
1 0 1
0 0 0
1
0
1 0 0
1 0 1
0
1











F =


(3) K-map of F:

00
01
11
10
10 11 01
YZ
00 WX
0
1
1 0
1 1
0
1
1 1 0
0 1 0
1
0










F =





Combinational Logic Design - 15
ENGI 3861 Digital Logic
K-maps for POS

e.g.,

YZ
01 11 10

F =
0

1
00
1 0 0
1 0 1
1
1
X



F =

















(Note also, F =

using K-map for SOP)


Combinational Logic Design - 16
ENGI 3861 Digital Logic
Dont Cares

- in some cases, outputs for given inputs can be either 0 or 1,
whichever is convenient for design dont care

indicated by X in values of truth table and K-map

- dont cares can be exploited to help minimize circuit

e.g.,

XYZ F
000 1
001 X
010 1
011 1
100 0
101 0
110 X
111 1












YZ
01 11 10

0

1
00
X
1 1
0
X 1
1 0
X




F =

(Compare to X'Z' +YZ if dont cares assumed to be 0.)
Combinational Logic Design - 17
ENGI 3861 Digital Logic
Multiple Output Minimization

- in many cases, there are multiple circuit outputs and considering
them together can result in fewer gates

e.g., F =XY +XZ +Y'Z
G =X'Y +XYZ
H =X'YZ +XZ

implemented independently:

5 2-input ANDs
2 3-input ANDs
2 2-input ORs
1 3-input OR

implemented together:













6 2-input ANDs (+1)
0 3-input ANDs (2)
2 2-input ORs
1 3-input OR
Combinational Logic Design - 18
ENGI 3861 Digital Logic
(d) Combinational Logic Design Examples

Summary of Combinational Logic Design

(1) Inputs
wording, truth table, Boolean function, K-map
(2) Objectives
minimize #and size of gates, minimize timing delay
(3) Constraints
NANDs only, maximum timing delays, gate driving
capabilities, limitations on gate size
(4) Tools
Boolean algebra, SOP/POS forms, Karnaugh maps (for
small circuits with s 6 inputs) , Espresso (for large
circuits)

Example 1: Temperature Controller

- temperature sensor produces following inputs to controller:

Temperature 4-bit Input Code Action
<15
0000
15
0001
16
0010
heat on, fan on high
17
0011
18
0100
19
0101
heat on, fan on low
20
0110 heat off, AC off
21
0111
22
1000
23
1001
24
1010
25
1011
>25
1100
AC on

Combinational Logic Design - 19
ENGI 3861 Digital Logic
- controller should control furnace/AC unit with 3 outputs with the
objective of keeping the temperature at 20:

H (heat+fan on/off) 1 on, 0 off
F (fan low/high) 0 low, 1 high
C (AC on/off) 1 on, 0 off


Design a NAND-only circuit to implement the controller logic.








WXYZ H F C
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

















Combinational Logic Design - 20
ENGI 3861 Digital Logic

H:
00
01
11
10
10 11 01
YZ
00 WX




















H =


F:
10
11
01
00
10 11 01
YZ
00 WX

















F =

Combinational Logic Design - 21
ENGI 3861 Digital Logic

C:
10
11
01
00
10 11 01
YZ
00 WX















C =

Resulting circuit using NANDs only:






Combinational Logic Design - 22
ENGI 3861 Digital Logic
Example 2: 2-out-of-5 Encoding

- 2-out-of-5 encoder encodes digits as follows:





(Aside: What is value of 2-out-
of-5 encoding?)

Design a logic circuit to convert a
binary representation of a digit to
a 2-out-of-5 code.


Digit Code
0 11000
1 00011
2 00101
3 00110
4 01001
5 01010
6 01100
7 10001
8 10010
9 10100

WXYZ A B C D E
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Truth table:
















Combinational Logic Design - 23
ENGI 3861 Digital Logic
A:









A =

B:









B =
10
11
01
00
10
11
01
00
10
11
01
00
10 11 01
YZ
00 WX
10 11 01
YZ
00 WX
10 11 01
YZ
00 WX













C:









C =
Combinational Logic Design - 24
ENGI 3861 Digital Logic
D:









D =
10
11
01
00
10
11
01
00
10 11 01
YZ
00 WX
10 11 01
YZ
00 WX









E:









E =


Draw circuit. Be sure to share gates where possible across multiple
outputs.


Combinational Logic Design - 25
ENGI 3861 Digital Logic
Combinational Logic Design - 26
Example 3: Weathervane

Design a logic circuit which takes four binary inputs indicating
north, east, south, and west wind components (i.e., N =1 indicates
a component of wind blowing north) and produces an output of 1
when the wind direction is northeast or southwest.

Note: N =S =1 and E =W =1 are not possible.














F =


Not surprising!

NESW F
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
10
11
01
00
10 11 01
SW
00




NE


Compare to result based on SOP and not taking into account dont
cares:

F =