Transcript Chapter 03 - Digital Logic

Chapter 3 - Digital Logic
B
A
Success is not the key to happiness.
Happiness is the key to success.
If you love what you are doing, you
will be successful.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
2
Concepts to Learn…










The Transistor
Devices: Inverter, NAND, NOR, Drivers
De Morgan’s Law
Translations
Decoders, Multiplexors, Adders, PLAs
Logical Completeness
Sequential Logic
Latches
Memory
Finite State Machine
BYU CS/ECEn 124
Chapter 3 - Digital Logic
3
The Transistor
History of the Transistor


Around 1945, Bell Labs scientists
discovered that silicon was comprised of
two distinct regions differentiated by the
way in which they favored current flow.
The area that favored positive current flow
they named "p" and the area that favored
negative current flow they named "n".
BYU CS/ECEn 124
Chapter 3 - Digital Logic
4
The Transistor
The Transistor Effect

The transistor effect describes the change
from a condition of conductivity (switched
“on”, full current flow) to a condition of
insulation (switched “off”, no current flow).
BYU CS/ECEn 124
Chapter 3 - Digital Logic
5
The Transistor
Digital Logic Circuits





Computers = large number of simple structures
Intel 4004 = 2,300 transistors
Intel Pentium 4 = 42 million transistors
Intel Core 2 Duo = 291 million transistors
Intel i7 “Bloomfield” = 731 million transistors
BYU CS/ECEn 124
Chapter 3 - Digital Logic
6
The Transistor
Moore’s Law
2000’s
1990’s
1980’s
1970’s
1960’s
1950’s
1947
Early 1900’s
BYU CS/ECEn 124
Moore’s Law: The number of transistors
per area doubles every 1.5 - 2 years.
Chapter 3 - Digital Logic
7
The Transistor
The MOS Transistor

A transistor acts like a switch

Off = open circuit
On = closed circuit
P-type Transistor
N-type Transistor
gate FET
0 off
1 on
gate
current flow
gate
current flow
conducts current only when "on"
complementary
gate FET
0 on
1 off
MOS = metal-oxide semiconductor
CMOS = complementary MOS with both N and P transistors
BYU CS/ECEn 124
Chapter 3 - Digital Logic
8
The Transistor
Field Effect Transistor
P type
N type
S
G
S
G
D
D
Gate = Ground = ‘0’
BYU CS/ECEn 124
Chapter 3 - Digital Logic
9
The Transistor
Field Effect Transistor Operation
P type
N type
S
G
S
G
D
D
Gate = Vcc = ‘1’
BYU CS/ECEn 124
Chapter 3 - Digital Logic
10
The Transistor
CMOS Gates
We want complementary pull-up and pulldown logic: the pull-down is “on” when
the pull-up is “off”, and visa-versa.
Pullup
Structure
F
Complementary
The “C” in CMOS
Pulldown
Structure
Even in the digital world "EVERYTHING IS ANALOG"!
BYU CS/ECEn 124
Chapter 3 - Digital Logic
11
Digital Logic Devices
The Inverter
1
1
1
on
off
in
out
0
1
1
0
on
0
in out
0 1
1 0
0
0
This is a truth-table. It
tells what the output will be
for all combinations of the
inputs.
Symbols are
abstractions!
BYU CS/ECEn 124
off
Chapter 3 - Digital Logic
Inverter Symbols
12
Digital Logic Devices
The NOR Gate (NOT-OR)
1
1
1
a
0
on
0
b
0
on
1
nor
on
off
1
0
0
ab
00
01
10
11
nor
1
0
0
0
BYU CS/ECEn 124
0
off
off
0
0
on
0
off
0
NOR Symbols
Chapter 3 - Digital Logic
13
Digital Logic Devices
The OR Gate

How do you build an OR gate?
a
a
or
or
b
b
0
ab
00
01
10
11
BYU CS/ECEn 124
or
0
1
1
1
OR Symbol
Chapter 3 - Digital Logic
14
Digital Logic Devices
The NAND Gate (NOT-AND)
1
1
1
1
1
1
off
off
on
off
NAND
b
1
0
1
1
on
a
on
1
0
on
0
ab
00
01
10
11
nand
1
1
1
0
BYU CS/ECEn 124
off
0
0
NAND Symbols
Chapter 3 - Digital Logic
15
Digital Logic Devices
The AND Gate

How do you build an AND gate?
a
and
AND
b
b
a
a
0
0
1
1
b AND
0 0
1 0
0 0
1 1
BYU CS/ECEn 124
AND Symbol
Chapter 3 - Digital Logic
16
Digital Logic Devices
Why Inverting Logic?

Why can’t we use



Because



N transistors to pull up to Vcc, and
P transistors to pull down to ground?
N transistors do not pass good voltage levels for 1’s
P transistors do not pass good voltage levels for 0’s
It just doesn’t work electronically! So…


