Chapter 3

working with combinational

logic

1
 Working with combinational logic
n Simplification
q two-level simplification
q exploiting don’t cares
q algorithm for simplification
n Logic realization
q two-level logic and canonical forms realized with NANDs and NORs
q multi-level logic, converting between ANDs and ORs
n Time behavior
n Hardware description languages

The first important topic here is formalizing the process of boolean minimization. In the
last chapter, we illustrated how logic functions (or its expressions) can be simplified by
boolean cubes or K-maps. Here we will look at a systematic or algorithmic approach.

2
 Design example: two-bit comparator
A B C D LT EQ GT
0 0 0 0 0 1 0
0 1 1 0 0
1 0 1 0 0
N1 A LT AB<CD 1 1 1 0 0
B 0 1 0 0 0 0 1
EQ AB=CD
C 0 1 0 1 0
N2 GT AB>CD 1 0 1 0 0
D
1 1 1 0 0
1 0 0 0 0 0 1
0 1 0 0 1
1 0 0 1 0
1 1 1 0 0
block diagram 1 1 0 0 0 0 1
and 0 1 0 0 1
truth table 1 0 0 0 1
1 1 0 1 0

we'll need a 4-variable Karnaugh map

for each of the 3 output functions
Before going into the formal minimization process, let’s look at some examples.
The first example compares two numbers, each of which is two bits long, N1 is AB and
N2 is CD, where A and C are most significant bits (MSBs) while B and D are least
significant bits (LSBs).
3
 Design example: two-bit comparator (cont’d)
A A A
0 0 0 0 1 0 0 0 0 1 1 1

1 0 0 0 0 1 0 0 0 0 1 1
D D D
1 1 0 1 0 0 1 0 0 0 0 0
C C C
1 1 0 0 0 0 0 1 0 0 1 0
B B B

K-map for LT K-map for EQ K-map for GT

LT = A' B' D + A' C + B' C D

EQ = A' B' C' D' + A' B C' D + A B C D + A B' C D’ = (A xnor C) • (B xnor D)
GT = B C' D' + A C' + A B D'

EQ = (AC +A’C’)BD + (AC+A’C’)B’D’=(AC+A’C’)(BD+B’D’)

4
Design example: two-bit comparator (cont’d)
A B C D

two alternative
implementations of EQ
with and without XOR

EQ

XNOR is implemented with

at least 3 simple gates
EQ

5
 Design example: 2x2-bit multiplier
A2 A1 B2 B1 P8 P4 P2 P1
0 0 0 0 0 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
A1 P1 0 1 0 0 0 0 0 0
A2 P2 0 1 0 0 0 1
1 0 0 0 1 0
B1 P4 1 1 0 0 1 1
B2 P8 1 0 0 0 0 0 0 0
0 1 0 0 1 0
1 0 0 1 0 0
1 1 0 1 1 0
1 1 0 0 0 0 0 0
block diagram 0 1 0 0 1 1
and 1 0 0 1 1 0
truth table 1 1 1 0 0 1
4-variable K-map
for each of the 4
output functions
This is a 2bit-by-2bit multiplier that generates 4 bit output (whose MSB is P8 and LSB is
P1). Note that A2 and B2 are MSBs.

6
Design example: 2x2-bit multiplier (cont’d)
A2 A2
K-map for P8 K-map for P4
0 0 0 0 0 0 0 0
P4 = A2B2B1'
0 0 0 0 0 0 0 0
B1 + A2A1'B2 B1
0 0 1 0 0 0 0 1
B2 P8 = A2A1B2B1 B2
0 0 0 0 0 0 1 1
A1 A1

A2 A2
0 0 0 0
K-map for P2 K-map for P1 0 0 0 0
P1 = A1B1
0 0 1 1 0 1 1 0
B1 B1
0 1 0 1 0 1 1 0
B2 P2 = A2'A1B2 B2
0 1 1 0 + A1B2B1' 0 0 0 0
A1 + A2B2'B1 A1
+ A2A1'B1

7
Design example: BCD increment by 1
I8 I4 I2 I1 O8 O4 O2 O1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1
0 0 1 1 0 1 0 0
I1 O1 0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
I2 O2 0 1 1 0 0 1 1 1
I4 O4 0 1 1 1 1 0 0 0
1 0 0 0 1 0 0 1
I8 O8 1 0 0 1 0 0 0 0
1 0 1 0 X X X X
1 0 1 1 X X X X
1 1 0 0 X X X X
1 1 0 1 X X X X
block diagram 1 1 1 0 X X X X
1 1 1 1 X X X X
and
truth table
4-variable K-map for each of
the 4 output functions

