Transcript 4 +

Why study logic design?

Obvious reasons


this course is part of the EE/CS/CE requirements
it is the implementation basis for all modern computing devices



building large things from small components
provide a model of how a computer works
More important reasons


the inherent parallelism in hardware is often our first exposure to
parallel computation
it offers an interesting counterpoint to software design and is
therefore useful in furthering our understanding of computation
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
1
What will we learn in this class?

The language of logic design


The concept of state in digital systems


analogous to variables and program counters in software systems
How to specify/simulate/compile/realize our designs





Boolean algebra, logic minimization, state, timing, CAD tools
hardware description languages
tools to simulate the workings of our designs
logic compilers to synthesize the hardware blocks of our designs
mapping onto programmable hardware
Contrast with software design


sequential and parallel implementations
specify algorithm as well as computing/storage resources it will use
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
2
Applications of logic design

Conventional computer design


Networking and communications


in cars, toys, appliances, entertainment devices
Scientific equipment


phones, modems, routers
Embedded products


CPUs, busses, peripherals
testing, sensing, reporting
The world of computing is much much bigger than just PCs!
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
3
A quick history lesson

1850: George Boole invents Boolean algebra



1938: Claude Shannon links Boolean algebra to switches


its switching elements are vacuum tubes (a big advance from relays)
1946: ENIAC . . . The world’s first completely electronic computer



his Masters’ thesis
1945: John von Neumann develops the first stored program computer


maps logical propositions to symbols
permits manipulation of logic statements using mathematics
18,000 vacuum tubes
several hundred multiplications per minute
1947: Shockley, Brittain, and Bardeen invent the transistor



replaces vacuum tubes
enable integration of multiple devices into one package
gateway to modern electronics
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
4
What is logic design?

What is design?



given a specification of a problem, come up with a way of solving
it choosing appropriately from a collection of available
components
while meeting some criteria for size, cost, power, beauty,
elegance, etc.
What is logic design?



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
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.)
the design may need to be optimized and/or transformed to meet
design constraints
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
5
What is digital hardware?

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”)




example: digital logic where voltage < 0.8v is a “0” and > 2.0v is a “1”
example: pair of transmission wires where a “0” or “1” is distinguished
by which wire has a higher voltage (differential)
example: orientation of magnetization signifies a “0” or a “1”
Primitive digital hardware devices

logic computation devices (sense and drive)




are two wires both “1” - make another be “1” (AND)
is at least one of two wires “1” - make another be “1” (OR)
is a wire “1” - then make another be “0” (NOT)
memory devices (store)


store a value
recall a previously stored value
sense
AND
drive
sense
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
6
What is happening now in digital design?

Important trends in how industry does hardware design




Scale



pervasive use of computer-aided design tools over hand methods
multiple levels of design representation
Time





larger and larger designs
shorter and shorter time to market
cheaper and cheaper products
emphasis on abstract design representations
programmable rather than fixed function components
automatic synthesis techniques
importance of sound design methodologies
Cost



higher levels of integration
use of simulation to debug designs
simulate and verify before you build
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
7
You must learn: concepts/skills/abilities






Understanding the basics of logic design (concepts)
Understanding sound design methodologies (concepts)
Modern specification methods (concepts)
Familiarity with a full set of CAD tools (skills)
Realize digital designs in an implementation technology (skills)
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
8
Digital Systems
Digital vs. Analog Waveforms
+5
+5
1
0
1
V
V
Time
–5
–5
Digital:
only assumes discrete values
I - Introduction
Time
Analog:
values vary over a broad range
continuously
© Copyright 2004, Gaetano Borriello and Randy H. Katz
9
Switches (cont’d)

Compose switches into more complex ones (Boolean
functions):
AND
B
A
Z  A and B
A
OR
Z  A or B
B
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
10
Relay networks


A simple way to convert between conducting paths and
switch settings is to use (electro-mechanical) relays.
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
11
Transistor networks

Relays aren't used much anymore


Modern digital systems are designed in CMOS technology



some traffic light controllers are still electro-mechanical
MOS stands for Metal-Oxide on Semiconductor
C is for complementary because there are both normally-open
and normally-closed switches
MOS transistors act as voltage-controlled switches

similar, though easier to work with than relays.
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
12
MOS transistors

