COE321-HO-01-Introduction

Fall 2017

Why study logic design?

n Obvious reasons
q this course is part of the COE/ELE requirements
q it is the implementation basis for all modern computing devices
n building large things from small components
n provide a model of how a computer works

n More important reasons

q the inherent parallelism in hardware is often our first exposure to
parallel computation
q it offers an interesting counterpoint to software design and is
therefore useful in furthering our understanding of computation, in
general

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 1

What will we learn in this class?

n The language of logic design

q Boolean algebra, logic minimization, state, timing, CAD tools
n The concept of state in digital systems
q analogous to variables and program counters in software systems
n How to specify/simulate/compile/realize our designs
q hardware description languages
q tools to simulate the workings of our designs
q logic compilers to synthesize the hardware blocks of our designs
q mapping onto programmable hardware
n Contrast with software design
q sequential and parallel implementations
q specify algorithm as well as computing/storage resources it will use

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 2

Applications of logic design

n Conventional computer design

q CPUs, busses, peripherals
n Networking and communications
q phones, modems, routers
n Embedded products
q in cars, toys, appliances, entertainment devices
n Scientific equipment
q testing, sensing, reporting
n The world of computing is much much bigger than just PCs!

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 3

1
COE321-HO-01-Introduction
Fall 2017

A quick history lesson

n 1850: George Boole invents Boolean algebra
q maps logical propositions to symbols
q permits manipulation of logic statements using mathematics
n 1938: Claude Shannon links Boolean algebra to switches
q his Masters’ thesis
n 1945: John von Neumann develops the first stored program computer
q its switching elements are vacuum tubes (a big advance from relays)
n 1946: ENIAC . . . The world’s first completely electronic computer
q 18,000 vacuum tubes
q several hundred multiplications per minute
n 1947: Shockley, Brittain, and Bardeen invent the transistor
q replaces vacuum tubes
q enable integration of multiple devices into one package
q gateway to modern electronics

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 4

What is logic design?

n What is design?
q given a specification of a problem, come up with a way of solving
it choosing appropriately from a collection of available
components
q while meeting some criteria for size, cost, power, beauty,
elegance, etc.
n What is logic design?
q determining the collection of digital logic components to perform
a specified control and/or data manipulation and/or
communication function and the interconnections between them
q which logic components to choose? – there are many
implementation technologies (e.g., off-the-shelf fixed-function
components, programmable devices, transistors on a chip, etc.)
q the design may need to be optimized and/or transformed to meet
design constraints

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 5

What is digital hardware?

n Collection of devices that sense and/or control wires that carry a
digital value (i.e., a physical quantity that can be interpreted
as a “0” or “1”)
q example: digital logic where voltage < 0.8v is a “0” and > 2.0v is a “1”
q example: pair of transmission wires where a “0” or “1” is distinguished
by which wire has a higher voltage (differential)
q example: orientation of magnetization signifies a “0” or a “1”
n Primitive digital hardware devices
q logic computation devices (sense and drive)
n are two wires both “ 1” - make another be “ 1” (AND)
n is at leas t one of two wires “ 1” - mak e another be “ 1” (OR)
n is a wire “ 1” - then mak e another be “ 0” (NOT)
q memory devices (store)
sense
n s tore a v alue
rec all a prev ious ly s tored v alue
AND drive
n

sense
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 6

2
COE321-HO-01-Introduction
Fall 2017

What is happening now in digital design?

n Important trends in how industry does hardware design

q larger and larger designs
q shorter and shorter time to market
q cheaper and cheaper products
n Scale
q pervasive use of computer-aided design tools over hand methods
q multiple levels of design representation
n Time
q emphasis on abstract design representations
q programmable rather than fixed function components
q automatic synthesis techniques
q importance of sound design methodologies
n Cost
q higher levels of integration
q use of simulation to debug designs
q simulate and verify before you build
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 7

COE 321: concepts/skills/abilities

n Understanding the basics of logic design (concepts)

n Understanding sound design methodologies (concepts)
n Modern specification methods (concepts)
n Familiarity with a full set of CAD tools (skills)
n Realize digital designs in an implementation technology (skills)
n Appreciation for the differences and similarities (abilities)
in hardware and software design

New ability: to accomplish the logic design task with the aid of computer-aided
design tools and map a problem description into an implementation with
programmable logic devices after validation via simulation and understanding
of the advantages/disadvantages as compared to a software implementation

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 8