8
 Design example: BCD increment by 1 (cont’d)
I8 I8
O8 O4
0 0 X 1 0 1 X 0

0 0 X 0 0 1 X 0
I1 I1
0 1 X X O8 = I4 I2 I1 + I8 I1' 1 0 X X
I2 O4 = I4 I2' + I4 I1' + I4’ I2 I1 I2
0 0 X X 0 1 X X
I4 O2 = I8’ I2’ I1 + I2 I1' I4
O1 = I1'
I8 I8
O2 O1
0 0 X 0 1 1 X 1

1 1 X 0 0 0 X 0
I1 I1
0 0 X X 0 0 X X
I2 I2
1 1 X X 1 1 X X
I4 I4
In O8, we will interpret a don’t care (DC) term as 1 if it helps to minimize the number of
literals for the elements of the ON-set. The other DC terms will be treated as 0. To
minimize the number of literals, we have to find out the maximum size subcube.
9
 Definition of terms for two-level simplification
n Implicant
q single element of ON-set or DC-set or any group of these elements that can
be combined to form a subcube (or an adjacent group)
n Prime implicant (PI)
q implicant that can't be combined with another to form a larger subcube
n Essential prime implicant
q prime implicant is essential if it alone covers an element of ON-set
q will participate in ALL possible covers of the ON-set
q DC-set used to form prime implicants but not to make implicant essential
n Objective:
q grow implicant into prime implicants
(to minimize literals per term)
q cover the ON-set with as few prime implicants as possible
(to minimize number of product terms)

So far we have examined a few examples of logic design simplification

From now on, we will try to perform simplification in a systematic or algorithmic way.
To do so, we first have to define some terminologies. 10
 Examples to illustrate terms
A
0 X 1 0 6 prime implicants:
A'B'D, BC', AC, A'C'D, AB, B'CD
1 1 1 0
D
essential
1 0 1 1
C
0 0 1 1 minimum cover: AC + BC' + A'B'D
B

A
5 prime implicants: 0 0 1 0
BD, ABC', ACD, A'BC, A'C'D
1 1 1 0
D
essential 0 1 1 1
C
0 1 0 0
minimum cover: 4 essential implicants
B
First of all, we have to find out all the possible prime implicants. Then we first transform
the essential prime implicants to boolean expressions. Then we will try to find the
minimum set of prime implicants to cover the entire on-set, called minimum cover. 11
Algorithm for two-level simplification
n Algorithm: minimum sum-of-products expression from a
Karnaugh map

q Step 1: choose an element of the ON-set

q Step 2: find "maximal" groupings of 1s and Xs adjacent to that element
n consider top/bottom row, left/right column, and corner adjacencies
n this forms prime implicants (number of elements always a power of 2)

q Repeat Steps 1 and 2 to find all prime implicants

q Step 3: revisit the 1s in the K-map

n if covered by single prime implicant, it is essential, and participates in final cover
n 1s covered by essential prime implicant do not need to be revisited
q Step 4: if there remain 1s not covered by essential prime implicants
n select the smallest number of prime implicants that cover the remaining 1s

12
 Algorithm for two-level simplification (example)
A A A
X 1 0 1 X 1 0 1 X 1 0 1

0 1 1 1 0 1 1 1 0 1 1 1
D D D
0 X X 0 0 X X 0 0 X X 0
C C C
0 1 0 1 0 1 0 1 0 1 0 1
B B B
2 primes around A'BC'D' 2 primes around ABC'D
A A A
X 1 0 1 X 1 0 1 X 1 0 1

0 1 1 1 0 1 1 1 0 1 1 1
D D D
0 X X 0 0 X X 0 0 X X 0
C C C
0 1 0 1 0 1 0 1 0 1 0 1
B B B
3 primes around AB'C'D' 2 essential primes minimum cover (3 primes)

For all 1s, check the PIs that include the 1. The PIs should be considered for all the 1s
and DCs around that can be united. Then we first choose essential PIs and then find out
the minimum cover, the minimum number of PIs that cover the remaining 1s. 13
 Activity
n List all prime implicants for the following K-map:
A
X 0 X 0

0 1 X 1
D CD’ BC BD AB AC’D
0 X X 0
C
X 1 1 1
B

n Which are essential prime implicants? CD’ BD AC’D

n What is the minimum cover? CD’ BD AC’D

Let’s start with prime implicants. Among PIs, check which are essential. Finally, we
should find out the minimum cover, which is the minimum number of PIs that cover all
the elements of the ON-set (including essential PIs)

III - Working with

