SSE3061: Digital System Design

Lecture 3.

Tae Hee Han: [email protected]

Semiconductor Systems Engineering
Sungkyunkwan University

Agenda
 In this lecture, we will study
 Digital Logic Circuit
 Specification of Logic circuits
 Boolean Function, Truth Table, Logic diagram, etc.
 Gate symbols and truth tables
 Combinational Logic
 Sequential Logic
 Latch and Flip-Flop
 Sequential Logic Circuits
 Clock cycle time
 FSM

2
Digital Logic Circuits
 Circuits
 Analog Circuits and Digital Circuits
 Digital Logic Circuits
 Processing information represented by digital signal (discrete values)
 e.g., Binary - information is represented by only 1 and 0

Volt
5
Value 1
3
undefined
1
0
Value 0

Two kinds of digital logic circuits

– Combinational logic circuits
– Sequential logic circuits
3

Combinational Logic Circuit

 Combinational Logic Circuits are Memoryless
 Output value is decided only by the input values
 Gates (AND, OR, NOT, NAND, NOR, XOR, so on)

0 0

1 1

𝑰 Gate
𝒇 𝑰
𝒇

4
Two Kinds of Logic Circuit: Sequential Logic Circuit
 Sequential Logic Circuits are capable of memorizing
information
 Output value is decided by the state of the circuit (memorizing
information) and the input value
 Flip-Flop (F/F), Latch

𝑰 F/F (𝒇)
𝒇(𝑰, 𝑺)
storing S

Axiom in Boolean Algebra

 x+0=x x+x=x
 x⋅0=0 x⋅x=x
 x+1=1 x + x′ = 1
 x⋅1=x x ⋅ x′ = 0
 x+y=y+x x⋅y=y⋅x
 x + (y + z) = (x + y) + z x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z
 x ⋅ (y + z) = x ⋅ y + x ⋅ z x + y ⋅ z = (x + y) ⋅ (x + z)
 (x + y)′ = x′ ⋅ y′ (x ⋅ y)′ = x′ + y′
 (x′ )′ = x

6
Combinational Logic Implementation
 Two-level logic
 Implementations of two-level logic
 NAND/NOR
 Multi-level logic
 Factored forms
 And-or-invert gates
 Time behavior
 Gate delays
 Hazards
 Regular logic
 Multiplexers
 Decoders
 PLAs/ROMs

Implementations of Two-level Logic

 Sum-of-products (SOP)
 AND gates to form product
terms : minterms
 OR gate to form sum

 Product-of-sums (POS)
 OR gates to form sum
terms: maxterms
 AND gates to form product

8
Two-level Logic using NAND Gates
 Replace minterm AND gates with NAND gates
 Place compensating inversion at inputs of OR gate

Two-level Logic using NAND Gates (cont’d)

 OR gate with inverted inputs is a NAND gate
 de Morgan's: A' + B' = (A • B)'
 Two-level NAND-NAND network
 Inverted inputs are not counted
 In a typical circuit, inversion is done once and signal distributed

10
Two-level Logic using NOR Gates
 Replace maxterm OR gates with NOR gates
 Place compensating inversion at inputs of AND gate

11

Two-level Logic using NOR Gates (cont’d)

 AND gate with inverted inputs is a NOR gate
 de Morgan's: A' • B' = (A + B)'
 Two-level NOR-NOR network
 Inverted inputs are not counted
 In a typical circuit, inversion is done once and signal distributed

12
Two-level Logic using NAND and NOR Gates
 NAND-NAND and NOR-NOR networks
 de Morgan's law: (A + B)' = A' • B'
(A • B)' = A' + B'
 written differently: A+B = (A' • B')’
(A • B) = (A' + B')'
 In other words,
 OR is the same as NAND with complemented inputs
 AND is the same as NOR with complemented inputs
 NAND is the same as OR with complemented inputs
 NOR is the same as AND with complemented inputs

OR OR AND AND

NAND NAND NOR NOR

13

Conversion Between Forms

 Convert from networks of ANDs and ORs to networks of NANDs
and NORs
 Introduce appropriate inversions ("bubbles")
 Each introduced "bubble" must be matched by a corresponding
"bubble"
 Conservation of inversions
 Do not alter logic function
 Example: AND/OR to NAND/NAND

A
B
Z
C
D

14
Conversion Between Forms (cont’d)
 Example: verify equivalence of two forms

Z = [ (A • B)' • (C • D)' ]'

= [ (A' + B') • (C' + D') ]'
= [ (A' + B')' + (C' + D')' ]
= (A • B) + (C • D)

