Synchronous sequential Circuits

GIVES A DETAILED PRESENTATION OF SYNCHRONOUS SEQUENTIAL
CIRCUITS (FINITE STATE MACHINES). IT EXPLAINS THE BEHAVIOR OF THESE
CIRCUITS AND DEVELOPS PRACTICAL DESIGN TECHNIQUES FOR BOTH
MANUAL AND AUTOMATED DESIGN. DEALS WITH A GENERAL CLASS OF
CIRCUITS IN WHICH THE OUTPUTS DEPEND ON THE PAST BEHAVIOR OF THE
CIRCUIT, AS WELL AS ON THE PRESENT VALUES OF INPUTS. THEY ARE
CALLED SEQUENTIAL CIRCUITS. IN MOST CASES A CLOCK SIGNAL IS USED TO
CONTROL THE OPERATION OF A SEQUENTIAL CIRCUIT; SUCH A CIRCUIT IS
CALLED A SYNCHRONOUS SEQUENTIAL CIRCUIT.

1. MATRUSRI ENGINEERING COLLEGE
DEPARTMENT OF ELECTRONICS AND COMMUNICATION
ENGINEERING
SUBJECT NAME: DIGITAL ELECTONICS
FACULTY NAME: Mrs. B. Indira Priyadarshini
MATRUSRI
ENGINEERING COLLEGE

2. INTRODUCTION:
GIVES A DETAILED PRESENTATION OF SYNCHRONOUS SEQUENTIAL
CIRCUITS (FINITE STATE MACHINES). IT EXPLAINS THE BEHAVIOR OF THESE
CIRCUITS AND DEVELOPS PRACTICAL DESIGN TECHNIQUES FOR BOTH
MANUAL AND AUTOMATED DESIGN. DEALS WITH A GENERAL CLASS OF
CIRCUITS IN WHICH THE OUTPUTS DEPEND ON THE PAST BEHAVIOR OF THE
CIRCUIT, AS WELL AS ON THE PRESENT VALUES OF INPUTS. THEY ARE
CALLED SEQUENTIAL CIRCUITS. IN MOST CASES A CLOCK SIGNAL IS USED TO
CONTROL THE OPERATION OF A SEQUENTIAL CIRCUIT; SUCH A CIRCUIT IS
CALLED A SYNCHRONOUS SEQUENTIAL CIRCUIT.





UNIT-V
OUTCOMES:
After successful completion of this Unit students should be able to
Analyze, design and implement sequential logic circuits in terms of state
machines.
Solve ASM for simple application
MATRUSRI
ENGINEERING COLLEGE

3. CONTENTS:

BASIC DESIGN STEPS
FSM REPRESENTATION USING MOORE STATE MODELS
FSM REPRESENTATION USING MEALY STATE MODELS







OUTCOMES:

Students will be able to design Mealy and Moore FSM models for completely
and incompletely specified circuits.






MODULE-I: Synchronous Sequential
Circuits
MATRUSRI
ENGINEERING COLLEGE

4. Synchronous Sequential Circuits
MATRUSRI
ENGINEERING COLLEGE
A circuit whose output(s) depend on past behaviour, and present inputs
•Clock is used => synchronous sequential circuits
•No clock => asynchronous sequence circuits
Also called Finite state machine (FSM)
State elements in synchronous sequential circuits are edge triggered
•To ensure state changes only once in a single cycle.

5. Synchronous Sequential Circuits
MATRUSRI
ENGINEERING COLLEGE
Synchronous sequential circuits are of two types:
•Moore output depends only n state
•Mealy: output depends on state and inputs

6. Basic Design Steps
MATRUSRI
ENGINEERING COLLEGE
The procedure for designing synchronous sequential circuits can be
summarized by a list of recommended steps.
1. From the word description and specifications of the desired operation,
derive a state diagram for the circuit.
2. Reduce the number of states if necessary.
3. Assign binary values to the states.
4. Obtain the binary-coded state table.
5. Choose the type of flip-flops to be used.
6. Derive the simplified flip-flop input equations and output equations.
7. Draw the logic diagram

7. FSM representation using Moore state
models
MATRUSRI
ENGINEERING COLLEGE
Suppose that we want a circuit with the following characteristics:
• One input w, and one output z
• Positive-edge-triggered design
• z = 1, if w = 1 during two consecutive clock cycles
Notes: using only input, we can not find an expression for output
•Hence need a state information – FSM