?
?
Only use P transistors in pull-up structures!
Only use N transistors in pull-down structures!
Pullup
Structure
F
Pulldown
Structure
BYU CS/ECEn 124
Chapter 3 - Digital Logic
17
Digital Logic Devices
Drivers

Why can’t we use CMOS transistors to connect
to a bus?




P transistors to pull up to Vcc, and
N transistors to pull down to ground
Because connecting Vcc to ground let’s the
magic smoke out!
Solution: Tri-state driver
BYU CS/ECEn 124
Chapter 3 - Digital Logic
18
De Morgan’s Law
De Morgan’s Law
To distribute the
bar, change the
operation.
A B  AB
NOR Symbols
A B  A  B
NAND Symbols
BYU CS/ECEn 124
Chapter 3 - Digital Logic
19
De Morgan’s Law
De Morgan’s Proof
A
B
AB
1
1
1
1
1
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
A
B
0
0
0
0
1
1
1
BYU CS/ECEn 124
A+B A+B
Chapter 3 - Digital Logic
20
Translations
Reading Functions from Symbols
The output will be high if
any of the inputs are low...
a
0
0
1
1
b
0
1
0
1
out
1
1
1
0
It’s just a NAND gate
drawn a different way!!!
BYU CS/ECEn 124
The output will be low if
all of the inputs are high...
The output will be high if
the first input is low OR
the second input is high...
Chapter 3 - Digital Logic
21
Translations
You Should Know How to Translate
These are three
different ways of
representing logical
information
Logic
Gates
BYU CS/ECEn 124
You can convert any
one of them to any
other
Logic
Equations
Truth
Tables
Chapter 3 - Digital Logic
22
Translations
From Equations to Gates
y = NOT(s) AND a AND NOT(b)
s
a
y
b
s
a
y
b
BYU CS/ECEn 124
Chapter 3 - Digital Logic
23
Translations
From Equations to Gates
y = (~s  a  ~b) + (~s  a  b) + (s  ~a  b) + (s  a  b)
s
a
b
s
a
out
b
s
a
b
s
a
b
BYU CS/ECEn 124
Chapter 3 - Digital Logic
24
Translations
From Truth tables to Gates


Each row of truth table is an AND gate
Each output column is an OR gate
s
0
0
0
0
1
1
1
1
a
0
0
1
1
0
0
1
1
b
0
1
0
1
0
1
0
1
out
0
0
1
1
0
1
0
1
s
a
b
s
a
b
When we write s we mean
the inverse of s or s after it has
gone through an inverter.
out
s
a
b
s
a
b
BYU CS/ECEn 124
Chapter 3 - Digital Logic
25
Translations
From Truth table to Equations

Write out truth table a combination of AND’s
and OR’s

equivalent to gates
easily converted to gates
s
0
0
0
0
1
1
1
1
a
0
0
1
1
0
0
1
1

b
0
1
0
1
0
1
0
1
out
0
0
1
1
0
1
0
1
BYU CS/ECEn 124
out =
s ab
OR
s ab
OR
Chapter 3 - Digital Logic
sa b
OR
sab
26
Translations
From Equations to Truth Tables
For each AND term


fill in the proper row on the truth table
out  s a  sb
out  s a OR sb
out  s ab  s ab  sa b  sab
s
0
0
0
0
1
1
1
1
a
0
0
1
1
0
0
1
1
b
0
1
0
1
0
1
0
1
out
0
0
1
1
0
1
0
1
out 
s ab OR
s ab OR
sa b OR
sab
s
0
0
0
0
1
1
1
1
a
0
0
1
1
0
0
1
1
b
0
1
0
1
0
1
0
1
out
0
0
1
1
0
1
0
1
Contains a don’t care out is independent of b
There is a whole field of
boolean minimization that
capitalizes on this property.
You will learn this in the
next class...
BYU CS/ECEn 124
Chapter 3 - Digital Logic
27
Translations
Manipulating Logic Expressions
Laws (basic identities) of Boolean algebra.
Law
OR
AND
Identity
One/Zero
Idempotent
Inverse
Commutative
Associative
Distributive
DeMorgan’s
x0=x
x1=x
x1=1
x0=0
xx= x
xx=x
xx=1
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
BYU CS/ECEn 124
Chapter 3 - Digital Logic
28
Some Special Function Blocks
Circuits
Decoders

Decode the input and signify its value by
raising just one of its outputs.
W
A
W
B
X
1 if A,B = 00
1 if A,B = 01
Y
1 if A,B = 10
Z
1 if A,B = 11
2-to-4
Decoder
X
Y
Z
A
B
DECODER
Symbol
BYU CS/ECEn 124
Chapter 3 - Digital Logic
30
Circuits
Decoders