Computation: abstract vs. implementation

n Up to now, computation has been a mental exercise (paper,

programs)
n This class is about physically implementing computation using
physical devices that use voltages to represent logical values
n Basic units of computation are:
q representation: "0", "1" on a wire
set of wires (e.g., for binary ints)
q assignment: x = y
q data operations: x+ y–5
q control:
sequential statements: A; B; C
conditionals: if x == 1 then y
loops: for ( i = 1 ; i == 10, i++)
procedures: A; proc(...); B;
n We will study how each of these are implemented in hardware
and composed into computational structures
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 9

3
COE321-HO-01-Introduction
Fall 2017

Switches: basic element of physical

implementations
n Implementing a simple circuit (arrow shows action if wire
changes to “1”):
A Z
close switch (if A is “1” or asserted)
and turn on light bulb (Z)

Z
A
open switch (if A is “1” or asserted)
and turn off light bulb (Z)

Z ≡ A

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 10

Switches (cont’d)

n Compose switches into more complex ones (Boolean

functions):
A B
AND
Z ≡ A and B

A
OR
Z ≡ A or B

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 11

Switching networks

n Switch settings
q determine whether or not a conducting path exists to light
the light bulb
n To build larger computations
q use a light bulb (output of the network) to set other switches
(inputs to another network).
n Connect together switching networks
q to construct larger switching networks, i.e., there is a way to
connect outputs of one network to the inputs of the next.

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 12

4
COE321-HO-01-Introduction
Fall 2017

Relay networks

n A simple way to convert between conducting paths and

switch settings is to use (electro-mechanical) relays.
n What is a relay?

conducting
path composed
of switches
closes circuit

current flowing through coil

magnetizes core and causes normally
closed (nc) contact to be pulled open
when no current flows, the spring of the contact
returns it to its normal position

What determines the switching speed of a relay network?

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 13

Transistor networks

n Relays aren't used much anymore

q some traffic light controllers are still electro-mechanical
n Modern digital systems are designed in CMOS technology
q MOS stands for Metal-Oxide on Semiconductor
q C is for complementary because there are both normally-open
and normally-closed switches
n MOS transistors act as voltage-controlled switches
q similar, though easier to work with than relays.

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 14

MOS transistors

n MOS transistors have three terminals: drain, gate, and source

q they act as switches in the following way:
if the voltage on the gate terminal is (some amount) higher/lower
than the source terminal then a conducting path will be
established between the drain and source terminals

G G

S D S D
n-channel p-channel
open when voltage at G is low open when voltage at G is high
closes when: closes when:
voltage(G) > voltage (S) + ε voltage(G) < voltage (S) – ε

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 15

5
COE321-HO-01-Introduction
Fall 2017

MOS networks

X what is the
relationship
between x and y?
3v x y

Y 0 volts 3 volts

0v 3 volts 0 volts

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 16

Two input networks

X Y

3v what is the
relationship
between x, y and z?
Z1
0v x y z1 z2

X Y 0 volts 0 volts 3 volts 3 volts

0 volts 3 volts 3 volts 0 volts
3v 3 volts 0 volts 3 volts 0 volts
Z2 3 volts 3 volts 0 volts 0 volts
NAND NOR
0v
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 17

Speed of MOS networks

n What influences the speed of CMOS networks?

q charging and discharging of voltages on wires and gates of
transistors
n Capacitors hold charge
q capacitance is at gates of transistors and wire material
n Resistors slow movement of electrons
q resistance mostly due to transistors

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 18

6
COE321-HO-01-Introduction
Fall 2017

Representation of digital designs

n Physical devices (transistors, relays)

n Switches
n Truth tables
n Boolean algebra
n Gates
scope of COE 321
n Waveforms
n Finite state behavior
n Register-transfer behavior
n Concurrent abstract specifications

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 19

Digital vs. analog

n Convenient to think of digital systems as having only

discrete, digital, input/output values
n In reality, real electronic components exhibit
continuous, analog, behavior

n Why do we make the digital abstraction anyway?

q switches operate this way
q easier to think about a small number of discrete values
n Why does it work?
q does not propagate small errors in values
q always resets to 0 or 1

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 20

Mapping from physical world to binary world

Technology State 0 State 1

Relay logic Circuit Open Circuit Closed

