ECE 545Digital System Design with VHDL Lecture 3

Sequential Logic Review and Algorithmic State Machines 9/9/08

Outline
Sequential Logic Building Blocks
Latches, Flip-Flops

Sequential Logic Circuits

Registers, Shift Registers, Counters Memory (RAM, ROM) Simple Finite State Machines (Mealy, Moore)

Complex Digital System Design with ASMs

Examples

Textbook References
Sequential Logic Review
Stephen Brown and Zvonko Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd or 3rd Edition
Chapters 7 and 8

OR your undergraduate digital logic textbook (chapters on sequential logic and state machines)

Algorithmic State Machines

Stephen Brown and Zvonko Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd or 3rd Edition
Chapter 8.10 Algorithmic State Machine (ASM) Charts Chapter 10.2.1 A Bit-Counting Circuit Chapter 10.2.2 ASM Chart Implied Timing Information Chapter 10.2.6 Sort Operation (handouts distributed in class)
3

Sequential Logic Building Blocks

some slides modified from: Brown and Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd Edition S. Dandamudi, Fundamentals of Computer Organization and Design

Introduction to Sequential Logic

Output depends on current as well as past inputs
Depends on the history Have memory property

Sequential circuit consists of

Combinational circuit Feedback circuit

Past input is encoded into a set of state variables

Uses feedback (to feed the state variables)
Simple feedback Uses flip flops

Introduction (contd)
Main components of a typical synchronous sequential circuit (synchronous = uses a clock to keep circuits in lock step)

INPUT COMBINATIONAL LOGIC PRESENT STATE S(t) STATE-HOLDING ELEMENTS (i.e. FLIP-FLOPS)

OUTPUT

NEXT STATE S(t+1)

CLOCK
6

State-Holding Memory Elements

Latch versus Flip Flop
Latches are level-sensitive: whenever clock is high, latch is transparent Flip-flops are edge-sensitive: data passes through (i.e. data is sampled) only on a rising (or falling) edge of the clock Latches cheaper to implement than flip-flops Flip-flops are easier to design with than latches

In this course, primarily use D flip-flops

D Latch vs. D Flip-Flop

D Q CLK

D CLK Q
Latch transparent when clock is high

D
D Q CLK

CLK Q
Samples D on rising edge of clock
8

D Flip-Flop (positive edge triggered)

1

D
P3

1
2

P1 5

0
Q

Clock

0 1
3 P2 6

D
4 D P4 Clock Q

D
(a) Circuit (b) Graphical symbol

NAND : one input 0, output always 1; all inputs 1 except A, output is A

9

D Flip-Flop (positive edge triggered)

D
1 P3

1
2

P1

D 0
5

D
Q

Clock

1 1
3

DP2

D
D Q

D
4 D P4 Clock Q

D
(a) Circuit (b) Graphical symbol

NAND : one input 0, output always 1; all inputs 1 except A, output is A

10

D Flip-Flop with Asynchronous Preset and Clear

Preset

Bubble on the symbol means active-low

Q

Clock Q

When preset = 0, preset Q to 1 When preset = 1, do nothing When clear = 0, clear Q to 0 When clear = 1, do nothing

D Clear

(a) Circuit
Preset D Q Q Clear

Preset and Clear also known as Set and Reset respectively In this circuit, preset and clear are asynchronous
Q changes immediately when preset or clear are active, regardless of clock
11

(b) Graphical symbol

D Flip-Flop with Synchronous Clear

D
Clear D Clock D Q Q Q Q

CLK CLEAR

Q
(asynchronous clear)

Q
(synchronous clear)

Asynchronous active-low clear: Q immediately clears to 0 Synchronous active-low clear: Q clears to 0 on rising-edge of clock
12

Other Types of Flip-Flops

D Flip-Flop
D Q CLK D 0 1 Q(t+1) 0 1

Set-Reset (SR) Flip-Flop