8. Develop State Diagram
MATRUSRI
ENGINEERING COLLEGE
The conceptually simplest method is to use a pictorial representation in the
form of a state diagram.
Optional to develop
One form to represent a FSM:
• How many states: States are circles
• Transitions between states: Transitions are directed edges
• Starting state: i.e. after reset/clear
Note in figure, reset is not treated as input: To simplify figure.

9. Develop State Table
MATRUSRI
ENGINEERING COLLEGE
Another way to describe a FSM
When implemented in a logic circuit, each state is represented by a particular
valuation (combination of values) of state variables.
It contains information on:
• States of the machine
• Transitions from all states, for all possible inputs
• Output values
• Reset information ignored: State A is assumed to be “start” state

10. Develop State Assignment
MATRUSRI
ENGINEERING COLLEGE
Find number of flip/flops needed to represent state
•No. of FFs = log2(no. of states)
Assign each state a combination of values of state variables
• “State assigned table”
• All unused variable combination are normally used as don’t cares
Below is the resulting table after state assignment
Notice that:
•Output depends on current state only - Moore type
•2 state variables are sufficient to represent 3 states
•Y1 & Y2 are next-state variables, y1&y2 are present-state variables
Need to decide type of FF to use as state element
Use D-FF since it is easiest
D1 = Y1, and D2 = Y2
For every next state and output, derive their function from present state and
input

11. Develop State Assignment
MATRUSRI
ENGINEERING COLLEGE



Y1 = w.y1y2
Y2 = w(y1+y2 )
z = y2



•State assignments has direct relation to the cost of derived implementation
Some state assignments are better than others
•Using the new state assignment a more cost effective realization in possible


Y1 = w, cheaper
Y2 = wy1, cheaper
z = y2 , same cost
Present state
y
2
y
1

Next state Output
Zw = 0 w = 1
Y
2
Y
1
Y
2
Y
1

A
B
C
D
00
01
10
11
00 01
00 10
00 10
d d
0
0
1
d
Present state
y
2
y
1

Next state Output
Zw = 0 w = 1
Y
2
Y
1
Y
2
Y
1

A
B
C
D
00
01
11
10
00 01
00 10
00 10
d d
0
0
1
d

12. Function Realization
MATRUSRI
ENGINEERING COLLEGE

13. Resulting Logic Circuit
MATRUSRI
ENGINEERING COLLEGE

14. Timing Diagram of Realization
MATRUSRI
ENGINEERING COLLEGE

15. FSM representation using Mealy state
models
MATRUSRI
ENGINEERING COLLEGE
Output values are generated using state & present inputs



State diagram State Table




State Assigned Table Logic Diagram





Y = D = wz = wy













Y = D = w
z = wy

16. Timing Diagram of Mealy Machine
MATRUSRI
ENGINEERING COLLEGE
Mealy implementation is more cost effective than Moore implementation
•However, circuit can be modified so that it behaves like a Moore machine
Note how output change based on state and input

17. 1.Moore machine produces an output over the change of transition states.

2.In mealy machine, the O/P depends upon present states and inputs.

3.The relationship that exists among the inputs, outputs, present states and
next states can be specified by either the state table or the state diagram.

4.A state-transition table is a table showing what state a finite-state
machine will move to, based on the current state and other inputs.
Questions & Answers
MATRUSRI
ENGINEERING COLLEGE

18. CONTENTS:

STATE MINIMIZATION
PARTITIONING MINIMIZATION PROCEDURE







OUTCOMES:

Students will be able to design a more complex FSM with fewer flips-flops.







MODULE-II: State Minimization
MATRUSRI
ENGINEERING COLLEGE

19. State Minimization
MATRUSRI
ENGINEERING COLLEGE
Two states Si and Sj are said to be equivalent if and only if for every possible
input sequence, the same output sequence will be produced regardless of
whether Si or Sj is the initial state.

Lower no. of states => lower no. of FFs
Solved using “partitioning minimization procedure”

Partition: A set of states
A partition consists of one or more blocks, where each block comprises a
subset of states that may be equivalent, but the states in a given block are
definitely not equivalent to the states in other blocks.

States in a partition may be equivalent.
Not equivalent to states in other partitions