Combinational Logic © Copyright 2004, Gaetano Borriello and Randy H. Katz 14
 Implementations of two-level logic
ABC
n Sum-of-products
q AND gates to form product terms (minterms)
q OR gate to form sum

n Product-of-sums
q OR gates to form sum terms (maxterms)
q AND gates to form product

In this section, we will focus on how to implement logic networks with NAND or NOR
gates. Again there are two kinds of canonical forms: S-O-P and P-O-S. A small circle is
an inverter. 15
 Two-level logic using NAND gates
n Replace minterm AND gates with NAND gates
n Place compensating inversion at inputs of OR gate
ABC ABC

NAND/NOR gates requires less CMOS TRs than AND/OR gates. So we want to change
AND/OR gates into NAND gates only (or NOR gates only)
The simplest way is to insert double inverters between AND and OR gates. Then what
happens is that AND becomes NAND just by placing bubbles. How about the OR gate?
16
 Two-level logic using NAND gates (cont’d)
n OR gate with inverted inputs is a NAND gate
q de Morgan’s: A’ + B’ = (A • B)’
n Two-level NAND-NAND network
q inverted inputs are not counted
q in a typical circuit, inversion is done once and signal distributed

Recall de Morgan’s Law. When inverters are passing through a gate, the gate should be
changed from OR to AND and vice versa.

17
 Two-level logic using NOR gates
n Replace maxterm OR gates with NOR gates
n Place compensating inversion at inputs of AND gate

In the case of P-O-S forms, the same technique is used; however, this time, the NOR gate
is the results of conversion.
Again, we insert two bubbles between OR and AND gates and push those bubbles in the
opposite directions.

18
 Two-level logic using NOR gates (cont’d)
n AND gate with inverted inputs is a NOR gate
q de Morgan’s: A’ • B’ = (A + B)’
n Two-level NOR-NOR network
q inverted inputs are not counted
q in a typical circuit, inversion is done once and signal distributed

Using de Morgan’s theorem again, the AND gate with inverted inputs is transformed into
the NOR gate as shown in the above.

19
 Two-level logic using NAND and NOR gates
n NAND-NAND and NOR-NOR networks
q de Morgan’s law: (A + B)’ = A’ • B’ (A • B)’ = A’ + B’
q written differently: A + B = (A’ • B’)’ (A • B) = (A’ + B’)’
n In other words ––
q OR is the same as NAND with complemented inputs
q AND is the same as NOR with complemented inputs
q NAND is the same as OR with complemented inputs
q NOR is the same as AND with complemented inputs

This slide summarizes what I explained about conversion from AND-OR combination to
either NAND or NOR gates. All the conversions are just variations of de morgan’s
theorem.
20
 Conversion between forms
n Convert from networks of ANDs and ORs to networks of
NANDs and NORs
q introduce appropriate inversions ("bubbles")
n Each introduced "bubble" must be matched by a
corresponding "bubble"
q conservation of inversions
q do not alter logic function
n Example: AND/OR to NAND/NAND

A A
NAND
B B
Z NAND Z
C C
NAND
D D
Again, inverters inserted between gates are called bubbles. In order to make no changes
in the logic function, the bubbles are always paired.

21
 Conversion between forms (cont’d)
n Example: verify equivalence of two forms

A A
NAND
B B
Z NAND Z
C C
NAND
D D

Z = [ (A • B)’ • (C • D)’ ]’
= [ (A’ + B’) • (C’ + D’) ]’
= [ (A’ + B’)’ + (C’ + D’)’ ]
= (A • B) + (C • D) ü

Let’s verify the conversion rule by boolean expressions and boolean theorems

22
 Conversion between forms (cont’d)
n Example: map AND/OR network to NOR/NOR network
A
B
Z
C
D

A \A
NOR NOR
\B
B
Z NOR Z
C
\C
D NOR NOR
\D
Step 1 Step 2
conserve conserve
"bubbles" "bubbles"
When an input variable, say A, is complemented, it is denoted by \A
When a S-o-P canonical form is converted to NOR networks, we have to insert two
bubbles at the input stage. And the same thing happens at the output stage.
23
 Conversion between forms (cont’d)
n Example: verify equivalence of two forms
\A
A NOR
\B
B
Z
C NOR Z

D \C
NOR
\D

Z = { [ (A’ + B’)’ + (C’ + D’)’ ]’ }’

={ (A’ + B’) • (C’ + D’) }’
= (A’ + B’)’ + (C’ + D’)’
= (A • B) + (C • D) ü

This is the boolean logic proof of the conversion in the previous slide.

24
 Multi-level logic