Write the truth table
A
W
B
X
Y
A
0
0
1
1
B
0
1
0
1
W
1
0
0
0
X
0
1
0
0
Y
0
0
1
0
Z
0
0
0
1
Z
BYU CS/ECEn 124
Chapter 3 - Digital Logic
31
Circuits
Multiplexors

Connect one of its inputs to its output according
to select signals
A
B
S
A
B
0
1
S
C
Symbols are
abstractions!
MULTIPLEXOR Symbol
C


Useful for selecting one from a collection of data
inputs.
Usually has 2n inputs and n select lines.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
32
Circuits
Multiplexors

Write the truth table
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
S
0
1
0
1
0
1
0
1
BYU CS/ECEn 124
C
0
0
0
1
1
0
1
1
A simpler way…
A
B
0
1
S
C
Chapter 3 - Digital Logic
A
0
1
X
X
B
X
X
0
1
S
0
0
1
1
C
0
1
0
1
33
Circuits
Adders

At each digit position add together the 2
operands and the carry-in
c
0110
+0101
1011
b3 a3
b2 a2
b1 a1
b0 a0
Full
c3 Adder
Full
c2 Adder
Full
c1 Adder
Full
c0 Adder
s3
s2
s1
‘0’
s0
Just like longhand addition
except it’s in binary...
BYU CS/ECEn 124
Chapter 3 - Digital Logic
34
Circuits
Full Adder Module Design
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
BYU CS/ECEn 124
cyout sum
0
0
0
1
0
1
1
0
0
1
1
0
1
0
1
1
cyout  a bc  ab c  abc  abc
sum  a b c  a bc  ab c  abc
 abc
Chapter 3 - Digital Logic
35
PLAs
Programmable Logic Arrays

Programmable Logic Array (PLA) can be used to
implement any logic function



Take truth table of any logic function
Convert into equation (any truth table can be expressed as set
of “and” expressions “or”ed together)
PLA programmed by making/breaking wire connections
?
?
?
Outputs:
?
?
?
?
?
?
?
Inputs:
?
?
?
?
?
?
?
?
?
?
?
?
BYU CS/ECEn 124
?
?
?
?
?
Chapter 3 - Digital Logic
36
PLAs
PLA Example
Out1 = ABC + ABC + ABC
Out2 = ABC + ABC + ABC
Out3 = ABC + ABC
A B C
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
?
?
?
Out1 Out2 Out3
0
1
0
1
0
1
0
1
BYU CS/ECEn 124
0
1
0
0
1
0
0
1
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
Out1
Out2
Out3
?
?
?
?
?
?
Outputs
Inputs
A
B
C
?
?
?
?
?
?
?
?
?
Chapter 3 - Digital Logic
?
?
?
?
?
?
?
?
?
37
Logical Completeness
Logical Completeness
What is the minimum set of gate types needed to
implement any logic function?
 AND gate, OR gate, INVERTER

AND gate, INVERTER

OR can be replaced by an AND and three INVERTERS
DeMorgan’s Theorem
A
B
A
B A
B
A
B

OR gate, INVERTER

AND can be replaced by an OR and three INVERTERS
DeMorgan’s Theorem
A
B
A
B A
B
A
B
BYU CS/ECEn 124
Chapter 3 - Digital Logic
38
Logical Completeness
Logical Completeness

NAND

INVERTER

AND

OR
BYU CS/ECEn 124
NAND (by itself) is logically complete if
you can implement an INVERTER, AND,
and OR gate using only NAND gates.
Chapter 3 - Digital Logic
39
Sequential Logic
Combinational vs. Sequential

Two types of “combination” locks
30
4 1 8 4
25
5
20
10
15
Combinational
Success depends only on
the values, not the order in
which they are set.
BYU CS/ECEn 124
Sequential
Success depends on
the sequence of values
(e.g, R-13, L-22, R-3).
Chapter 3 - Digital Logic
40
Sequential Logic
Storage Elements

Everything so far is called combinational


Real computing systems need storage



the output is strictly a function of the current
inputs
for holding previously computed values
for remembering its place (state) in the middle
of a multi-step operation
Storage elements remember what was
stored in them for later retrieval using
feedback
BYU CS/ECEn 124
Chapter 3 - Digital Logic
41
Sequential Logic
Bi-Stability = Key to Memory
This is a stable state –
it will sit like this forever
0
1
0
This is also a stable state –
it will sit like this forever
1
0
1
When there are 2 stable states - a bi-stable circuit…
BYU CS/ECEn 124
Chapter 3 - Digital Logic
42
Sequential Logic
RS Latch

Signals s and r are active low

they change the circuit when they go low
s
s
q
s
q
q
Cross-coupled
NAND gates
same
same
q
r