20. State Minimization
MATRUSRI
ENGINEERING COLLEGE
•P1 = (ABCDEFG)
Partition based on output z
•P2 = (ABD)(CEFG),
Partition based on 0- & 1-successor for
block (ABD) & (CEFG)
•P3 = (ABD)(CEG)(F),
Partition based on 0- & 1-successor for
block (ABD) & (CEG),
•P4 = (AD)(B)(CEG)(F)
Partition based on 0- & 1-successor for block
(AD) & (CEG), => Final
•Final Partitions: P5 = (AD)(B)(CEG)(F)



2 FFs are sufficient after state minimization instead of 3

21. Incompletely Specified FSMs
MATRUSRI
ENGINEERING COLLEGE
The partitioning scheme for minimization of states works well when all
entries in the state table are specified. FSMs of this type are said to be
completely specified.
If one or more entries in the state table are not specified, corresponding to
don’t-care conditions, then the FSM is said to be incompletely specified.
Affects the number of minimized states
Assume x’s are zeros:
P1 = (ABCDEFG)
P2 = (ABDG)(CEF),
P3 = (AB)(D)(G)(CE)(F),
P4 = (A)(B)(D)(G)(CE)(F),
P5 = P4 => 6 states
Assume x’s are ones:
P1 = (ABCDEFG)
P2 = (AD)(BCEFG),
P3 = (AD)(B)(CEFG),
P4 = (AD)(B)(CEG)(F),
P5 = P4 => 4 states

22. 1.State Minimizing reduces the number of flips-flops used in the FSM.

2.State Minimizing reduces the complexity of the combinational circuit
needed in the FSM.

3.By state minimization, two different FSMs may exhibit identical behavior
in terms of the outputs produced in response to all possible inputs.

4.If one or more entries in the state table are not specified, corresponding to
don’t-care conditions, then the FSM is said to be incompletely specified.
Questions & Answers
MATRUSRI
ENGINEERING COLLEGE

23. CONTENTS:

ASM CHART
ASM BLOCK
SIMPLIFICATIONS AND TIMING CONSIDERATIONS WITH DESIGN EXAMPLE.





OUTCOMES:

Students will be able to design algorithmic state machines.







MODULE-V: ALGORITHMIC STATE
MACHINES (ASMs)
MATRUSRI
ENGINEERING COLLEGE

24. ASM
MATRUSRI
ENGINEERING COLLEGE
The design of the logic of a digital system can be divided into two distinct
efforts.
One part is concerned with designing the digital circuits that perform the
data-processing operations.
The other part is concerned with designing the control circuits that determine
the sequence in which the various manipulations of data are performed.

25. ASM Chart
MATRUSRI
ENGINEERING COLLEGE
ASM chart resembles a conventional flowchart describes the sequence of
events, i.e., the ordering of events in time, as well as the timing relationship
between the states of sequence controller and the events that occur while
going from one sate to the next.
An ASM chart is composed of three basic elements:
State box: Conditional box:




Decision box:

26. Example
MATRUSRI
ENGINEERING COLLEGE
Moore Model: Mealy Model:

27. ASM Block
MATRUSRI
ENGINEERING COLLEGE
An ASM block is a structure consisting of one state box and all the decision and
conditional boxes connected to its exit path.
An ASM block has one entrance and any number of exit paths represented by
the structure of the decision boxes.
An ASM chart consists of one or more interconnected blocks.
Example:

28. Simplifications
MATRUSRI
ENGINEERING COLLEGE
State diagram equivalent to the ASM chart:
Decision box can be simplified by labelling only the edge corresponding to the
asserted decision variable and leaving the other edge without a label.
A further it omits the edges corresponding to the state transitions that occur
when a reset condition is asserted.
•Output signals that are not asserted are not shown on the chart.
•Presence of the name of an output signal indicates that it is asserted.

29. Timing Considerations
MATRUSRI
ENGINEERING COLLEGE
Transition between states:


The timing for all registers and flip-flops in a digital system is controlled by a
master- clock generator.
The clock pulses are applied not only to the registers of the datapath, but also
to all the flip-flops in the state machine implementing the control unit.

30. 1.While converting a FSM state diagram to an ASM chart, every FSM state
will map into an ASM Block.

2.What are the three basic elements in an ASM chart?
Ans: State Box, Decision Box, Conditional box

3. Difference in conventional flowchart and ASM chart is time relationship.

4.State box without decision and conditional box is simple block.