S Q CLK R S 0 0 1 1 R 0 1 0 1 Q(t+1) Q(t) 0 1 not allowed

Toggle (T) Flip-Flop

T Q CLK T 0 1 Q(t+1) Q(t) Q(t)

JK Flip-Flop
J Q CLK K J 0 0 1 1 K 0 1 0 1 Q(t+1) Q(t) 0 1 Q(t)

13

Sequential Logic Circuits

some slides modified from: Brown and Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd Edition S. Dandamudi, Fundamentals of Computer Organization and Design

14

Register
D(3)
D Q CLK

Q(3)

D(2)

D Q CLK

Q(2)

D(1) D(0)

D Q CLK D Q CLK

Q(1) Q(0)

In typical nomenclature, a register is a name for a collection of flip-flops used to hold a bus (i.e. std_logic_vector)
15

Shift Register
In Clock D Q Q Q1 D Q Q Q2 D Q Q Q3 D Q Q Q4 Out

(a) Circuit
In 1 0 1 1 1 0 0 0 Q1 0 1 0 1 1 1 0 0 Q2 0 0 1 0 1 1 1 0 Q3 0 0 0 1 0 1 1 1 Q4 = Out 0 0 0 0 1 0 1 1

t0 t1 t2 t3 t4 t5 t6 t7

(b) A sample sequence

16

Parallel Access Shift Register

Parallel output Q3 Q2 Q1 Q0

Q Q

Q Q

Q Q

Q Q

clock serial_in parallel_in 4 shift/load SHIFT REGISTER 4 output

Serial input

Shift/Load

Parallel input

Clock

17

Synchronous Up Counter
Enable D0
0 1

Q Q

Q0

enable
0

D1

Q Q

Q1

load D0 D1 D2

carry Q0 Q1 Q2 Q3

D2

Q Q

Q2

D3

clock
0

D3

Q Q

Q3

Output carry Load Clock

Enable (synchronous): when high enables the counter, when low counter holds its value Load (synchronous) : when load = 1, load the desired value into the counter Output carry: indicates when the counter rolls over D3 downto D0, Q3 downto Q0 is how to interpret MSB to LSB
18

Memories

some slides modified from: Brown and Vranesic, Fundamentals of Digital Logic with VHDL Design, 2nd Edition S. Dandamudi, Fundamentals of Computer Organization and Design

19

Random Access Memory (RAM)

More efficient than registers for storing large amounts of data Can read and write to RAM Addressable memory Can be synchronous (with clock) or asynchronous (no clock) SRAM dimensions are:
(number of words) x (bits per word) SRAM 2m x n-bit RAM

data in (n)

data out (n)

address (m) RAM write read

Address is m bits, data is n bits

Example: address is 5 bits, data is 8 bits

32 x 8-bit RAM Data_in and address are stable Assert write signal (then de-assert) Address is stable Assert read signal Data_out is valid

Write Read

20

Random Access Memory (RAM)

Data inputs Write dn 1 d n 2 d0

Sel0 Sel1 m-to-2m decoder a0 a1 Address am 1 Sel2

Sel2m 1

Read Data outputs qn 1 qn 2 q0

21

Read Only Memory (ROM)

Similar to RAM except read only Addressable memory Can be synchronous (with clock) or asynchronous (no clock)

data in (n)

data out (n)

address (m) ROM

read

22

Read-Only Memory (ROM)

Sel0 Sel1 m-to-2m decoder a0 a1 Address am 1 Sel2 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1

Sel2m 1

0/1

0/1

0/1

Read Data dn 1 dn 2 d0

23

Simple Finite State Machines

24

Finite State Machines (FSMs)

Any Circuit with Memory Is a Finite State Machine
Even computers can be viewed as huge FSMs

Design of FSMs Involves

Defining states Defining transitions between states Optimization / minimization

Above Approach Is Practical for Simple FSMs Only

25