q
r
q
Note the
feedback
r
Output q goes high when s goes low
Output q goes low when r goes low
Output q remains the same otherwise
BYU CS/ECEn 124
Chapter 3 - Digital Logic
43
Sequential Logic
RS Latch – Bi-Stable Circuit
1
s
q
1
q
1
r
0
This is a stable state –
it will sit like this forever
BYU CS/ECEn 124
1
s
q
0
q
1
r
1
This is also a stable state –
it will sit like this forever
Chapter 3 - Digital Logic
44
Sequential Logic
RS Latch
(continued)
s
q
q
r
1
1
0
1
BYU CS/ECEn 124
0
1
1
0
1
1
1
0
Chapter 3 - Digital Logic
1
0
0
1
1
1
0
1
45
Sequential Logic
RS Latch : Next State Table

Defines output as a function of inputs (s
and r) and current output (q, its state)
s
0
0
0
0
1
1
1
1
BYU CS/ECEn 124
r
0
0
1
1
0
0
1
1
q
0
1
0
1
0
1
0
1
qnext
x
x
1
1
0
0
q
q
Chapter 3 - Digital Logic
not allowed
set
reset
keep old state
46
Latch
Gated D Latch

Output q gets value from input d only when we is
high

we stands for write enable, think of it as a load signal
d
s
q
we
q
WE
D
Q
D-Latch
r
Symbols are
abstractions!
BYU CS/ECEn 124
Chapter 3 - Digital Logic
LATCH Symbol
47
Quiz
1. What is a bi-stable circuit?
2. Draw a logic circuit (using N and P type
transistors) for a 3 input NAND gate.
3. With a RS NAND latch, why can’t R and
S be low at the same time?
4. How is Q set with the following latch?
BYU CS/ECEn 124
Chapter 3 - Digital Logic
48
Quiz (Answers)
1. What is a bi-stable circuit?

When the circuit has 2 stable states
2. Draw a logic circuit (using N and P type
transistors) for a 3 input NAND gate.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
49
Quiz (Answers)
3. With a RS NAND latch, why can’t R and
S be low at the same time?



This state would force both outputs to a logic
1, overriding the feedback latching action.
Outputs Q and Q' must have opposite logic
levels.
Results in a “race” condition – final state of
the latch cannot be determined.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
50
Quiz (Answers)
4. How is Q set with the following latch?

Q is set by changing input S from a logic 0 to
a logic 1
0
0
1
0
0
BYU CS/ECEn 124
1
Chapter 3 - Digital Logic
51
Latch
Register

A computer register is a place to store a
collection of bits
d3
we
d2
d1
d0
d
D-Latch
D-Latch
D-Latch
we
D-Latch
Register
q
q3


REGISTER Symbol
q2
q1
q0
Very fast memory
Numbered right to left (LSB on the right)
BYU CS/ECEn 124
Chapter 3 - Digital Logic
52
Memory
Memory


A collection of addressable locations
Address selects which location to read from
or write to
A memory with n address wires has 2n locations.
The number of data wires in equal the number of
data wires out.
we
address
d
Memory is changed with we is asserted.
n
m
Memory
m
q
q always reflects the contents stored at the
addressed memory location.
Memory can be viewed as a large collection of
slower registers.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
53
Memory
Memory Usage
addr
000
001
010
011
100
101
110
111
value
1001
0000
1111
1011
0000
0011
1010
0101
addr => 101
data => 0000
we => 1
addr
000
001
010
011
100
101
110
111
value
1001
0000
1111
1011
0000
0000
1010
0101
addr => 101
data => 0000
we => 0
addr
000
001
010
011
100
101
110
111
value
1001
0000
1111
1011
0000
0000
1010
0101
addr => 111
data => 1100
we => 1
addr
000
001
010
011
100
101
110
111
value
1001
0000
1111
1011
0000
0000
1010
1100
Power-Up State
(random bits)
addr => 000
data => 0000
we => 1
addr
000
001
010
011
100
101
110
111
BYU CS/ECEn 124
value
0000
0000
1111
1011
0000
0000
1010
1100
addr => 000
data => 0110
we => 1
addr
000
001
010
011
100
101
110
111
value
0110
0000
1111
1011
0000
0000
1010
1100
addr => 110
data => 0110
we => 0
Chapter 3 - Digital Logic
addr
000
001
010
011
100
101
110
111
value
0110
0000
1111
1011
0000
0000
1010
1100
54
Memory
Building a Memory From Latches
writeEnable
00
2-to-4
Decoder
01
10
11
a1 a0
address
n=2
we
we
we
we
d input
Register
Register
Register
Register
This is a functional view.
The key parts are:
address decoder
memory cells (registers)
output selector (mux)
BYU CS/ECEn 124
Chapter 3 - Digital Logic
q0
q1
q output
q2
q3
we
address
d
MEMORY
Symbol
n
m
Memory
m
q
55
Memory
Address Space

When we say a computer has a 4GB
(giga-byte) address space we mean