CMOS logic 0.0-1.0 volts 2.0-3.0 volts
Transistor transistor logic (TTL) 0.0-0.8 volts 2.0-5.0 volts
Fiber Optics Light off Light on
Dynamic RAM Discharged capacitor Charged capacitor
Nonvolatile memory (erasable) Trapped electrons No trapped electrons
Programmable ROM Fuse blown Fuse intact
Bubble memory No magnetic bubble Bubble present
Magnetic disk No flux reversal Flux reversal
Compact disc No pit Pit

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 21

7
COE321-HO-01-Introduction
Fall 2017

Combinational vs. sequential digital circuits

n A simple model of a digital system is a unit with inputs and

outputs:

inputs system outputs

n Combinational means "memory-less"

q a digital circuit is combinational if its output values
only depend on its input values

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 22

Combinational logic symbols

n Common combinational logic systems have standard symbols

called logic gates

q Buffer, NOT
A Z

q AND, NAND
A
Z easy to implement
B
with CMOS transistors
(the switches we have
q OR, NOR available and use most)
A
Z
B

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 23

Sequential logic

n Sequential systems
q exhibit behaviors (output values) that depend not only
on the current input values, but also on previous input values
n In reality, all real circuits are sequential
q because the outputs do not change instantaneously after an
input change
q why not, and why is it then sequential?
n A fundamental abstraction of digital design is to reason
(mostly) about steady-state behaviors
q look at the outputs only after sufficient time has elapsed for the
system to make its required changes and settle down

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 24

8
COE321-HO-01-Introduction
Fall 2017

Synchronous sequential digital systems

n Outputs of a combinational circuit depend only on current inputs

q after sufficient time has elapsed
n Sequential circuits have memory
q even after waiting for the transient activity to finish
n The steady-state abstraction is so useful that most designers
use a form of it when constructing sequential circuits:
q the memory of a system is represented as its state
q changes in system state are only allowed to occur at specific times
controlled by an external periodic clock
q the clock period is the time that elapses between state changes; it
must be sufficiently long so that the system reaches a steady-state
before the next state change at the end of the period

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 25

Example of combinational and sequential logic

n Combinational:
q input A, B
q wait for clock edge
q observe C A
q wait for another clock edge C
B
q observe C again: will stay the same
n Sequential: Clock
q input A, B
q wait for clock edge
q observe C
q wait for another clock edge
q observe C again: may be different

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 26

Abstractions

n Some we've seen already

q digital interpretation of analog values
q transistors as switches
q switches as logic gates
q use of a clock to realize a synchronous sequential circuit
n Some others we will see
q truth tables and Boolean algebra to represent combinational logic
q encoding of signals with more than two logical values into
binary form
q state diagrams to represent sequential logic
q hardware description languages to represent digital logic
q waveforms to represent temporal behavior

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 27

9
COE321-HO-01-Introduction
Fall 2017

An example

n Calendar subsystem: number of days in a month (to control

watch display)
q used in controlling the display of a wrist-watch LCD screen

q inputs: month, leap year flag

q outputs: number of days

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 28

Implementation in software

integer number_of_days ( month, leap_year_flag)

{
switch (month) {
case 1: return (31);
case 2: if (leap_year_flag == 1) then return (29)
else return (28);
case 3: return (31);
...
case 12: return (31);
default: return (0);
}
}

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 29

Implementation as a
combinational digital system
n Encoding:
q how many bits for each input/output?
q binary number for month month leap d28 d29 d30 d31
0000 – – – – –
q four wires for 28, 29, 30, and 31 0001 – 0 0 0 1
0010 0 1 0 0 0
n Behavior: 0010 1 0 1 0 0
0011 – 0 0 0 1
q combinational 0100 – 0 0 1 0
q truth table 0101 – 0 0 0 1
month leap 0110 – 0 0 1 0
specification 0111 – 0 0 0 1
1000 – 0 0 0 1
1001 – 0 0 1 0
1010 – 0 0 0 1
1011 – 0 0 1 0
1100 – 0 0 0 1
1101 – – – – –
111– – – – – –
d28 d29 d30d31

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 30

10
COE321-HO-01-Introduction
Fall 2017

Combinational example (cont’d)

n Truth-table to logic to switches to gates

q d28 = 1 when month=0010 and leap=0 symbol
for not
q d28 = m8'•m4'•m2•m1'•leap'