n x=ADF + AEF + BDF + BEF + CDF + CEF + G
q reduced sum-of-products form – already simplified
q 6 x 3-input AND gates + 1 x 7-input OR gate (that may not even exist!)
q 25 wires (19 literals plus 6 internal wires)
n x = (A + B + C) (D + E) F + G
q factored form – not written as two-level S-o-P
q 1 x 3-input OR gate, 2 x 2-input OR gates, 1 x 3-input AND gate
q 10 wires (7 literals plus 3 internal wires)

A
B
C
X
D
E
F
G
If there are common parts in a canonical form, it may be better to use multi-level logic to
reduce the number of literals and gates at the cost of delay. Again tradeoff between delay
and gate count 25
 Conversion of multi-level logic to NAND gates
Level 1 Level 2 Level 3 Level 4
C
n F = A (B + C D) + B C’ D
original F
B
AND-OR
A
network
B
\C

C
D
introduction and F
B
conservation of
A
bubbles
B
\C

C
redrawn in terms D
F
of conventional \B
NAND gates A
B
\C

Normally when we add two bubbles in a wire, two levels are converted to NAND gates.
Here we add two bubbles between AND and OR gates. 26
 Conversion between forms
n Example
A A

B F B F
C X C X
D D
original circuit add double bubbles to
invert all inputs of OR gate

A
A
X
B F
C X B F
\D C \X
\D

add double bubbles to

insert inverters to eliminate
invert output of AND gate
double bubbles on a wire

This slide illustrates how we can convert a combination of AND and OR gates into
NAND and NOT gates. As mentioned before, NOT gates can be replaced by NAND
gates by splitting the input.

27
 Conversion of multi-level logic to NORs
Level 1 Level 2 Level 3 Level 4
n F = A (B + C D) + B C’ C
D
original F
AND-OR B
network A
B
\C
C

introduction and D
F
conservation of B
bubbles A
B
\C
\C
redrawn in terms
\D
B
. F
of conventional
\ A
NOR gates
\B
C

Here we add bubbles in different position to use NOR gates. Note that the final inverter
is implemented by NOR!
28
 AND-OR-Invert (AOI) gates
n AOI function: three stages of logic — AND, OR, Invert
q multiple gates "packaged" as a single circuit block

logical concept possible implementation

A A
B B
Z Z
C C
D D

AND OR Invert NAND NAND Invert

& &
2x2 AOI gate 3x2 AOI gate
+ +
symbol symbol
& &

Here is a special case of AND-OR-Inverter gates, which is a popular combination in a

logic package. The reason it becomes a popular combination is that it can be
implemented compactly with CMOS TRs.
29
 AOI example
n Why AOI is more compact than NAND or NOR?

out = [ab+c]’:
X Y
invert 3v
symbol Z1
circuit 0v
NAND
or X Y
3v
and Z2
0v NOR

30
 Conversion to AOI forms
n General procedure to place in AOI form
q compute the complement of the function in sum-of-products form
q by grouping the 0s in the Karnaugh map

n Example: XOR implementation

q A xor B = A’ B + A B’ A’
&
q AOI form: B’ + F
A
n F = (A’ B’ + A B)’ &
B

Let’s take an example to use AOI to implement a logic function. Suppose we have to
implement a XOR function.
F = AB’+A’B. first of all, we consider F’ (note that there is an inverter at the end of AOI).
F’ = AB+A’B’. So we implement F’ in the SOP form.

31
 Summary for multi-level logic
n Advantages
q circuits may be smaller
q gates have smaller fan-in

n Disadvantages
q circuits will be slower
q more difficult to design
q tools for optimization are not as good as for two-level
q analysis is more complex
Multi-level logic design can reduce the number of gates or at least the number of fan-ins
of gates. However, optimization is more complex.

32
 Time behavior of combinational networks
n Waveforms
q visualization of values carried on signal wires over time
q useful in explaining sequences of events (changes in value)
n Simulation tools are used to create these waveforms
q input to the simulator includes gates and their connections
q input stimulus, that is, input signal waveforms
n Some terms
q gate delay — time for change at input to cause change at output
n min delay – typical/nominal delay – max delay
n careful designers design for the worst case
q rise time — time for output to transition from low to high voltage
q fall time — time for output to transition from high to low voltage
q pulse width — time that an output stays high or stays low between changes

The next topic of this chapter is the behavior of combinational logic as time goes by.
The waveform of a system can be simulated by a tool considering gates and their
connections. The output of the system is triggered by the input stimulus.
33
 Momentary changes in outputs
n Can be useful — pulse shaping circuits
n Can be a problem — incorrect circuit operation
(glitches/hazards)
A B C D
n Example: pulse shaping circuit F
q A’ • A = 0
q delays matter