Mealy vs. Moore State Machines

Finite State Machines (FSM) are of two types: Moore Machines
Next State = Function(Input, Present State) Output = Function(Present State)

Mealy Machines
Next State = Function(Input, Present State) Output = Function(Input, Present State)

26

Moore FSM
Output Is a Function of a Present State Only
Inputs Next State Function
(comb. logic)

Next State clock reset Present State Register

Present State

Output Function
(comb. logic)

Outputs

27

Mealy FSM
Output Is a Function of a Present State and Inputs
Inputs Next State Function
(comb. logic)

Next State clock reset Present State Register

Present State

Output Function
(comb. logic)

Outputs

28

Moore Machine

transition condition 1 state 1 / output 1 state 2 / output 2 transition condition 2

29

Mealy Machine

transition condition 1 / output 1 state 2 transition condition 2 / output 2

state 1

30

Moore vs. Mealy FSM (1)

Moore and Mealy FSMs can be functionally equivalent
Equivalent Mealy FSM can be derived from Moore FSM and vice versa

Mealy FSM Has Richer Description and Usually Requires Smaller Number of States
Smaller circuit area

31

Moore vs. Mealy FSM (2)

Mealy FSM computes outputs as soon as inputs change
Mealy FSM responds one clock cycle sooner than equivalent Moore FSM

Moore FSM Has no combinational path between inputs and outputs

Moore FSM is more likely to have a shorter critical path Moore outputs synchronized with clock; Mealy outputs may not be (may have race conditions, timing issues, etc.)
32

Moore FSM - Example 1

Moore FSM that Recognizes Sequence 10
0 S0 / 0 reset Meaning of states: S0: No elements of the sequence observed 1 1 S1 / 0 0 1 S2 / 1

0 S1: 1 observed S2: 10 observed

33

Mealy FSM - Example 1

Mealy FSM that Recognizes Sequence 10
0/0 S0 reset Meaning of states: S0: No elements of the sequence observed 0/1 S1: 1 observed 1/0 S1 1/0

34

Moore & Mealy FSMs Example 1

clock 0 input S0 Moore S0 Mealy S1 S0 S0 S0 S1 S2 S0 S0 1 0 0 0

35

FSM Limitations
Simple finite state machines (those expressed using state diagrams and state tables) good only for simple designs
Many inputs and many outputs make it awkward to draw state machines Often only one input affects the next change of state Most outputs remain the same from state to state

Instead use algorithmic state machines (ASM)

36

Complex Digital System Design with Algorithmic State Machines

37

Complex Digital System Design

external inputs control signals CONTROLLER status signals DATAPATH data input

external outputs

Some refer to this as the register-transfer level (RTL) design method

data output

Complex digital systems can be decomposed into a datapath and controller Datapath manipulates and processes data
To perform arithmetic, logic, shifting, and other data-processing tasks These operations are implemented with ALUs, registers, multiplexers, adders, comparators, etc. Controller provides signal to activate various processing in the datapath
Example: enable signals for registers Example: control signals for muxes

Controller determines the enabling and sequencing of datapath operations

Controller also determines the sequence the operations are performed

38

Inputs and Outputs

external inputs control signals CONTROLLER status signals DATAPATH data input

external outputs
Datapath inputs and outputs
External data input
Example: data to be processed Example: result data Example: when an adder has overflowed

data output

External data output Status signals to the controller (to indicate what is occuring in the datapath)

Controller inputs and outputs

External inputs
Example: reset signal, mode select Example: done flag to outside world Example: mux select, enable signals

External outputs Control signals to the datapath

39

Controller
Controller can be programmable or non-programmable Programmable
Has a program counter which point to next instruction Instructions are held in a RAM or ROM externally Microprocessor is an example of programmable controller

Non-Programmable
Once designed, implements the same functionality Another term is a hardwired state machine or hardwired instructions We will be focusing primarily on the non-programmable type in this course
40