it has enough address lines to address 232
address locations
Kilobyte= 210 or 10241 bytes
Megabyte
= 220 or 10242 bytes
Gigabyte
= 230 or 10243 bytes
Tera-byte
= 240 or 10244 bytes
Peta-byte
= 250 or 10245 bytes
BYU CS/ECEn 124
Chapter 3 - Digital Logic
56
Finite State Machine
The MSP430
You may not know how it works, but you know the parts its made from!
Status Register
Program Counter
Register
Memory
Multiplexor
Memory
Mapped I/O
Bus Driver
16 16-bit
Registers
Instruction Register
BYU CS/ECEn 124
Arithmetic Logic Unit
Chapter 3 - Digital Logic
Lots of Gates
60
START HERE
BYU CS/ECEn 124
Chapter 3 - Digital Logic
61
Finite State Machine
Sequential State Machine

Another type of sequential circuit


Combines combinational logic with storage
“Remembers” state, and changes output (and state)
based on inputs and current state
State Machine
Inputs
Combinational
Logic Circuit
Outputs
Storage
Elements
BYU CS/ECEn 124
Chapter 3 - Digital Logic
62
Finite State Machine
State of a System


The state of a system is a snapshot of all
the relevant elements of the system at the
moment the snapshot is taken.
Examples:

The state of a basketball game can be represented by
the scoreboard (ie. number of points, time remaining,
possession, etc.)

The state of a tic-tac-toe game can be represented by
the placement of X’s and O’s on the board.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
63
Finite State Machine
Combinational vs. Sequential

Two types of “combination” locks
30
4 1 8 4
25
5
20
10
15
Combinational
Success depends only on
the values, not the order in
which they are set.
BYU CS/ECEn 124
Sequential
Success depends on
the sequence of values
(e.g, R-13, L-22, R-3).
Chapter 3 - Digital Logic
64
Finite State Machine
State of Sequential Lock

Our lock example has four different states,
labeled A-D:
 A: The lock is not open, and no relevant
operations have been performed.
 B: The lock is not open, and the user has
completed the R-13 operation.
 C: The lock is not open, and the user has
completed R-13, followed by L-22.
 D: The lock is open.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
65
Finite State Machine
State Diagram

Shows states and actions that cause a
transition between states.
Open = 0
Open = 0
Open = 0
Open = 1
BYU CS/ECEn 124
Chapter 3 - Digital Logic
66
Finite State Machine
Finite State Machine

A description of a system with the
following components:






A finite number of states
A finite number of external inputs
A finite number of external outputs
An explicit specification of all state transitions
An explicit specification of what determines each
external output value
Often described by a state diagram.


Inputs trigger state transitions.
Outputs are associated with each state (or with each
transition).
BYU CS/ECEn 124
Chapter 3 - Digital Logic
67
Finite State Machine
The Clock

Frequently, a clock circuit triggers transition from
one state to the next.
“1”
“0”
One
Cycle

time
At the beginning of each clock cycle, state
machine makes a transition, based on the current
state and the external (or internal) inputs.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
68
Finite State Machine
FSM Implementation


Combinational logic
 Determine outputs and next state.
Storage elements
 Maintains state representation.
State Machine
Inputs
Clock
BYU CS/ECEn 124
Combinational
Logic Circuit
Outputs
Storage
Elements
Chapter 3 - Digital Logic
69
Finite State Machine
Storage: Master-Slave Flipflop

A pair of gated D-latches isolates next state
from current state.
During 1st phase (clock=1),
previously-computed state
becomes current state and is
sent to the logic circuit.
BYU CS/ECEn 124
During 2nd phase (clock=0),
next state, computed by
logic circuit, is stored in
Latch A.
Chapter 3 - Digital Logic
70
Finite State Machine
Storage: Master-Slave Flipflop
“1”
“0”
time
SET/RESET
BYU CS/ECEn 124
Chapter 3 - Digital Logic
HOLD
71
Finite State Machine
Storage: Master-Slave Flipflop
“1”
“0”
time
HOLD
BYU CS/ECEn 124
SET/RESET
Chapter 3 - Digital Logic
72
Another view
Input
Combinational
Logic
Slave
Master
LOW
BYU CS/ECEn 124
Chapter 3 - Digital Logic
73
Another view
Input
Combinational
Logic
Slave
Master
LOW
BYU CS/ECEn 124
Chapter 3 - Digital Logic
74
Another view
Input
Combinational
Logic
Slave
Master
HIGH
BYU CS/ECEn 124
Chapter 3 - Digital Logic
75
Another view
Input
Combinational
Logic
Slave
Master
HIGH
BYU CS/ECEn 124
Chapter 3 - Digital Logic
76
Another view
Input
Combinational
Logic
Slave
Master
HIGH
BYU CS/ECEn 124
Chapter 3 - Digital Logic
77
Another view
Input
Combinational
Logic
Slave
Master
LOW
BYU CS/ECEn 124
Chapter 3 - Digital Logic
78
Another view
Input
Combinational
Logic
Slave
Master
LOW
BYU CS/ECEn 124
Chapter 3 - Digital Logic
79
Finite State Machine
Storage Elements



