CEG 360/560 - EE 451/651 Section III Slides
Download
Report
Transcript CEG 360/560 - EE 451/651 Section III Slides
Section III:
Complex system design
CEG 360/560; EE 451/651
Digital System Design
Dr. Travis Doom, Associate Professor
Department of Computer Science and Engineering
Wright State University
Outline
Dealing with Complexity
Data unit (Datapath) design
– Registers
– RTL language
– Datapath Construction
Control unit (Controller) design
– ASM Charts
Implementation issues
– PLDs
– ROM
– VLSI Design
CEG 360/560 - EE 451/651 Section III - 2
Dealing with Complexity
Practical synchronous sequential circuits are too complex to design at
the flip-flop level.
– A simple 8-bit CPU capable of storing only four values (in four GPRs) has
at least 4 x 8 = 32 1-bit state devices!
– If the CPU had only 8 inputs it would still require a 232 by 28 truth table to
represent the device. Each of these billion or so entries would have to
contain a 32-bit next state. Storing 240 32-bit entries would require 4 TB!
K (kilo)
M (mega)
G (giga)
T (tera)
210
220
230
240
1024
1048576
1.07 x 109
1.10 x 1012
– Simplification would require a 40-variable K-map!
How do we manage complex design?
CEG 360/560 - EE 451/651 Section III - 3
Complex System Design
Practical sequential designs, like combinational designs, require a
hierarchical approach
– Use well defined building blocks
Complex blocks made of simpler blocks (hierarchy)
Examples: Registers, counters
Associate a high-level of behavior with those blocks (abstraction)
– Design methodologies based on abstractions can more easily encompass
complexity
– Common function blocks: registers and counters
ORDER a sequence of high-level behaviors that (when executed in the
proper order) solves the overall problem
– Like computer programming!
CEG 360/560 - EE 451/651 Section III - 4
Decomposing a Design: Control and Data
Control Signals
Control
Inputs
Control Unit
Status Signals
Datapath
Data
Outputs
Control
Outputs
Data
Inputs
Complex designs are generally broken down into to high-level
abstractions.
– The datapath is home to one or more datapath components that provide
higher-level functionality (viewable at the register transfer level)
– The control unit controls the sequence in which the datapath functions are
performed in order to perform the system task
CEG 360/560 - EE 451/651 Section III - 5
Outline
Dealing with Complexity
Data unit (Datapath) design
– Registers
– RTL language
– Datapath Construction
Control unit (Controller) design
– ASM Charts
Implementation issues
– PLDs
– ROM
– VLSI Design
CEG 360/560 - EE 451/651 Section III - 6
Datapath components
Gates and flip-flops are good building blocks for simple designs
We need more sophisticated building blocks for complex systems
Register-transfer level (RTL) components (aka Datapath components)
include medium scale devices such as:
–
–
–
–
–
–
Registers
Counters
ALUs
Multiplexers
Comparators
etc
CEG 360/560 - EE 451/651 Section III - 7
MSI Quad/Hex Registers
74LS175
1D
Q
D
CLR
2D
Q
D
CLR
3D
/CLR
All four flip-flops use the same clock!
Q
Q
D
CLR
CLK
Q
Q
D
CLR
4D
Q
Q
1Q
/1Q
2Q
/2Q
74LS175
CLK
CLR
1D
2D
3D
4D
1Q
1Q
2Q
2Q
3Q
3Q
4Q
4Q
3Q
74LS174
CLK
/3Q
4Q
/4Q
CLR
1D
1Q
2D
2Q
3D
3Q
4D
4Q
5D
5Q
6D
6Q
CEG 360/560 - EE 451/651 Section III - 8
Octal Register with Parallel Load Enable
1b-mux
CLK
Load
1D
2D
3D
4D
5D
6D
7D
8D
D
1Q
2Q
3Q
4Q
5Q
6Q
7Q
8Q
1D
Q
1Q
/Load
CLK
Why don’t we gate the clock?
CEG 360/560 - EE 451/651 Section III - 9
Shift Registers
Multi-bit register that moves data “sideways” left/right ( 1 bit/clock )
– Shift Left (or Shift Down) is towards MSB
Q3 Q2 Q1
Q0
0
1
1
1
Q3 Q2 Q1
LSI
1
1
Q0
1 LSI
– Shift Right (or Shift Up) is towards LSB
RSI
Q3 Q2 Q1
Q0
0
1
1
1
Q3 Q2 Q1
RSI
0
Q0
1
1
Often used to rearrange bits or Multiply/Divide by 2
CEG 360/560 - EE 451/651 Section III - 10
Bi-directional Universal Shift Registers
74x194
11
1
Modes:
Hold
Load
Shift Right
Shift Left
10
9
7
6
5
4
3
2
Block symbol
CLK
CLR
S1
S0
LIN
D
C
B
A
RIN
R
QD
QC
QB
QA
L
(SI)
(LSB)
12
13
14
15
(MSB)
> SRG n
S1
S0
LSI
D0
Q0
D1
Q1
Dn
Qn
RSI
(SO)
Quad Bi-directional Universal (4-bit) PIPO
Function
Hold
Shift right/up
Shift left/down
Load
Mode
S1 S0
0
0
0
1
1
0
1
1
Next state
QA* QB* QC*
QA QB QC
RIN QA QB
QB QC QD
A
B
C
QD*
QD
QC
LIN
D
CEG 360/560 - EE 451/651 Section III - 11
Universal SR Schematic
CLK
(11)
/CLR
(1)
LIN
(7)
RIGHT
74x194
S1 S0
LEFT
SL
10
HO
00
(6)
D
(12)
LD
D
QD
Q
11
CLK
SR
01
CLR
(10)
S1
10
(9)
S0
00
D
(3)
A
(15)
QA
11
CLK
(2)
RIN
Q
01
CLR
CEG 360/560 - EE 451/651 Section III - 12
Octal Tri-state Register/Latch
74LS374
/OE
CLK
1D
2D
8D
D
Q
1Q
Q
2Q
D
D
Q
8Q
74LS374
CLK
OE
1D
2D
3D
4D
5D
6D
7D
8D
1Q
2Q
3Q
4Q
5Q
6Q
7Q
8Q
74LS373
C
OE
1D
2D
3D
4D
5D
6D
7D
8D
1Q
2Q
3Q
4Q
5Q
6Q
7Q
8Q
CEG 360/560 - EE 451/651 Section III - 13
Shift Register Applications
State Registers
– Shift registers are often used as the state register in a sequential device.
Usually, the next state is determined by shifting right and inserting a
primary input or output into the next position
– Very effective for finite memory machines
Serial Interconnection of Systems
– keep interconnection cost low with serial interconnect
Bit Serial Operations
– Bit serial operations can be performed quickly through device iteration
– Iteration (a purely combinational approach) is expensive (in terms of # of
transistors, chip area, power, etc).
– A sequential approach allows the reuse of combinational functional units
throughout the multi-cycle operation
CEG 360/560 - EE 451/651 Section III - 14
Shift Register Applications
Transmitter
CLOCK
Control
Control
/SYNC
Circuits
Parallel
Data
from
A-to-D
converter
Parallelto-serial
converter
DIGITAL
TELEPHONY
SDATA
Receiver
Circuits
Serial-toparallel
converter
Parallel
Data to
D-to-A
converter
CLOCK - 1 bit per clock tick = 2.048 MHz
/SYNC - synchronization of start of “frame”
SDATA - serial data stream
CEG 360/560 - EE 451/651 Section III - 15
Shift Register Applications
x7
x6
x0
x5
CTL
CLK
7
6
5
y7
y6
y5
7
6
5
...
Sequential Implementation of:
Z[7..0] = X[7..0] + Y[7..0]
0
>
y0
...
0
>
D
Cin A B
FA
Cout
S
Q
CLK
CLR
7
6
5
z7
z6
z5
...
0
>
CLEAR_C
V
...
z0
CEG 360/560 - EE 451/651 Section III - 16
Counters
Counters are registers with extra
functions
Clocked sequential circuit with
single-cycle state diagram
– Modulo-m counter = divide-by-m
counter
000
001
S1
010
011
Sm
S2
100
101
110
S3
111
Most Common:
n-bit binary counter, where m = 2n n
flip-flops, counts 0 … 2n-1
CEG 360/560 - EE 451/651 Section III - 17
Counting
Common output codes for mod-8 and decimal counters
State
0
1
2
3
4
5
6
7
8
9
Binary
000
001
010
011
100
101
110
111
BCD
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Gray
000
001
011
010
110
111
101
100
Excess-3
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
Ring
Twisted-tail
00000001
0000
00000010
0001
00000100
0011
00001000
0111
00010000
1111
00100000
1110
01000000
1100
10000000
1000
CEG 360/560 - EE 451/651 Section III - 18
Asynchronous/Ripple Counter
Q
CLK
Q0
1 bit
divide-by-2
T
Q
Q
Q1
T
2 bit
divide-by-4
Uses
Minimal
Logic!
Q
Q
Q2
T
3 bit
divide-by-8
Q
Tpd = n x Tpd,tff
Setup = Tsetup,tff
Q
T
Q3
4 bit
divide-by-16
Q
CEG 360/560 - EE 451/651 Section III - 19
Synchronous Counters
All clock inputs connected to common CLK signal
– So all flip-flop outputs change simultaneously tCQ after CLK
Synchronous Counters are/have
– Faster
– More Complex Logic (more “expensive”)
– Most Frequently Used Type of Counter
Two types of synchronous counters
– Serial
– Parallel
Easy to combine iteratively to build bigger counters
– Combined counters have serial aspects. If the devices are parallel, then the
overall device is “mixed mode”.
CEG 360/560 - EE 451/651 Section III - 20
Synchronous Serial Counter
CNTEN
Flip-flops enabled
when all lower flipflops = 1.
Enable propagates
serially — limits speed
Requires
(n-1) D t < TCLK
All outputs change
simultaneously tCQ after
CLK
EN
CLK
Q
Q0
Q
Q1
Q
Q2
Q
Q3
>T
Dt
EN
>T
Dt
EN
>T
Tpd = Tpd,tff
Tsetup = (n-1)Dt + Tsetup,tff
Dt
Equation?
Delay?
EN
>T
CEG 360/560 - EE 451/651 Section III - 21
Synchronous Parallel Counter
CNTEN
EN
CLK
>T
Single-level enable
logic per flip-flop
Fastest and most
complex type of
counter
Requires D t < TCLK
All outputs change
simultaneously tCQ after
CLK
Tpd = Tpd,tff
Tsetup = Tpd,bigestAND + Tsetup,Tff
EN
Q
Q0
Q
Q1
Q
Q2
Q
Q3
>T
EN
>T
EN
Equation?
Delay?
>T
CEG 360/560 - EE 451/651 Section III - 22
74163 4-bit Synchronous Parallel Counter
74X163
Common Clock
Synchronous Clear
Synchronous Load
Count Enable = ENP ENT
Load Data Inputs
(74161 is the same, but with an
asynchronous clear)
>CLK
CLR
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
LSB
MSB
RCO = Ripple Carry Out,
when Count = 1111 and ENT
=1
CEG 360/560 - EE 451/651 Section III - 23
74163 State Table
Inputs
Current State
Next State
/CLR /LD ENT ENP
QD QC QB QA
QD* QC* QB* QA*
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
X
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
X
X
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
X
X
X
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Clear
Load
Hold
Hold
Count
.
.
.
X
X
X
X
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
X
X
X
X
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
X
X
X
X
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
X
X
X
X
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
D
QD
QD
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
C
QC
QC
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
B
QB
QB
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
A
QA
QA
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
CEG 360/560 - EE 451/651 Section III - 24
74169 Up/Down Counter
74X169
>CLK
UP/DN
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
UP/DN = 1 = up
RCO = 15
UP/DN = 0 = down RCO = 0
up
down
up
Ex: 0,1,2, 1,0,15,14, 15,0,1,2
RCO
RCO
CEG 360/560 - EE 451/651 Section III - 25
Application - Free Running Modulo-16 Counter
74X163
>CLK
CLOCK
+5 V
R
CLR
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
Q0
Q1
Q2
Q3
CEG 360/560 - EE 451/651 Section III - 26
Modulo-11 Counter [5,6, …, 15, 5, 6, ...]
+5 V
When Count=15 Load 5 (0101)
74X163
CLOCK
Any Modulus 2 16 possible
>CLK
CLR
LD
ENP
ENT
A 1
B 0
C 1
D 0
QA
QB
QC
QD
RCO
Q0
Q1
Q2
Q3
CNT15
RCO
/CNT15
CEG 360/560 - EE 451/651 Section III - 27
Modulo-11 Counter [0,1,2, …, 10, 0, 1, ...]
+5 V
When Count=10 Clear
74X163
CLOCK
>CLK
CLR
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
Decode Count 1x1x (10…15)
Q3 Q1
Q0
Q1
Q2
Q3
CEG 360/560 - EE 451/651 Section III - 28
Cascaded 74163s for 8-bit Counter
Up to Modulo-256
74X163
CLOCK
/RESET
/LOAD
CNTEN
D0
D1
D2
D3
>CLK
CLR
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
Q0
Q1
Q2
Q3
74X163
>CLK
D4
D5
D6
D7
CLR
LD
ENP
ENT
A
B
C
D
QA
QB
QC
QD
RCO
Q4
Q5
Q6
Q7
RCO8
CEG 360/560 - EE 451/651 Section III - 29
4-bit, 8-state Johnson Counter
+5 V
Also known as
R
– twisted-ring counter
– Moebius counter
74X194
CLOCK
/RESET
2n states with n flip-flops
– NOT self-correcting
CLK
CLR
S1
S0
LIN
D
C
B
A
RIN
Wired as a
shift-left
shift register
QD
QC
Q0
Q1
QB
QA
Q2
Q3
74X04
CEG 360/560 - EE 451/651 Section III - 30
Design Decomposition
A digital system is a sequential circuit with specified behavior.
– A microprocessor is a digital system.
Specifying large digital systems with state tables may be exceptionally
difficult, due to the number of states involved.
– As in computer programming, most digital systems are designed using a
modular, hierarchical approach.
– The system is partitioned into modular subsystems.
Each subsystem performs a well defined function with specified interface.
– Interconnection the various subsystems though data and control signals
results in a digital system.
CEG 360/560 - EE 451/651 Section III - 31
Design Decomposition
Most digital systems are partitioned into two top-level modules:
– Data Unit (or Datapath): performs data-processing operations.
– Control Unit: determines the sequence of these operations.
Datapaths are sequential systems.
– the system state is defined by the contents of the registers.
– the functionality is the set of defined operations that can be performed on
the contents of the registers.
– Elementary operations are usually, but not always, performed in parallel on
a string of bits in one clock tick.
A microoperation is an elementary operation performed on data stored in
the datapath. They fall into four general categories:
– Transfer microoperations: transfer binary data from one register (or data
input/memory) to another.
– Arithmetic microoperations: perform arithmetic on data in registers.
– Logic microoperations: perform bit manipulations on data in registers.
CEG 360/560 - EE 451/651 Section III - 32
– Shift microoperations: shift data in registers.
Register-Transfer Level Design
An approach to specify, analyze, and design systems too complex to use
the state-table based approaches commonly utilized in “simple” designs.
The Register-Transfer Level (RTL) approach is characterized by:
– A digital system is viewed as divided into a data subsystem and a control
subsystem.
– The state of the data subsystem consists of the contents of the registers.
– The function of the system is performed as a sequence of register transfers.
– A register transfer is a transformation performed on the datum while the
datum is transferred from one register to another.
– The sequence of register transfers is controlled by the control subsystem.
The operation of the device can be designed as a sequence of register
transfers can be designed using state diagrams, ASM charts, etc.
– Each transfer must correspond to a sequence of microoperations.
– The control unit implements the RTL design through microoperations.
CEG 360/560 - EE 451/651 Section III - 33
RTL Languages (1)
The notation for register transfers are sufficiently complete to describe
any digital system at the register-transfer level.
– known as register-transfer languages.
Registers are denoted by uppercase letters (sometimes followed by
numbers) that indicate the function of the register
– e.g. R0, R1, AR, PC, MAR, et al.
– The individual bits can be denoted using parenthesis and bit numbers or
labels
e.g. R0(0), R0(7:0), PC(L), PC(H)
Data transfer is denoted in symbolic form by the means of the
replacement operator .
– e.g. R2 R1
CEG 360/560 - EE 451/651 Section III - 34
RTL Languages (2)
Normally we want a given transfer to occur not for every clock pulse,
but only for specific values of the control signals.
– RTL conditional statements:
e.g. If (K1 = 1) Then (R2 R1)
– Control function notation (Colon, :)
e.g. K1: R2 R1
All RTL statements occur in response to a clock tick. A comma is used
to separate two or more register transfers that are executed at the same
time. A semi-colon is used for an instruction with different control
– e.g. Brake: R2 R1, R4 R3; not(Brake): R1 R2
CEG 360/560 - EE 451/651 Section III - 35
RTL Languages (3)
Register to Memory Transfers are denoted using square brackets
surrounding the memory address.
– e.g. DR M[AR] (Read operation)
– e.g. M[AR] SR (Write operation)
CEG 360/560 - EE 451/651 Section III - 36
RTL Languages (4)
Examples of Arithmetic Microoperations
Examples of Logic Microoperations
CEG 360/560 - EE 451/651 Section III - 37
Designing a datapath
Design a device with two 8-bit inputs A and B, one 1-bit input START,
one 8-bit output C, and one 1-bit output DONE. The device begins idle
(with output DONE = 0). When START is asserted (for one clock tick)
the unsigned binary inputs A and B are and held constant until the
device asserts “DONE”. The device must calculate the approximate
length of the hypotenuse of a right triangle with sides A and B. When
the final answer is available on output C, the device will assert DONE
for one clock tick. If the answer cannot be computed, assert ERR.
>
START
8
8
C
DONE
A
C
B
ERR
8
C = sqrt (A2 + B2)
A
B
CEG 360/560 - EE 451/651 Section III - 38
Designing a datapath
Euler formula for Square Root Approximation:
– Let x = max (|a|, |b|)
– Let y = min (|a|, |b|)
– Sqrt (a^2 + b^2) ~= max (x,(0.875x+0.5y))
What sort of functions do you need to process the data?
CEG 360/560 - EE 451/651 Section III - 39
Designing a datapath
SRA Circuit Model
Let x = max (a, b) and y = min (a, b)
– Sqrt (a^2 + b^2) ~= max (x,(0.875x+0.5y))
Control unit
…
Rx max (A, B)
Ry min (A, B)
Ry Ry >> 1 # shift right 1; *0.5
Rt Rx >> 3 # shift right 3 (1/8th)
Rt Rx – Rt # x – 1/8x = x*0.875
Rt Ry + Rt
Rc max (Rx, Rt)
C Rc
…
Datapath
Registers: c, x, y, t
Functions: min, max, +, -, shift
CEG 360/560 - EE 451/651 Section III - 40
Designing a datapath
8RcIN
Control unit
RcLD
…
Rx max (A, B)
Ry min (A, B)
Ry Ry >> 1
Rt Rx >> 3
Rt Rx – Rt
Rt Ry + Rt
Rc max (Rx, Rt)
C Rc
…
>
RG8
8RxIN
RxLD
>
RG8
8
Rx
8
MXC1
>
C
B
1
MUX
8
0
MXC2
MUX
8
Ry
Ry
0
MXA1
Rt
Rx
8
1
8
>
RG8
8
Rt
8
8RtIN
RtLD
RG8
Rx
8
0
RyLD
8
Rc
A
8RyIN
Rt
Ry
8
Rx
8
1
8
0
MUX
MXS
8
1
MUX
8
8
8
SR1,3
Min
Max
8
ALU+-
ALU8
8
Overflow
MXF
8
8
A
B
0
2
1
8b-Shifter
8
8
2
3
MUX
8
RcIN, RxIN, RyIN, RtIN
C
CEG 360/560 - EE 451/651 Section III - 41
8
Designing a datapath
Datapath
Control unit
…
Rx max (A, B)
Ry min (A, B)
Ry Ry >> 1
Rt Rx >> 3
Rt Rx – Rt
Rt Ry + Rt
Rc max (Rx, Rt)
C Rc
…
Data
Inputs
8
8
4
2
Control
Signals
2
2
2
A
B
C
8
Data
Outputs
LDRx, LDRy, LDRt, LDRc
Status
Signals
MXC1, MXC2
MXA1, ALU+-
Overflow
MXS, SR1,3
MXF
CEG 360/560 - EE 451/651 Section III - 42
Outline
Dealing with Complexity
Data unit (Datapath) design
– Registers
– RTL language
– Datapath Construction
Control unit (Controller) design
– ASM Charts
Implementation issues
– PLDs
– ROM
– VLSI Design
CEG 360/560 - EE 451/651 Section III - 43
Interaction between Data and Control Units
Control Signals
Control
Inputs
Control Unit
Status Signals
Datapath
Data
Outputs
Control
Outputs
Data
Inputs
Control Signals - signals that activate data-processing functions.
– To activate a sequence of such operations, the control unit sends the proper
sequence of control signals to the datapath.
Status Signals - signals that describe aspects of the state of the datapath.
– The control unit uses these signals in determining the specific sequence of
operations to be performed.
Other Signals - allow the control unit and datapath to interact with other
parts of the system, such as memory and input-output logic.
CEG 360/560 - EE 451/651 Section III - 44
The Control Unit
The control unit generates the signals for sequencing the operations in
the datapath
– A sequential circuit with states that dictate the control signals for the system
– Using status conditions and control inputs, the sequential control unit
determines the next state in which additional microoperations are activated.
Hardwired Control
– The control unit is implemented to provide a particular digital function
Microprogrammed Control
– LATER!
CEG 360/560 - EE 451/651 Section III - 45
Control Unit Design
Control unit
Start
PS
IDLE
S1
S2
S3
S4
S5
S6
S7
S8
ERR
Next State
StartOverflow =
00
01
IDLE
IDLE
S2
S2
S3
S3
S4
S4
S5
S5
S6
S6
S7
ERR
S8
S8
IDLE
IDLE
IDLE
IDLE
LDx …
10
S1
S2
S3
S4
S5
S6
S7
S8
IDLE
IDLE
11
S1
S2
S3
S4
S5
S6
ERR
s8
IDLE
IDLE
RTL
Rx max (A, B)
Ry min (A, B)
Ry Ry >> 1
Rt Rx >> 3
Rt Rx – Rt
Rt Ry + Rt
Rc max (Rx, Rt)
C Rc; Done 1
ERR 1
Done
Overflow
CEG 360/560 - EE 451/651 Section III - 46
ASM for Control
Control unit
…
Rx max (A, B)
Ry min (A, B)
Ry Ry >> 1
Rt Rx >> 3
Rt Rx – Rt
Rt Ry + Rt
Rc max (Rx, Rt)
C Rc; DONE 1
…
Rx max (A,B)
LDRx, MXC1=0,
MC2=0, MXF=1
Ry max (A,B)
LDRy, MXC1=0
MC2=0, MXF=0
Ry Ry >> 1
LDRy, MXS=0,
SR1,3 = 0
Rt Rx >> 3
LDRt, MXS=1,
SR1,3 = 1
.
.
.
.
.
.
CEG 360/560 - EE 451/651 Section III - 47
Algorithmic State Machines
Algorithmic State Machine (ASM) Chart
– Special flowchart used to define digital hardware algorithms
– Describes a sequence of events
– Determines the actions which occur in the states
in response to the clock pulse
in response to changes in the inputs
ASM Charts contain three basic elements:
– State boxes
Rectangles, labeled with the state name and assignment, containing a register
operation and/or the names of Moore outputs asserted in that state.
– Decision boxes
Diamonds containing a conditional input expression and exits 1 and 0.
– Conditional output boxes
Ovals containing Mealy outputs asserted for the conditions leading to the box.
CEG 360/560 - EE 451/651 Section III - 48
ASM elements
State box
state entry path
state name state code
Moore output list
Decision box
condition false
exit path
condition true
exit path
state exit path
0
condition
1
Conditional (Mealy) output box
from decision-box
exit path
OR
0
condition
1
conditional output list
exit path
CEG 360/560 - EE 451/651 Section III - 49
ASM Timing
Each state box has a corresponding “ASM Block” that includes all decision and
conditional output boxes reached from that state
– Each ASM Block has exactly one state box, all paths leaving the ASM Block lead
directly to a different state box.
The current state box represents the current state.
The current inputs decide a path through the decision boxes.
– Unlike state diagrams, ambiguity is easily avoided in ASM charts.
– Conditional outputs along the path occur immediately in response to changes in the
inputs values.
The next state box is not entered until a clock tick occurs.
– The Moore outputs in the state box and any conditional (Mealy) outputs in the new
ASM Block are asserted immediately.
ASM boxes may also include Register Transfer directives!
– Any changes (conditional or otherwise) to a sequential device wait until the next
positive clock edge.
CEG 360/560 - EE 451/651 Section III - 50
ASM Example: 4-bit binary counter
STATE = Q1 Q0
STATE = Q1 Q0
00
A
00
A
Z=0
01
B
01
B
Z0
Z=1
-or-
10
C
Z1
D
Z=2
11
Z1,Z0
10
C
D
11
Z=3
CEG 360/560 - EE 451/651 Section III - 51
ASM Example: 4-bit counter with enable
STATE = Q1 Q0
A
00
C
Z=0
0
Z=2
0
EN
1
B
01
EN
1
EN
1
D
Z=1
0
10
11
Z=3
0
EN
1
CEG 360/560 - EE 451/651 Section III - 52
ASM Example: Modulo-4 counter (Mealy)
STATE = QD QC QB QA (one hot)
A
0
0001
EN
1
0
B
0010
C
0100
D
1000
EN
1
MAX
Mealy output
CEG 360/560 - EE 451/651 Section III - 53
ASM Example: 1’s Counter
Count # of 1’s on X & Y inputs
output Z if count = multiple of 4 ( 0, 4, 8 ... )
If
(XY)
Else if ( X+Y )
Else
2 1’s
1 1’s
0 1’s
( Inc by 2 )
( Inc by 1 )
( No Inc )
CEG 360/560 - EE 451/651 Section III - 54
ASM chart for 1’s Counter
STATE = Q1 Q2
S0
00
S1
01
S2
X +Y
0
S3
11
Z
XY
0
10
1
1
XY
0
X +Y
0
1
1
XY
0
X +Y
0
1
1
XY
0
X +Y
0
1
1
CEG 360/560 - EE 451/651 Section III - 55
Convert ASM chart to Transition List
Needs an extra step to find transition expressions
Trace all possible paths, from any state to all destination states
Transition expression to any given next state (= one line of the transition
list) is product (AND) of all conditions along path:
( condition) if 1 branch taken
– (condition)’ if 0 branch taken
CEG 360/560 - EE 451/651 Section III - 56
Example: 1’s Counter
S0
00
PS
00
00
00
Z
XY
0
(XY)’(X+Y)’
X +Y
0
1
1
INPUT
(XY)
(XY)’(X+Y)
(XY)’(X+Y)’
NS
10
01
00
(XY)
(XY)’(X+Y)
CEG 360/560 - EE 451/651 Section III - 57
Example: 1’s Counter
Q1Q0
00
00
00
01
01
01
10
10
10
11
11
11
INPUT
(XY)
(XY)’(X+Y)
(XY)’(X+Y)’
(XY)
(XY)’(X+Y)
(XY)’(X+Y)’
(XY)
(XY)’(X+Y)
(XY)’(X+Y)’
(XY)
(XY)’(X+Y)
(XY)’(X+Y)’
Q1*Q0*
10
01
00
11
10
01
00
11
10
01
00
11
Q1* =
Q1’Q0’(XY) +
Q1’Q0(XY) +
Q1’Q0(XY)’(X+Y) +
Q1Q0’(XY)’(X+Y) +
Q1Q0’(XY)’(X+Y)’ +
Q1Q0(XY)’(X+Y)’
Q2* =
Q1’Q0’(XY)’(X+Y) +
Q1’Q0(XY) +
Q1’Q0(XY)’(X+Y)’ +
Q1Q0’(XY)’(X+Y) +
Q1Q0(XY) +
Q1Q0(XY)’(X+Y)’ +
CEG 360/560 - EE 451/651 Section III - 58
Outline
Dealing with Complexity
Data unit (Datapath) design
– Registers
– RTL language
– Datapath Construction
Control unit (Controller) design
– ASM Charts
Implementation issues
– PLDs
– ROM
– VLSI Design
CEG 360/560 - EE 451/651 Section III - 59
Programmable Logic Definitions
Digital integrated circuit (MSI, LSI, VLSI)
– manufactured as a standard off-the-shelf component
– containing “regular” array of logic gates and flip-flops
– whose logic functions are determined by the application design engineer
and implemented locally
Many types of programmable logic
–
–
–
–
sometimes generically called PLDs (Programmable Logic Devices)
PAL or PLD
PROM
FPGA
output
Combinational
input
PLD
CEG 360/560 - EE 451/651 Section III - 60
Programmable Logic Definitions
PLA
– Programmable Logic Array
– first PLDs
– simple programmable
AND/OR array
– programmed by “blowing
fuses” by hand or by mask
CEG 360/560 - EE 451/651 Section III - 61
Programmable Logic
PAL
– Programmable Array Logic
– similar to a PLA, but the ORarray is fixed
– most commonly used PLD
– may include input/output flipflops
GAL
– Generic Array Logic
– can be configured to emulate
the AND/OR, flip-flop, and
output structure of a variety of
combinational and sequential
PAL devices
CEG 360/560 - EE 451/651 Section III - 62
Read-Only Memory (ROM)
A combinational circuit with n inputs and b outputs:
Address n
inputs
A(n-1, ... , 0)
2n x b
ROM
b
Data
outputs
D(b-1, ... , 0)
Programmable values determined by user
Nonvolatile contents retained without power
Uniform (Random) Access delay is uniform for all addresses
CEG 360/560 - EE 451/651 Section III - 63
Read-Only Memory (ROM)
Two views:
– ROM stores 2n words of b bits each, or
– ROM stores an n-input, b-output truth table
Example:
n=2
A1 A0
0
0
0
1
1
0
1
1
b=4
D3 D2
0
1
1
1
0
0
1
0
D1 D0
0
1
1
1
0
1
0
0
Stores 4 4-bit words, or
stores 4 functions of 2
input variables
CEG 360/560 - EE 451/651 Section III - 64
Using ROMs for Combinational Logic
A 3-input, 4-output combinational logic function:
A2
0
0
0
0
1
1
1
1
Inputs
A1 A0
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
D3
1
1
1
0
0
0
0
1
Outputs
D2 D1
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
D0
0
1
1
1
1
0
0
0
8 4 ROM
I0
I1
POL
A0
A1
A2
D0
D1
D2
D3
Y0
Y1
Y2
Y3
Function: 2-to-4 Decoder with Polarity Control
A2 = Polarity
(0 = active Low, 1= active High)
A1, A0 = I1, I0
(2-bit input )
D3...D0 = Y3...Y0
(4-bit decoded output)
CEG 360/560 - EE 451/651 Section III - 65
Internal Structure of 44 Diode ROM
+5 V
R3
A1
A0
2 to 4
Decoder
R2
R1
R0
/w0
0101
/w1
1111
/w2
0001
/w3
1000
Bit Lines
Diode
1 of n Word Lines
1
D0
D1
D2
No Diode
Why use diodes?
Why not replace them with wires?
0
D3
CEG 360/560 - EE 451/651 Section III - 66
Types Of ROMs (1)
Bit Line
Mask ROM
–
–
–
–
–
Connections made by the semiconductor vendor
Expensive setup cost
Several weeks for delivery
High volume only
Bipolar or MOS technology
Word Line
PROM
– Programmable ROM
– Connections made by equipment manufacturer
– Vaporize (blow) fusible links with PROM programmer using high
voltage/current pulses
– Bipolar technology
– One-time programmable
CEG 360/560 - EE 451/651 Section III - 67
Internal Structure of Transistor ROM
Replace diodes with MOS transistors
Change decoder to active-high outputs
+5 V
R3
R2
R1
R0
w3
Transistor
1000
1
/D3
No transistor
/D2
/D1
/D0
0
CEG 360/560 - EE 451/651 Section III - 68
EPROM and EEPROM Structure
VD
D
Floating gate
Nonfloating gate
Active-high
word lines
Active-low
bit lines
CEG 360/560 - EE 451/651 Section III - 69
Types of ROMs (2)
EPROM
– Erasable Programmable ROM
– Charge trapped on extra “floating gate” of MOS
transistors
– Exposure to UV light removes charge
Bit Line
Word Line
10-20 minutes
Quartz Lid = expensive package
– Limited number of erasures (10-100)
EEPROM (E2ROM)
–
–
–
–
Electrically Erasable ROM
Floating gates charged/discharged electrically
Not RAM! (relatively slow charge/discharge)
limited number of charge/discharge cycles (10,000)
CEG 360/560 - EE 451/651 Section III - 70
Types of ROMs (3)
Flash Memory
–
–
–
–
Electronically erasable in blocks
100,000 erase cycles
Simpler and denser than EEPROM
Often used for firmware
CEG 360/560 - EE 451/651 Section III - 71
ROM Type Summary
Type
Technology
Read Cycle
Write Cycle Comments
20-200 ns
4 weeks
Write once; low power
Mask ROM Bipolar
<100 ns
4 weeks
Write once; high power; low density
PROM
Bipolar
<100 ns
5 minutes
Write once; high power; no mask
charge
EPROM
NMOS, CMOS
25-200 ns
5 minutes
Reusable; low power; no mask charge
EEPROM
NMOS
50-200 ns
10 ms/byte
10,000 writes/location limit
FLASH
CMOS
25-200 ns
10 ms/block 100,000 erase cycles
Mask ROM NMOS, CMOS
CEG 360/560 - EE 451/651 Section III - 72
Consider a 64 x 1 ROM
+5 V
This Decoder needs 64 6-input gates!
/w0
A5
A0
6-to-64
Decoder
/w1
/w63
64 x 1
Diode Array
D0
How can we make it more square?
Very tall, narrow chip (BAD)
Even worse for larger chips!
CEG 360/560 - EE 451/651 Section III - 73
64 x 1 ROM with 2-Dimensional Decoding
+5 V
/w0
A5
A3
A2
A0
3 to 8
Decoder
/w1
8x8
Diode Array
/w7
0
7
8 to 1 mux
Decoder and mux = 8 3-input gates + 8 4-input gates
D0
Almost square chip!
CEG 360/560 - EE 451/651 Section III - 74
64K x 8 ROM with 2-D Decoding
9
A
512
9 to 512
Decoder
512
128
128
7
A
512
128
128
512
1024
Array
128
128
to 1
Mux
128
to 1
Mux
D0
D1
Is this a square chip?
512
128
128
to 1
Mux
D7
2-D Decoding / Coincident selection
64k x 8 = 216 * 23 = 219
square root (219) ~= 29
CEG 360/560 - EE 451/651 Section III - 75
Internal 2n x b ROM Control Structure
A0
A1
Am-1
Am
Am+1
Row
decoder
Power
on
Storage
array
Power
on
Power
on
Column
multiplexer
An-1
/CS
/OE
Db-1 Db-2
D0
CEG 360/560 - EE 451/651 Section III - 76
Programmable Logic
Advantages
–
–
–
–
–
–
Design flexibility
Better design automation
Higher density, fewer packages (compared to SSI-MSI)
Less expensive
Lower power
Higher performance
Programming Technologies
– Interconnections usually made by pass transistors controlled by memory
bits of some type:
– Antifuse - permanent connections made electrically
– EPROM - charged floating gate, UV erasable
– EEPROM - charged floating gate, electrically erasable
– Flash Memory - charged floating gate, electrically erasable
– Programmed using CAD - Hardware Description Languages
CEG 360/560 - EE 451/651 Section III - 77
Modern (VLSI) Design
The VLSI chips that are used in most modern designs come in three
varieties:
– Custom Approach: VLSI chips, or some of their parts, are designed by
hand.
Full Custom Vs. Standard Cell - Using standard cell designs (same height,
variable width) and routing channels simplifies the design process
Highest Density, Highest Manufacturing Cost
– Semicustom Approach: The VLSI chips employ gate arrays and technology
mapping.
Gate array: a partially prefabricated IC that incorporates a large number of
identical gates (usually 3-input NAND or NOR gates) that are laid out in a
regular two-dimensional array.
Technology mapping: The process of designing a logic function as a network
of available devices.
Lower Density (10-25% more gates than an equivalent custom design).
Inexpensive: Requires only metal deposition (define interconnections), economy
of scale.
CEG 360/560 - EE 451/651 Section III - 78
Modern (VLSI) Design
The VLSI chips that are used in most modern designs come in three
varieties:
– VLSI PLDs
Field Programmable Gate Arrays (FPGAs)
A VLSI modules that can be programmed to implement a digital system
consisting of tens of thousands of gates.
LSI PLDs implement two-level combinational and sequential networks,
FPGAs allow the realization of multilevel networks and complex systems on a
single chip!
Highly reprogrammable!
Low cost
May produce slower network
May require a larger silicon area
CEG 360/560 - EE 451/651 Section III - 79