q d31 = 1 when month=0001 or month=0011 or ... month=1100

q d31 = (m8'•m4'•m2'•m1) + (m8'•m4'•m2•m1) + ...
(m8•m4•m2'•m1')
month leap d28 d29 d30 d31
q d31 = can we simplify more? 0001 – 0 0 0 1
0010 0 1 0 0 0
0010 1 0 1 0 0
symbol symbol 0011 – 0 0 0 1
for and for or 0100 – 0 0 1 0
...
1100 – 0 0 0 1
1101 – – – – –
111– – – – – –
0000 – – – – –
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 31

Combinational example (cont’d)

n d28 = m8'•m4'•m2•m1'•leap’
n d29 = m8'•m4'•m2•m1'•leap
n d30 = (m8'•m4•m2'•m1') + (m8'•m4•m2•m1') +
(m8•m4'•m2'•m1) + (m8•m4'•m2•m1)
= (m8'•m4•m1') + (m8•m4'•m1)
n d31 = (m8'•m4'•m2'•m1) + (m8'•m4'•m2•m1) +
(m8'•m4•m2'•m1) + (m8'•m4•m2•m1) +
(m8•m4'•m2'•m1') + (m8•m4'•m2•m1') +
(m8•m4•m2'•m1')

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 32

Activity

n How much can we simplify d31?

d31 is true if:month is 7 or less and odd (1, 3, 5, 7), or
month is 8 or more and even (8, 10, 12, and includes 14)

d31 is true if:m8 is 0 and m1 is 1, or m8 is 1 and m1 is 0

d31 = m8’m1 + m8m1’

n What if we started the months with 0 instead of 1?

(i.e., January is 0000 and December is 1011)

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 33

11
COE321-HO-01-Introduction
Fall 2017

Combinational example (cont’d)

n d28 = m8'•m4'•m2•m1'•leap’
n d29 = m8'•m4'•m2•m1'•leap
n d30 = (m8'•m4•m2'•m1') + (m8'•m4•m2•m1') +
(m8•m4'•m2'•m1) + (m8•m4'•m2•m1)
n d31 = (m8'•m4'•m2'•m1) + (m8'•m4'•m2•m1) +
(m8'•m4•m2'•m1) + (m8'•m4•m2•m1) +
(m8•m4'•m2'•m4') + (m8•m4'•m2•m1') +
(m8•m4•m2'•m1')

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 34

Another example

n Door combination lock:

q punch in 3 values in sequence and the door opens; if there is an
error the lock must be reset; once the door opens the lock must
be reset

q inputs: sequence of input values, reset

q outputs: door open/close
q memory: must remember combination
or always have it available as an input

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 35

Implementation in software

integer combination_lock ( ) {
integer v1, v2, v3;
integer error = 0;
static integer c[3] = 3, 4, 2;

while (!new_val u e( ));

v1 = read_value ( );
if (v1 != c[1]) then error = 1;

while (!new_val u e( ));

v2 = read_value ( );
if (v2 != c[2]) then error = 1;

while (!new_val u e( ));

v3 = read_value ( );
if (v2 != c[3]) then error = 1;

if (error == 1) then return(0); else return (1);

}

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 36

12
COE321-HO-01-Introduction
Fall 2017

Implementation as a sequential digital system

n Encoding:
q how many bits per input value?
q how many values in sequence?
q how do we know a new input value is entered?
q how do we represent the states of the system?
n Behavior: new value reset
q clock wire tells us when it’s ok
to look at inputs
(i.e., they have settled after change)
state
q sequential: sequence of values clock
must be entered
q sequential: remember if an error occurred open/closed
q finite-state specification

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 37

Sequential example (cont’d):

abstract control
n Finite-state diagram
q states: 5 states
nrepresent point in execution of machine
neach state has outputs
q transitions: 6 from state to state, 5 self transitions, 1 global
n changes of state occur when clock says it’s ok

n based on value of inputs ERR

q inputs: reset, new, results of comparisons closed

q output: open/closed C1!=value

C2!=value C3!=value
& new
& new & new
S1 S2 S3 OPEN
reset closed closed closed open
C1=value C2=value C3=value
& new & new & new

not new not new not new

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 38

Sequential example (cont’d):

data-path vs. control
n Internal structure
q data-path q control
n storage for combination n finite-state machine controller
n comparators n control for data-path

n state changes controlled by clock

new equal reset

value
C1 C2 C3
multiplexer
mux
controller
control
comparator
clock

equal open/closed
I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 39

13
COE321-HO-01-Introduction
Fall 2017

Sequential example (cont’d):

finite-state machine
n Finite-state machine
q refine state diagram to include internal structure

ERR
closed

not equal not equal

& new not equal
& new & new
S1 S2 S3 OPEN
closed closed closed
reset mux=C1 mux=C2 mux=C3 open
equal equal equal
& new & new & new

not new not new not new

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 40

Sequential example (cont’d):

finite-state machine
n Finite-state machine ERR
q generate state table (much like a truth-table) cl o se d

not equa l not equa l not equa l

& new & new & new
S1 S2 S3 OPEN
re se t cl o se d cl o se d cl o se d open
m u x=C1e q u a l m u x=C2 e q u a l m u x=C3e q u a l
& new & new & new

not new not new not new

next
reset new equal state state mux open/ closed
1 – – – S1 C1 closed
0 0 – S1 S1 C1 closed
0 1 0 S1 ERR – closed
0 1 1 S1 S2 C2 closed
0 0 – S2 S2 C2 closed
0 1 0 S2 ERR – closed
0 1 1 S2 S3 C3 closed
0 0 – S3 S3 C3 closed
0 1 0 S3 ERR – closed
0 1 1 S3 OPEN – open
0 – – OPEN OPEN – open
0 – – ERR ERR – closed

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 41

Sequential example (cont’d):

encoding
n Encode state table
q state can be: S1, S2, S3, OPEN, or ERR
n needs at least 3 bits to encode: 000, 001, 010, 011, 100
n and as many as 5: 00001, 00010, 00100, 01000, 10000
n choose 4 bits: 0001, 0010, 0100, 1000, 0000
q output mux can be: C1, C2, or C3
n needs 2 to 3 bits to encode
n choose 3 bits: 001, 010, 100
q output open/closed can be: open or closed
n needs 1 or 2 bits to encode
n choose 1 bit: 1, 0

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 42

14
COE321-HO-01-Introduction
Fall 2017

Sequential example (cont’d):

encoding
n Encode state table
q s tate c an be: S1, S2, S3, OPEN, or ERR
n choose 4 bits: 0001, 0010, 0100, 1000, 0000
q output mux c an be: C1, C2, or C3
n choose 3 bits: 001, 010, 100
q output open/c los ed c an be: open or clos ed
n choose 1 bit: 1, 0
next
reset new equal state state mux open/ closed
1 – – – 0001 001 0
0 0 – 0001 0001 001 0
0 1 0 0001 0000 – 0 good choice of encoding!
0 1 1 0001 0010 010 0
0 0 – 0010 0010 010 0 mux is identical to
0 1 0 0010 0000 – 0
last 3 bits of state
0 1 1 0010 0100 100 0
0 0 – 0100 0100 100 0
open/closed is
0 1 0 0100 0000 – 0 identical to first bit
0 1 1 0100 1000 – 1 of state
0 – – 1000 1000 – 1
0 – – 0000 0000 – 0

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 43

Activity

n Have lock always wait for 3 key presses exactly before

making a decision
q remove reset
not new not new

E2 E3 ERR
new new
closed closed closed

not equal not equal not equal

& new & new & new

S1 S2 S3 OPEN
closed closed closed
mux=C1 equal mux=C2 equal mux=C3 equal open
& new & new & new

not new not new not new

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 44

Sequential example (cont’d):

controller implementation
n Implementation of the controller
special circuit element,
new equal reset
called a register, for
remembering inputs
mux when told to by clock
control controller
clock
new equal reset
open/closed
mux
comb. logic
control
state clock

open/closed

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 45

15
COE321-HO-01-Introduction
Fall 2017

Design hierarchy

system

data-path control

code state combinational

registers multiplexer comparator registers logic

register logic

switching
networks

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 46

Summary

n That was what the entire course is about

q converting solutions to problems into combinational and
sequential networks effectively organizing the design
hierarchically
q doing so with a modern set of design tools that lets us handle
large designs effectively
q taking advantage of optimization opportunities

n Now let’s do it again

I - Introduction © C opyright 2004, Gaetano Borriello and Randy H. Katz 47

16