Each master-slave flip flop stores one state bit.
The number of storage elements (flip flops) needed is
determined by the number of states (and the
representation of each state).
Examples:
 Sequential lock
 4 states – 2 bits
 Basketball scoreboard
 7 bits for each score, 5 bits for minutes, 6 bits for
seconds, 1 bit for possession arrow, 1 bit for half, …
 Blinking traffic sign
 4 states – 2 bits
BYU CS/ECEn 124
Chapter 3 - Digital Logic
80
Finite State Machine
Finite State Machine Example

A blinking traffic sign





No lights on
1 & 2 on
1, 2, 3, & 4 on
1, 2, 3, 4, & 5 on
Repeat as long as switch
is turned on
BYU CS/ECEn 124
Chapter 3 - Digital Logic
3
4
1
5
2
DANGER
MOVE
RIGHT
81
Finite State Machine
Traffic Sign State Diagram
Switch on
Transition on each clock cycle.
State bit S1
Switch off
State bit S0
Outputs
BYU CS/ECEn 124
Chapter 3 - Digital Logic
82
Finite State Machine
Traffic Sign Truth Tables
Outputs
(depend only on state: S1S0)
Next State: S1'S0'
(depend on state and input)
Lights 1 and 2
Lights 3 and 4
Light 5
S1
0
0
1
1
S0
0
1
0
1
BYU CS/ECEn 124
Z
0
1
1
1
Y
0
0
1
1
X
0
0
0
1
Switch
In S1
0 X
1 0
1 0
1 1
1 1
S0
X
0
1
0
1
S1'
0
0
1
1
0
S0'
0
1
0
1
0
Whenever In=0, next state is 00.
Chapter 3 - Digital Logic
83
Finite State Machine
Traffic Sign Logic
BYU CS/ECEn 124
Chapter 3 - Digital Logic
84
Finite State Machine
From Logic to Data Path



The data path of a computer is all the logic used to
process information.
 See the data path of the LC-3 on next slide.
Combinational Logic
 Decoders -- convert instructions into control signals
 Multiplexers -- select inputs and outputs
 ALU (Arithmetic and Logic Unit) -- operations on data
Sequential Logic
 State machine -- coordinate control signals and data
movement
 Registers and latches -- storage elements
BYU CS/ECEn 124
Chapter 3 - Digital Logic
85
STOP HERE
BYU CS/ECEn 124
Chapter 3 - Digital Logic
86
Finite State Machine
MSP430 Finite State Machine
DECODE:NOCLK:MOV||EVSRC
EVDST:CLK1:MOV,Rd|D,ROX=Rd|STORE
EVSRC:CLK1:MOV,Rs|S,ROX=Rs|EVDST
STORE:CLK1:MOV,Rd|ALU,RWE,RIX=Rd|FETCH
...
BYU CS/ECEn 124
Chapter 3 - Digital Logic
87
BYU CS/ECEn 124
Chapter 3 - Digital Logic
88
Review…
Signals, Logic Operators, Gates
Name
NOT
AND
OR
XOR
Operator
sign and
alternat e(s)
x _
x or x
xy
x y
xy
x y
xy
x  y
Output
is 1 iff:
Input is 0
Both inputs
are 1s
At least one
input is 1
Inputs are
not equal
1x
x y or xy
x  y  xy
x  y 2xy
Graphical
symbol
Arithmetic
expression
BYU CS/ECEn 124
Chapter 3 - Digital Logic
90
Variations in Gate Symbols
AND
OR
NAND
NOR
XNOR
Gates with more than two inputs and/or with inverted signals at
input or output.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
91
Gates as Control Elements
Enable/Pass signal
e
Enable/Pass signal
e
Data out
x or 0
Data in
x
Data in
x
(a) AND gate for controlled trans fer
Data out
x or “high impedance”
(b) Tristate buffer
e
e
0
0
1
x
(c) Model for AND switch.
0
ex
1
x
No data
or x
(d) Model for tristate buffer.
An AND gate and a tristate buffer act as controlled switches or valves.
An inverting buffer is logically the same as a NOT gate.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
92
Wired OR and Bus Connections
ex
ex
x
x
ey
ey
Data out
(x, y, z, or 0)
y
y
ez
Data out
(x, y, z,
or high
impedance)
ez
z
z
(a) Wired OR of product terms
(b) Wired OR of t ristate outputs
Wired OR allows tying together of several controlled signals.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
93
Boolean Functions / Expressions
Ways of specifying a logic function
 Truth table: 2n row, “don’t-care” in input or output
 Logic expression: w  (x  y  z), product-of-sums,