Algorithmic State Machine (ASM)

Complex digital systems can be represented by algorithmic state machines Simple finite state machines (expressed using state diagrams and state tables) good only for simple designs Algorithmic State Machines (ASM) are
flow-chart type diagrams to represent finite state machines suitable for a larger number of inputs and outputs compared to simple FSMs
41

Elements used in ASM charts

State name Output signals or actions (Moore type)

0 (False)

Condition expression

1 (True)

(a) State box

(b) Decision box

Conditional outputs or actions (Mealy type)

(c) Conditional output box

42

State Box
State box represents a state. Equivalent to a node in a state diagram or a row in a state table. Contains register transfer actions or output signals Moore-type outputs are listed inside of the box. It is customary to write only the name of the signal that has to be asserted in the given state, e.g., z instead of z=1. Also, it might be useful to write an action to be taken, e.g., count = count + 1, and only later translate it to asserting a control signal that causes a given action to take place.
State name Output signals or actions (Moore type)

43

Decision Box
Decision box indicates that a given condition is to be tested and the exit path is to be chosen accordingly The condition expression consists of one or more inputs to the FSM.

0 (False)

Condition expression

1 (True)

44

Conditional Output Box

Conditional output box Denotes output signals that are of the Mealy type. The condition that determines whether such outputs are generated is specified in the decision box.

Conditional outputs or actions (Mealy type)

45

ASMs representing simple FSMs

Algorithmic state machines can model both Mealy and Moore simple finite state machines Three examples follow

46

Moore FSM Example 1: State diagram

Reset w = 1 w = 0 Az=0 w = 0 w = 0 w = 1 Bz= 0

Cz = 1

w = 1

47

ASM Chart for Moore FSM Example 1

Reset A

w 1 B

w 1

C z

48

Mealy FSM Example 2: State diagram

Reset w = 1z= 0 w = 0z= 0 A w = 0z= 0 B w = 1z= 1

49

ASM Chart for Mealy FSM Example 2

Reset

w 1

B z

50

Control Unit Example: Arbiter (1)

reset

r1 r2 r3

g1

Arbiter

g2 g3

clock
51

Control Unit Example: Arbiter (2)

Reset Idle 0xx 1xx 000

gnt1 g1 = 1 1xx gnt2 g2 = 1 x1x gnt3 g3 = 1 xx1

52

x0x

01x

xx0

001

Control Unit Example: Arbiter (3)

Reset Idle r1 r1 r 1r 2 r 3

gnt1 g1 = 1 r2 r1 gnt2 g2 = 1 r3 r2 gnt3 g3 = 1 r3

53

r 1r 2

r 1r 2 r 3

ASM Chart for Control Unit - Example 3

Reset

Idle

r1 0

1 gnt1 g1 1 gnt2 g2 1 r2 0 1 r1 0

r2 0

0 r3

1 gnt3 g3 1 r3 0

54

Complex Digital System Design: ASM Design Steps

55

Complex Digital Design: ASM Design Steps

Given a specification, to design a complex digital system using ASMs, the following steps are involved:
1. 2. 3. 4. 5. Translate specification into pseudocode. Translate pseudocode into a high-level ASM. Also called pseudocode ASM, since it uses pseudocode instead of actual signal names. Design a datapath block diagram based on high-level ASM. Also called an execution unit. (Some references decompose block diagram into a datapath block diagram and controller block diagram.) Draw top-level interface diagram. This diagram connects the datapath with the controller to show all inputs, outputs, and internal connections of the entire digital system. Design detailed controller ASM based on high-level ASM. Detailed means using the exact signal names, not pseudocode representations. Datapath: represented by a datapath block diagram Controller: represented by a detailed controller ASM Top-Level: represented by top-level interface diagram

After this process you have three results:

From this it is easy to translate into VHDL

56

Examples
We will do examples in class:
Bit-counting circuit Sorting circuit

57