15

Conversion Between Forms (cont’d)

 Example: map AND/OR network to NOR/NOR network

Step 1 Step 2
conserve conserve
"bubbles" "bubbles"

16
Conversion Between Forms (cont’d)
 Example: verify equivalence of two forms

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

={ (A' + B') • (C' + D') }'
= (A' + B')' + (C' + D')'
= (A • B) + (C • D)

17

Multi-level Logic
 𝑋 =𝐴𝐷𝐹+𝐴𝐸𝐹+𝐵𝐷𝐹+𝐵𝐸𝐹+𝐶𝐷𝐹+𝐶𝐸𝐹+𝐺
Literal : a variable or its
 Reduced sum-of-products form – already simplified complement in a logic
expression.
 6 × 3-input AND gates + 1 × 7-input OR gate (may not exist!)
 25 wires (19 literals plus 6 internal wires) e.g.
𝑎𝑏′𝑐 + 𝑎′𝑏 + 𝑎′𝑏𝑐′ + 𝑏′𝑐′
 𝑋 = (𝐴 + 𝐵 + 𝐶)(𝐷 + 𝐸)𝐹 + 𝐺  10 literals
 Factored form – not written as two-level SOP
 1 × 3-input OR gate, 2 × 2-input OR gates, 1 × 3-input AND gate
 10 wires (7 literals plus 3 internal wires)

𝐴
𝐵
𝐶
𝑋

𝐹
𝐺

18
Conversion of Multi-level Logic to NAND Gates
 Level 4 Level 3 Level 2 Level 1
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′

19

Conversion of Multi-level Logic to NORs


Level 4 Level 3 Level 2 Level 1
C
D
original F
B
AND-OR
network A
B
C′
C
introduction and D F
conservation of B
bubbles A
B
C′

C’
D’
redrawn in terms F
of conventional B
NOR gates A’
B’
C

20
Summary for Multi-level Logic
 Advantages
 Circuits may be smaller
 Gates have smaller fan-in
 Circuits may be faster

 Disadvantages
 More difficult to design
 Tools for optimization are not as good as for two-level; but
more popular and mostly used!!
 Analysis is more complex

21

Time Behavior of Combinational Networks

 Waveforms
 Visualization of values carried on signal wires over time
 Useful in explaining sequences of events (changes in value)
 Simulation tools are used to create these waveforms
 Input to the simulator includes gates and their connections
 Input stimulus, that is, input signal waveforms
 Some terms
 Gate propagation delay: time for change at input to cause
change at output
 Min delay–typical/nominal delay–max delay
 Careful designers design for the worst case
 Rise (Rising) time: time for output to transition from low to
high voltage (from 10% to 90% of VDD)
 Fall (Falling) time: time for output to transition from high to
low voltage (from 90% to 10% of VDD)
 Pulse width: time an output stays high or low between changes

22
Hazards/Glitches
 Hazards/glitches: unwanted switching at the outputs
 Occur when different paths through circuit have different
propagation delays
 As in pulse shaping circuits, we just analyzed
 Dangerous if logic causes an action while output is unstable
 May need to guarantee absence of glitches

 Usual solutions
1. Wait until signals are stable (by using a clock): preferable
(easiest to design when there is a clock – synchronous design)
2. Design hazard-free circuits: sometimes necessary (clock not
used – asynchronous design)

23

Types of Hazards
 Static 1-hazard
 Input change causes output to go from 1 to 0 to 1
1 1
0

 Static 0-hazard
 Input change causes output to go from 0 to 1 to 0 1
0 0

 Dynamic hazards
1 1
 Input change causes a double change 0 0
from 0 to 1 to 0 to 1 OR from 1 to 0 to 1 to 0

1 1
0 0

24
Static Hazards
 Due to a literal and its complement momentarily taking on the
same value
 Thru different paths with different delays and reconverging
 May cause an output that should have stayed at the same value to
momentarily take on the wrong value
 Example: multiplexer
A
A
S
B
F
S
B
S'

S' F
static-0 hazard static-1 hazard
hazard

25

Dynamic Hazards
 Due to the same versions of a literal taking on opposite values
 Thru different paths with different delays and reconverging
 May cause an output that was to change value to change 3 times instead of
once
 Example:

A C
F
3
2 B1
B
1 B2

C B3

dynamic hazards hazard

26
 Eliminating Static Hazards
 Following two-level logic function has a hazard, e.g., when inputs
change from ABCD = 0101 to 1101
A
AB
1 1
CD 00 01 11 10 A
G1
1 A
G1
1
C′ C′
1 1 1 1
00 0 0 1 1 G3 F G3 F