sum-of-products, equivalent expressions
 Word statement: Alarm will sound if the door
is opened while the security system is engaged,
or when the smoke detector is triggered
 Logic circuit diagram: Synthesis vs analysis
BYU CS/ECEn 124
Chapter 3 - Digital Logic
94
Manipulating Logic Expressions
Laws (basic identities) of Boolean algebra.
Name of law
OR version
AND version
Identity
One/Zero
x0=x
x1=x
x1=1
x0=0
Idempotent
Inverse
Commutative
Associative
xx= x
xx=x
xx=1
xx=0
xy=yx
xy=yx
(x  y)  z = x  (y  z)
(x y) z = x (y z)
Distributive
DeMorgan’s
x  (y z) = (x  y) (x  z)
x (y  z) = (x y)  (x z)
(x  y) = x  y 
(x y) = x   y 
BYU CS/ECEn 124
Chapter 3 - Digital Logic
95
Designing Gate Networks
 AND-OR, NAND-NAND, OR-AND, NOR-NOR
 Logic optimization: cost, speed, power dissipation
x
y
y
z
z
x
(a) A ND-OR circuit
x
y
y
z
z
x
x
y
y
z
z
x
(b) Int ermediate circuit
(c) NA ND-NA ND equivalent
A two-level AND-OR circuit and two equivalent circuits.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
96
BCD-to-Seven-Segment Decoder
4-bit input in [0, 9]
x3 x2 x1 x0
Signals to
enable or
turn on the
segments
e0
0
e5
5
1
e6
e4
e3
6
4
2
3
e2
e1
The logic circuit that generates the enable signal for the lowermost
segment (number 3) in a seven-segment display unit.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
97
Useful Combinational Parts
 High-level building blocks
 Much like prefab parts used in building a house
 Arithmetic components will be covered in Part III
(adders, multipliers, ALUs)
 Here we cover three useful parts:
multiplexers, decoders/demultiplexers, encoders
BYU CS/ECEn 124
Chapter 3 - Digital Logic
98
Multiplexers
x0
z
x1
y
0
x0
x1
(a) 2-to-1 mux
1
0
/
32
1
/
32
x0
x1
x2
x3
0
1
2
3
z
y
y1y0
(d) Mux array
y
x0
0
x1
1
x2
0
x3
1
(e) 4-to-1 mux with enable
x0
0
x1
1
z
y
(c) Mux symbol
(b) Switch view
e (Enable)
/
32
z
y0
0
z
1
y1
y0
(e) 4-to-1 mux design
Multiplexer (mux), or selector, allows one of several inputs to be
selected and routed to output depending on the binary value of a set of
selection or address signals provided to it.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
99
Decoders/Demultiplexers
y1
y0
x0
x1
x2
y1y0
y1y0
0
1
2
3
x0
x1
x2
x3
x3
(a) 2-to-4 decoder
(b) Decoder symbol
e
(Enable)
0
1
2
3
x0
x1
x2
x3
(c) Demultiplexer, or
decoder wit h “enable”
A decoder allows the selection of one of 2a options using an a-bit
address as input. A demultiplexer (demux) is a decoder that only
selects an output if its enable signal is asserted.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
100
Encoders
x0
x1
x0
x1
x2
x3
x2
x3
y1y0
y1y0
(a) 4-to-2 encoder
0
1
2
3
(b) Enc oder symbol
A 2a-to-a encoder outputs an a-bit binary number equal to the
index of the single 1 among its 2a inputs.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
101
Programmable Combinational Parts
A programmable combinational part can do the job of
many gates or gate networks
Programmed by cutting existing connections (fuses)
or establishing new connections (antifuses)
 Programmable ROM (PROM)
 Programmable array logic (PAL)
 Programmable logic array (PLA)