MOS transistors have three terminals: drain, gate, and source

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
S
G
D
n-channel
open when voltage at G is low
closes when:
voltage(G) > voltage (S) + 
I - Introduction
S
D
p-channel
closed when voltage at G is low
opens when:
voltage(G) < voltage (S) – 
© Copyright 2004, Gaetano Borriello and Randy H. Katz
13
MOS networks
X
what is the
relationship
between x and y?
3v
x
Y
0v
I - Introduction
y
0 volts
3 volts
3 volts
0 volts
© Copyright 2004, Gaetano Borriello and Randy H. Katz
14
Two input networks
X
Y
3v
Z1
0v
what is the
relationship
between x, y and z?
x
X
Y
3v
Z2
y
z1
z2
0 volts 0 volts
3 volts
3 volts
0 volts 3 volts
3 volts
0 volts
3 volts 0 volts
3 volts
0 volts
3 volts 3 volts
0 volts
0 volts
NAND
NOR
0v
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
15
Representation of digital designs









Physical devices (transistors, relays)
Switches
Truth tables
Boolean algebra
Gates
Waveforms
Finite state behavior
Register-transfer behavior
Concurrent abstract specifications
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
scope of this course
16
Digital vs. analog



Convenient to think of digital systems as having only
discrete, digital, input/output values
In reality, real electronic components exhibit
continuous, analog, behavior
Why do we make the digital abstraction anyway?



switches operate this way
easier to think about a small number of discrete values
Why does it work?


does not propagate small errors in values
always resets to 0 or 1
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
17
Mapping from physical world to binary world
Technology
State 0
Relay logic
CMOS logic
Transistor transistor logic (TTL)
Fiber Optics
Dynamic RAM
Nonvolatile memory (erasable)
Programmable ROM
Bubble memory
Magnetic disk
Compact disc
I - Introduction
Circuit Open
0.0-1.0 volts
0.0-0.8 volts
Light off
Discharged capacitor
Trapped electrons
Fuse blown
No magnetic bubble
No flux reversal
No pit
© Copyright 2004, Gaetano Borriello and Randy H. Katz
State 1
Circuit Closed
2.0-3.0 volts
2.0-5.0 volts
Light on
Charged capacitor
No trapped electrons
Fuse intact
Bubble present
Flux reversal
Pit
18
Combinational vs. sequential digital circuits

A simple model of a digital system is a unit with inputs and
outputs:
inputs

system
outputs
Combinational means "memory-less"

a digital circuit is combinational if its output values
only depend on its input values
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
19
Combinational logic symbols

Common combinational logic systems have standard symbols
called logic gates

Buffer, NOT
A

AND, NAND
A
B

Z
easy to implement
with CMOS transistors
(the switches we have
available and use most)
Z
OR, NOR
A
B
I - Introduction
Z
© Copyright 2004, Gaetano Borriello and Randy H. Katz
20
Sequential logic

Sequential systems


In reality, all real circuits are sequential



exhibit behaviors (output values) that depend not only
on the current input values, but also on previous input values
because the outputs do not change instantaneously after an
input change
why not, and why is it then sequential?
A fundamental abstraction of digital design is to reason
(mostly) about steady-state behaviors

look at the outputs only after sufficient time has elapsed for the
system to make its required changes and settle down
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
21
Synchronous sequential digital systems

Outputs of a combinational circuit depend only on current inputs


Sequential circuits have memory


after sufficient time has elapsed
even after waiting for the transient activity to finish
The steady-state abstraction is so useful that most designers
use a form of it when constructing sequential circuits:



the memory of a system is represented as its state
changes in system state are only allowed to occur at specific times
controlled by an external periodic clock
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
22
Example of combinational and sequential logic

Combinational:






input A, B
wait for clock edge
observe C
wait for another clock edge
observe C again: will stay the same
A
C
B
Sequential:





Clock
input A, B
wait for clock edge
observe C
wait for another clock edge
observe C again: may be different
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
23
An example

Calendar subsystem: number of days in a month (to control
watch display)

used in controlling the display of a wrist-watch LCD screen

inputs: month, leap year flag
outputs: number of days

I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
24
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
25
Implementation as a
combinational digital system

Encoding:




how many bits for each input/output?
month
binary number for month
0000
0001
four wires for 28, 29, 30, and 31
Behavior:


combinational
truth table
specification
month
leap
d28 d29 d30 d31
I - Introduction
0010
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
111–
© Copyright 2004, Gaetano Borriello and Randy H. Katz
leap
–
–
0
1
–
–
–
–
–
–
–
–
–
–
–
–
d28
–
0
1
0
0
0
0
0
0
0
0
0
0
0
–
–
d29
–
0
0
1
0
0
0
0
0
0
0
0
0
0
–
–
d30
–
0
0
0
0
1
0
1
0
0
1
0
1
0
–
–
d31
–
1
0
0
1
0
1
0
1
1
0
1
0
1
–
–
26
Combinational example (cont’d)

Truth-table to logic to switches to gates





symbol
for not
d28 = 1 when month=0010 and leap=0
d28 = m8'•m4'•m2•m1'•leap'
d31 = 1 when month=0001 or month=0011 or ... month=1100
d31 = (m8'•m4'•m2'•m1) + (m8'•m4'•m2•m1) + ... (m8•m4•m2'•m1')
d31 = can we simplify more?
symbol
for and
I - Introduction
symbol
for or
month
0001
0010
0010
0011
0100
...
1100
1101
111–
0000
leap
–
0
1
–
–
d28
0
1
0
0
0
d29
0
0
1
0
0
d30
0
0
0
0
1
d31
1
0
0
1
0
–
–
–
–
0
–
–
–
0
–
–
–
0
–
–
–
1
–
–
–
© Copyright 2004, Gaetano Borriello and Randy H. Katz
27
Combinational example (cont’d)




d28 = m8'•m4'•m2•m1'•leap’
d29 = m8'•m4'•m2•m1'•leap
d30 = (m8'•m4•m2'•m1') + (m8'•m4•m2•m1') +
(m8•m4'•m2'•m1) + (m8•m4'•m2•m1)
= (m8'•m4•m1') + (m8•m4'•m1)
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
28
Activity

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’

What if we started the months with 0 instead of 1?
(i.e., January is 0000 and December is 1011)
More complex expression (0, 2, 4, 6, 7, 9, 11):
d31 = m8’m4’m2’m1’ + m8’m4’m2m1’ + m8’m4m2’m1’ + m8’m4m2m1’
+ m8’m4m2m1 + m8m4’m2’m1 + m8m4’m2m1
d31 = m8’m1’ + m8’m4m2 + m8m1 (includes 13 and 15)
d31 = (d28 + d29 + d30)’
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
29
Combinational example (cont’d)




d28 = m8'•m4'•m2•m1'•leap’
d29 = m8'•m4'•m2•m1'•leap
d30 = (m8'•m4•m2'•m1') + (m8'•m4•m2•m1') +
(m8•m4'•m2'•m1) + (m8•m4'•m2•m1)
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
© Copyright 2004, Gaetano Borriello and Randy H. Katz
30
Design hierarchy
system
control
data-path
code
registers multiplexer
comparator
register
state
registers
combinational
logic
logic
switching
networks
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
31
Summary

That was what the entire course is about



converting solutions to problems into combinational and
sequential networks effectively organizing the design
hierarchically
doing so with a modern set of design tools that lets us handle
large designs effectively
taking advantage of optimization opportunities
I - Introduction
© Copyright 2004, Gaetano Borriello and Randy H. Katz
32
Chapter Overview

Contemporary Logic Design
Arithmetic Circuits
Binary Number Representation
Sign & Magnitude, Ones Complement, Twos Complement

Binary Addition
Full Adder Revisted

ALU Design

BCD Circuits

Combinational Multiplier Circuit

Design Case Study: 8 Bit Multiplier
I - Introduction
© R.H. Katz Transparency No. 5-33
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Sign and Magnitude Representation
-7
-6
1111
+0
1110
-5
+1
0000
0001
1101
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-3
1011
0100
+4
1 100 = - 4
-2
1010
0101
1001
-1
+5
-
0110
1000
-0
0111
+6
+7
High order bit is sign: 0 = positive (or zero), 1 = negative
Three low order bits is the magnitude: 0 (000) thru 7 (111)
n-1
Number range for n bits = +/-2
-1
Representations for 0
I - Introduction
© R.H. Katz Transparency No. 5-34
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Sign and Magnitude
Cumbersome addition/subtraction
Must compare magnitudes to determine sign of result
Ones Complement
N is positive number, then N is its negative 1's complement
n
N = (2 - 1) - N
2 4 = 10000
-1
= 00001
Example: 1's complement of 7
1111
-7
Shortcut method:
=
0111
1000
= -7 in 1's comp.
simply compute bit wise complement
I - Introduction
0111 -> 1000
© R.H. Katz Transparency No. 5-35
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Ones Complement
-0
-1
-2
1111
1110
+0
0000
+1
0001
1101
0010
+2
+
-3
1100
0011
+3
0 100 = + 4
-4
1011
0100
+4
1 011 = - 4
-5
1010
0101
1001
-6
+5
-
0110
1000
-7
0111
+6
+7
Subtraction implemented by addition & 1's complement
Still two representations of 0 This causes some problems
I - Introduction
Some complexities in addition
© R.H. Katz Transparency No. 5-36
Contemporary Logic Design
Arithmetic Circuits
Number Representations
Twos Complement
-1
-2
-3
like 1's comp
except shifted
one position
clockwise
1111
1110
+0
0000
+1
0001
1101
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-5
1011
0100
+4
1 100 = - 4
-6
1010
0101
1001
-7
+5
-
0110
1000
-8
0111
+6
+7
Only one representation for 0
One more negative number than
positive number
I - Introduction
© R.H. Katz Transparency No. 5-37
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Twos Complement Numbers
n
N* = 2 - N
Example: Twos complement of 7
4
2 = 10000
sub 7 = 0111
1001 = representation of -7
Example: Twos complement of -7
4
2 = 10000
sub -7 = 1001
0111 = representation of 7
Shortcut method:
Twos complement = bitwise complement + 1
0111 -> 1000 + 1 -> 1001 (representation of -7)
1001 -> 0110 + 1 -> 0111 (representation of 7)
I - Introduction
© R.H. Katz Transparency No. 5-38
Number Representations
Addition and Subtraction of Numbers
Contemporary Logic Design
Arithmetic Circuits
Sign and Magnitude
result sign bit is the
same as the operands'
sign
when signs differ,
operation is subtract,
sign of result depends
on sign of number with
the larger magnitude
4
0100
-4
1100
+3
0011
+ (-3)
1011
7
0111
-7
1111
4
0100
-4
1100
-3
1011
+3
0011
1
0001
-1
1001
I - Introduction
© R.H. Katz Transparency No. 5-39
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Addition and Subtraction of Numbers
Ones Complement Calculations
4
0100
-4
1011
+3
0011
+ (-3)
1100
7
0111
-7
10111
End around carry
1
1000
4
0100
-4
1011
-3
1100
+3
0011
1
10000
-1
1110
End around carry
1
0001
I - Introduction
© R.H. Katz Transparency No. 5-40
Number Systems
Addition and Subtraction of Binary Numbers
Contemporary Logic Design
Arithmetic Circuits
Twos Complement Calculations
4
0100
-4
1100
+3
0011
+ (-3)
1101
7
0111
-7
11001
4
0100
-4
1100
-3
1101
+3
0011
1
10001
-1
1111
If carry-in to sign =
carry-out then ignore
carry
if carry-in differs from
carry-out then overflow
Simpler addition scheme makes twos complement the most common
choice for integer number systems within digital systems
I - Introduction
© R.H. Katz Transparency No. 5-41
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Overflow Conditions
Add two positive numbers to get a negative number
or two negative numbers to get a positive number
-1
-2
0001
0010
1100
0100
1010
0101
1001
-7
0110
1000
-8
0111
+6
+7
5 + 3 = -8
-3
+2
0011
1011
-6
-2
+1
0000
1101
-4
-5
1111
1110
-3
-1
+0
+3
-4
1111
+1
0000
1110
0001
1101
0010
1100
-5
1011
+4
+5
+0
1010
-6
0110
1000
-8
0011
+3
0100
+4
0101
1001
-7
+2
0111
+5
+6
+7
-7 - 2 = +7
I - Introduction
© R.H. Katz Transparency No. 5-42
Contemporary Logic Design
Arithmetic Circuits
Number Systems
Overflow Conditions
5
0111
0101
-7
1000
1001
3
0011
-2
1110
-8
1000
7
10111
Overflow
Overflow
5
0000
0101
-3
1111
1101
2
0010
-5
1011
7
0111
-8
11000
No overflow
No overflow
Overflow when carry in to sign does not equal carry out
I - Introduction
© R.H. Katz Transparency No. 5-43