A′ 0 G2 A′ 0 G2
01 1 1 1 1 D 0 0 D 1 0
D ABCD = 1100 ABCD = 1101
11 1 1 0 0 No Glitch in this case
C
10 0 0 0 0 This is the fix
B Glitch in this case
1 0 0
A 1 A 0 A 0
G1 G1 G1
C′ C′ C′
1 1 1 0 1 1
G3 F G3 F G3 F
0 0 1
A′ G2 A′ G2 A′ G2
D 1 0 D 1 0 D 1 1

ABCD = 1101 ABCD = 0101 (A′ is still 0 – NOT gate delay) ABCD = 0101 (A′ is 1)

27

Eliminating Dynamic Hazards

 Very difficult!
 A circuit that is static
hazard free can still have
dynamic hazards
1 0 1
A
G1
B
0 1
 Best approach:
Slow G3
1 0
1 01  Design critical circuits to
B G2 1 01 0
be two level and eliminate
C 1 0
1 G5 F all static hazards
0
A
1 0
 OR use good clocked
G4
B synchronous design style
1 0
Very slow

28
Making Connections
 Direct point-to-point connections between gates
 Wires we've seen so far
 Route one of many inputs to a single output ⎯ multiplexer
 Route a single input to one of many outputs ⎯ demultiplexer

control control

multiplexer demultiplexer 4×4 switch

29

Mux and Demux

 Switch implementation of multiplexers and demultiplexers
 Can be composed to make arbitrary size switching networks
 Used to implement multiple-source/multiple-destination interconnections

A Y

B Z

A Y

B Z