BYU CS/ECEn 124
Chapter 3 - Digital Logic
102
PROMs
w
x
x
y
y
z
z
Inputs
Decoder
w
.
.
.
...
Outputs
(a) Programmable
OR gates
(b) Logic equivalent
of part a
(c) Programmable read-only
memory (PROM)
Programmable connections and their use in a PROM.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
103
PALs and PLAs
Inputs
8-input
ANDs
...
AND
array
(AND
plane)
.
.
.
6-input
ANDs
OR
array
(OR
plane)
...
4-input
ORs
Outputs
(a) General programmable
combinational logic
(b) PAL: programmable
AND array, fixed OR array
(c) PLA: programmable
AND and OR arrays
Programmable combinational logic: general structure and two classes
known as PAL and PLA devices. Not shown is PROM with fixed AND
array (a decoder) and programmable OR array.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
104
Latches, Flip-Flops, and Registers
D
R
R
Q
Q
Q
S
C
(a) SR latch
D
C
Q
S
D
C
Q
Q
(b) D latch
D
C
Q
Q
Q
Q
(c) Master-slave D flip-flop
D
Q
FF
C
Q
(d) D flip-flop symbol
/
k
D
FF
C
Q /
k
Q
(e) k -bit register
Latches, flip-flops, and registers.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
105
Latches vs Flip-Flops
Setup Hold
time time
Setup Hold
time time
D
C
D latch: Q
D FF: Q
Operations of D latch and negative-edge-triggered D flip-flop.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
106
R/W FFs in the Same Cycle
/
k
D
Q
FF
C
Q
/
D
k
k
Computation module
(combinational logic)
Q
FF
C
Clock
/
Q
/
k
Propagation delay
Register-to-register operation with edge-triggered flip-flops.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
107
Finite-State Machines
Dime
Quarter
Reset
------- Input ------Dime
Current
state
S 00
S 10
S 25
S 00
S 10
S 20
S 35
S 00
S 20
S 30
S 35
S 00
S 25
S 35
S 35
S 00
S 30
S 35
S 35
S 00
S 35
S 35
S 35
S 00
Next state
S 00 is the initial state
S 35 is the final state
S 10
S 20
Reset
Reset
Dime
Start
Quarter
Dime
Quarter
Quarter
S 00
S 25
Reset
Reset
Dime
Quarter
Reset
Dime
Quarter
S 35
Dime
Quarter
S 30
State table and state diagram for a vending machine coin
reception unit.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
108
Register File and FIFO
Write
data
2 h k -bit registers
/
/
k
k
Write
/
address h
D
Q
FF
C
/
Write
enable
k
Write enable
/
k
Q
D
Q
FF
C
Decoder
Muxes
/
Read
data 0
k
Q
/
k
k
/
k
D
Q
FF
/
D
Q
FF
C
k
Write
data
h
/
Write
addr
/
Read
addr 0
h
/
h
/
k
Read
data 1
Q
C
k
/
/
Read
data 0 k/
Read
data 1 k/
Read
addr 1
Read enable
(b) Graphic symbol
for register file
/
k
Q
Push
Read address 0
h
Read address 1
h
/
Read
enable
/
k
Input
Empty
Full
Output /
k
Pop
/
(a) Register file with random access
(c) FIFO symbol
Register file with random access and FIFO.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
109
Row decoder
SRAM
Write enable
/
g
/
h
Data in
Address
Chip
select
.
.
.
Square or
almost square
memory matrix
Data out /
g
. . .
Output
enable
Row buffer
. . .
Address /
Row
Column mux
h Column
g bits data out
(a) SRAM block diagram
(b) SRAM read mechanism
SRAM memory is simply a large, single-port register file.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
110
Programmable Sequential Parts
A programmable sequential part contain gates and
memory elements
Programmed by cutting existing connections (fuses)
or establishing new connections (antifuses)
 Programmable array logic (PAL)
 Field-programmable gate array (FPGA)
 Both types contain macrocells and interconnects
BYU CS/ECEn 124
Chapter 3 - Digital Logic
111
From Components to Applications
Highlevel
view
Computer organization
Circuit designer
Logic designer
Computer archit ecture
Electronic components
Hardware
Computer designer
System designer
Application designer
Application domains
Software
Lowlevel
view
Subfields or views in computer system engineering.
BYU CS/ECEn 124
Chapter 3 - Digital Logic
112
High- vs Low-Level Programming
One task =
Many instructions
BYU CS/ECEn 124
temp=v[i];
v[i]=v[i+1];
v[i+1]=temp;
Compiler
Swap v[i]
and v[i+1]
High-level
language
statements
Interpreter
Very highlevel language
objectives
or tasks
More concrete, machine-dependent; error
-prone, harder to write, read, debug, maintain
One statement =
Several instructions
Assembly
language
instruction,
mnemonic
MOV.B 0x0001(SP),R14
MOV.W SP,R15
INCD.W R15
ADD.W R15,R14
MOV.B @R14,0x0000(SP)
MOV.B 0x0001(SP),R14
INC.W R14
MOV.W SP,R15
INCD.W R15
ADD.W R15,R14
MOV.B 0x0001(SP),R13
MOV.W SP,R15
INCD.W R15
ADD.W R15,R13
MOV.B @R14,0x0000(R13)
MOV.B 0x0001(SP),R15
INC.W R15
MOV.W SP,R14
INCD.W R14
ADD.W R15,R14
MOV.B @SP,0x0000(R14)
Chapter 3 - Digital Logic
Assembler
More abstract, machine-independent;
easier to write, read, debug, maintain
Mostly one
for one
Machine
language
instructions
binary (hex)
415E 0001
410F
532F
5F0E
4EE1 0000
415E 0001
531E
410F
532F
5F0E
415D 0001
410F
532F
5F0D
4EED 0000
415F 0001
531F
410E
532E
5F0E
41EE 0000
113