5.In ASM design flip-flops are considered to be positive edge triggered.
Questions & Answers
MATRUSRI
ENGINEERING COLLEGE

31. CONTENTS:

A SIMPLE ARBITER








OUTCOMES:

Student will able to design and implement a FSM for serial adder



MODULE-VI: Additional Topic
MATRUSRI
ENGINEERING COLLEGE

32. A Simple Arbiter
MATRUSRI
ENGINEERING COLLEGE
When various devices need to use the resource, they have to request to do so.
These requests are handled by an arbiter circuit.
Arbitration structure







Handshake signaling
Communication between two entities in the asynchronous environment,
known as handshake signaling.

33. A Simple Arbiter
MATRUSRI
ENGINEERING COLLEGE
State diagram ASM Chart

34. A Simple Arbiter
MATRUSRI
ENGINEERING COLLEGE
Modified State diagram








Flow Table

Excitation Table






Y
1
= r
2
r
1
+ r
1
y
2
Y
2
= r
2
r
1
+ r
2
y
2

g
1
= y
1
g
2
= y
2

35. A Simple Arbiter
MATRUSRI
ENGINEERING COLLEGE
An alternative for avoiding a critical race
Flow Table





Excitation Table

Y
1
= r
1
y
2

Y
2
= r
1
r
2
y
1
+ r
2
y
2


g
1
= y
1


g
2
= y
2

36. A Simple Arbiter
MATRUSRI
ENGINEERING COLLEGE
Mealy model for the arbiter FSM
State diagram:



Flow Table:




Excitation Table:

Y = r
2
r
1
+ r
1
y + r
2
y
g
1
= r
1
y
g
2
= r
2
y

37. 1.When various devices need to use the resource, then requests are handled
by an arbiter circuit.

2.Each device communicates with the arbiter by means of two
signals—Request and Grant.

3.Communication between two entities in the asynchronous environment,
known as handshake signaling.

4.The time elapsed between the changes in the cause-effect signals depends
on the specific implementation of the circuit.
Questions & Answers
MATRUSRI
ENGINEERING COLLEGE

38. Question Bank
MATRUSRI
ENGINEERING COLLEGE
Short Answer Question

S.No

Question
Blooms
Taxonomy
Level
Course
Outcome
1Define ASM Block and explain with example. L2 CO4
2Draw ASM chart for the arbiter FSM. L1 CO4
3Explain transition and flow table in asynchronous
sequential circuit.
L2 CO4
4List out the elements of ASM chart and their operation. L1 CO4
5Draw ASM chart for vending machine. L1 CO4
6Explain Hazards in combinational circuits with examples. L2 CO4
7Differentiate between state table and flow table. L3 CO4
8Draw ASM chart for given FSM model
shown below.



L1 CO4
9Differentiate between ASM and ASMD chart. L3 CO4
10Explain simplifications and timing considerations. L2 CO4
PS Input X
0 1
A
B
C
D
E
B/0 E/0
A/1 C/1
B/0 C/1
C/0 E/0
D/1 A/0

39. Question Bank
MATRUSRI
ENGINEERING COLLEGE
Long Answer Question

S.No

Question
Blooms
Taxonomy
Level
Course
Outcome
1Design vending machine controller and implement its verilog
code.
L5 CO4
2Analyze given asynchronous sequential circuit and obtain its
state table and timing diagram.








L5 CO4
3Explain controller design with one hot design. L2 CO4
4With neat ASM chart and Verilog code, explain Binary
multiplier.
L2 CO4
5Describe steps involved in an analysis procedure of
asynchronous sequential circuits.
L5 CO4

40. Question Bank
MATRUSRI
ENGINEERING COLLEGE
Long Answer Question

S.No

Question
Blooms
Taxonomy
Level
Course
Outcome
6Derive a flow table that describes the behaviour of the as
shown
L3 CO4
7Analyze the given asynchronous sequential circuit. L5 CO4

41. Assignment Questions
MATRUSRI
ENGINEERING COLLEGE
1.Analyze given asynchronous sequential circuit and obtain its state table
and timing diagram.









2.With the help of block diagram, explain fundamental mode asynchronous
sequential machine.
3.Explain one hot state controller design.
4.Explain Binary multiplier with neat ASMD chart and write a verilog code.
5.Design vending machine controller. Draw its ASM chart and implement its
verilog code.