30
Mux and Demux (cont'd)
 Uses of multiplexers/demultiplexers in multi-point connections

A0 A1 B0 B1

Sa MUX MUX Sb multiple input sources

A B

Sum

Ss DEMUX multiple output destinations

S0 S1

31

Multiplexers/Selectors
 Multiplexers/Selectors: general concept
 data inputs, control inputs (called "selects"), 1 output
 Used to connect points to a single point
 Control signal pattern forms binary index of input connected to
output
I1 I0 A Z
0 0 0 0
0 0 1 0
A Z
0 1 0 1
Z = A' I0 + A I1 0 I0
0 1 1 0
1 I1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

two alternative forms

for a 2:1 Mux truth table

32
Gate Level Implementation of Muxes
 2:1 mux

 4:1 mux

33

Cascading Multiplexers
 Large multiplexers implemented by cascading smaller ones

8:1
I0 mux
I1 4:1 alternative
I2 mux implementation
I3
2:1 Z
mux I0 2:1 8:1
I4 I1 mux mux
I5 4:1
I6 mux I2 2:1
I7 I3 mux
4:1
Z
mux
A I4 2:1
B C
I5 mux
control signals B and C simultaneously choose
I6 2:1
one of I0, I1, I2, I3 and one of I4, I5, I6, I7
I7 mux
control signal A chooses which of the
upper or lower mux's output to gate to Z C A B

34
Demultiplexers/Decoders
 Decoders/demultiplexers: general concept
 Single data input, control inputs, outputs
 Control inputs (called “selects” (S)) represent binary index of
output to which the input is connected
 Data input usually called “enable” (G)

1:2 Decoder: 3:8 Decoder:

O0 = G ⋅ S’ O0 = G ⋅ S2’ ⋅ S1’ ⋅ S0’
O1 = G ⋅ S O1 = G ⋅ S2’ ⋅ S1’ ⋅ S0
O2 = G ⋅ S2’ ⋅ S1 ⋅ S0’
2:4 Decoder:
O3 = G ⋅ S2’ ⋅ S1 ⋅ S0
O0 = G ⋅ S1’ ⋅ S0’
O4 = G ⋅ S2 ⋅ S1’ ⋅ S0’
O1 = G ⋅ S1’ ⋅ S0
O5 = G ⋅ S2 ⋅ S1’ ⋅ S0
O2 = G ⋅ S1 ⋅ S0’
O6 = G ⋅ S2 ⋅ S1 ⋅ S0’
O3 = G ⋅ S1 ⋅ S0
O7 = G ⋅ S2 ⋅ S1 ⋅ S0

35

Gate Level Implementation of Demultiplexers

 1:2 Decoders
active-high enable active-low enable

G
00
S

01

 2:4 Decoders
G G’
O0 O0
active-high
enable active-low
O1 enable O1

10 10

11 11

S1 S0 S1 S0

36
Programmable Logic Arrays
 Pre-fabricated building block of many AND/OR gates
 Actually, NOR or NAND
 ”Personalized" by making or breaking connections among gates
 Programmable array block diagram for sum of products form

• • •
inputs

AND product OR
array terms array

outputs
• • •

37

Programmable Logic Array Example

 Multiple functions of A, B, C
 F1 = A B C
full decoder as for memory address
 F2 = A + B + C bits stored in memory
A B C
 F3 = A' B' C'
 F4 = A' + B' + C' A'B'C'
 F5 = A xor B xor C A'B'C
 F6 = A xnor B xnor C A'BC'

A'BC
A B C F0 F1 F2 F3 F4 F5
0 0 0 0 0 1 1 0 0 AB'C'
0 0 1 0 1 0 1 1 1 AB'C
0 1 0 0 1 0 1 1 1
ABC'
0 1 1 0 1 0 1 0 0
1 0 0 0 1 0 1 1 1 ABC
1 0 1 0 1 0 1 0 0
1 1 0 0 1 0 1 0 0
1 1 1 1 1 0 0 1 1 F1 F2 F3 F4 F5
F6
38
Read-only Memory (ROM)
 Two dimensional array of 1s and 0s
 Entry (row) is called a "word"
word lines (only one
 Width of row = word-size is active – decoder is
just right for this)
 Index is called an "address" 1 1 1 1
 Address is input
 Selected word is output 2n–1

i word[i] = 0011
decoder
j word[j] = 1010

internal organization 0

0 n−1

bit lines (normally pulled to 1 through

Address resistor – selectively connected to 0
by word line-controlled switches)

39

ROMs and Combinational Logic

 Combinational logic implementation (two-level canonical
form) using a ROM
F0 = A' B' C + A B' C' + A B' C
F1 = A' B' C + A' B C' + A B C
F2 = A' B' C' + A' B' C + A B' C'
F3 = A' B C + A B' C' + A B C'

A B C F0 F1 F2 F3
0 0 0 0 0 1 0 ROM
0 0 1 1 1 1 0 8 words × 4 bits/word
0 1 0 0 1 0 0
0 1 1 0 0 0 1
1 0 0 1 0 1 1
1 0 1 1 0 0 0
1 1 0 0 0 0 1 A B C F0 F1 F2 F3
1 1 1 0 1 0 0 address outputs

truth table block diagram

40
ROM Structure
 Similar to a PLA structure but with a fully decoded AND
array
 Completely flexible OR array
𝑛 address lines
• • •
inputs

memory
decoder array
2 word
(2 words
lines
by 𝑚 bits)

outputs

• • •

𝑚 data lines

41

ROM vs. PLA

 ROM approach advantageous when
 Design time is short (no need to minimize output functions)
 Most input combinations are needed (e.g., code converters)
 Little sharing of product terms among output functions

 ROM problems
 Size doubles for each additional input
 Can't exploit don't cares

 PLA approach advantageous when

 Design tools are available for multi-output minimization
 There are relatively few unique minterm combinations
 Many minterms are shared among the output functions
42
Regular Logic Structures for Two-level Logic
 ROM – full AND plane, general OR plane
 Cheap (high-volume component)
 Can implement any function of n inputs
 Medium speed

 PLA – programmable AND and OR planes

 Most expensive (most complex in design, need more
sophisticated tools)
 Can implement any function up to a product term limit
 Slow (two programmable planes)

43

Regular Logic Structures for Multi-level Logic

 Difficult to devise a regular structure for arbitrary
connections between a large set of different types of
gates
 Efficiency/speed concerns for such a structure
 Xilinx field programmable gate arrays (FPGAs) are just such
programmable multi-level structures
 Programmable multiplexers for wiring
 Lookup tables for logic functions (programming fills in the table)
 Multi-purpose cells (utilization is the big issue)

 Use multiple levels of PLAs/ROMs

 Output intermediate result
 Make it an input to be used in further logic
44
Combinational Logic Implementation Summary
 Multi-level Logic
 Conversion to NAND-NAND and NOR-NOR networks
 Transition from simple gates to more complex gate building blocks
 Reduced gate count, fan-ins, potentially faster
 More levels, harder to design

 Time Response in Combinational Networks

 Gate delays and timing waveforms
 Hazards/glitches (what they are and why they happen)

 Regular Logic
 Multiplexers/decoders
 ROMs/PLAs
 Advantages/disadvantages of each
45

Announcements
 Homework #1
 Textbook problems.
 Page 48~50: 1.3, 1.4, 1.6, 1.7, 1.8, 1.12
 Reports must be written in hand

46