D remains high for

three gate delays after F is not always 0
A changes from low to high pulse 3 gate-delays wide

Let’s see how a waveform changes over time in this case. Here, each gate is assumed to
incur 10 time unit delay. This time-varying behavior is utilized to make a periodic pulse.
34
 Oscillatory behavior
+
n Another pulse shaping circuit
resistor
A B
open C
switch D
close switch

initially open switch

undefined

Assume that each gate delay is 10 time units. Here, the output of NAND is feedback to
its input with a couple of inverters. Let’s look at the waveform of B. what does it look
like?

35
 Hardware description languages (HDLs)
n Describe hardware at varying levels of abstraction
n Structural description
q textual replacement for schematic
q hierarchical composition of modules from primitives
n Data-flow style description
q textual replacement of truth table
n Behavioral/functional description
q describe what module does, not how
q synthesis generates circuit for module
n Simulation semantics

This is the last topic of chapter 3.

So far, we rely on boolean expressions and schematic drawings to describe logic functions. However, as a logic function gets
complicated, it will become extremely hard to write and understand the logic system. Hierarchy can help to mitigate this
problem; but it is not enough. HDLs are proposed to deal with this problem.

Using HDLs, we can describe any complicated logic system. Moreover, the languages can be executed, they run like s/w. A
program emulates the behavior of the designed system as faithfully as possible. It radically reduces the time to design a system
36
 HDLs
n Abel (circa 1983) - developed by Data-I/O
q targeted to programmable logic devices
q not good for much more than state machines
n ISP (circa 1977) - research project at CMU
q simulation, but no synthesis
n Verilog (circa 1985) - developed by Gateway (absorbed by Cadence)
q similar to Pascal and C
q delay is only interaction with simulator
q fairly efficient and easy to write
q IEEE standard
n VHDL (circa 1987) - DoD sponsored standard V: very high speed IC
q similar to Ada (emphasis on re-use and maintainability)
q simulation semantics visible
q very general but verbose
q IEEE standard

Verilog and VHDL are the most popular HDLs.

This course does not aim to cover HDLs in-depth.
37
Verilog power
n Alternative to schematics (interconnection of components)
n Much more powerful than schematics
q Boolean eqs.
q Truth table
q Complex operations (addition, …)
n Represent entire system – designed as a hierarchy
n Many tools available
Verilog design example
n Design half of a 74x139 (Dual 2-to-4 decoder)
q Three different types of programming (description)
n Structural description
n Data-flow style description
n Behavioral description
74x139

G U6
U1
U7

A_i U8
A_L
U3 U5
B_L B_i U9
U2 U4
Behavioral Description
n To this point, structural and data-flow description à
alternatives of schematic and truth table

n Behavioral description: richest set of language element à

algorithmic description of hardware

n Main element: always

Sensitivity list

always @ (signal_name1, signal_name2, …)

begin
----
Sequential statements
----
- loops
end
- case statements
- if-then-else
Verilog design flow
½ 74x139 timing diagram
½ 74x139 fitting result
Magnification of a MC (Macrocell)
Hierarchical Design (2 ´ ½ 74x139)
 HDLs vs. programming languages (PLs)
n Program structure
q instantiation of multiple components of the same type
q specify interconnections between modules via schematic
q hierarchy of modules
n Assignment
q continuous assignment (logic always computes)
q propagation delay (computation takes time)
q timing of signals is important (when does computation have its effect)
n Data structures
q size explicitly spelled out - no dynamic structures
q no pointers
n Parallelism
q hardware is naturally parallel (must support multiple threads)
q assignments can occur in parallel (not just sequentially)

Even though a hierarchical structure is common on HDLs and PLs, there are some
fundamental differences between HDLs and PLs.
For example, continuous assignment and propagation delay are not typically supported in
PLs.
50
 HDLs and combinational logic
n Modules - specification of inputs, outputs, bidirectional,
and internal signals

n Continuous assignment - a gate’s output is a function of

its inputs at all times (doesn’t need to wait to be "called")

n Propagation delay- concept of time and delay in input

affecting gate output

n Composition - connecting modules together with wires

n Hierarchy - modules encapsulate functional blocks

HDLs can describe every aspect of combinational logic systems.

51
Working with combinational logic summary
n Design problems
q filling in truth tables
q incompletely specified functions
q simplifying two-level logic
n Realizing two-level logic
q NAND and NOR networks
q networks of Boolean functions and their time behavior
n Time behavior
n Hardware description languages
n Later
q combinational logic technologies
q more design case studies

52