Logic Circuits

EG 533EX

Chapter 4
Sequential Machines

- Jyoti Tandukar

Chapter Introduction

Sequential systems are the circuits that need to take
care of past as well as the current input to determine
the output.

There are two types of sequential machines:
synchronous and asynchronous

Synchronous circuits have their operations following
a certain timing train provided by the timer unit.

Asynchronous circuits do not have any timing
reference of the sort.

Flip-flops are the basic memory element of any
sequential machine. This chapter introduces
procedures to design and develop the sequential
machines using these basic elements and other
necessary components

Topics Covered

4.1 Synchronous machines

4.1.1 Clock driven models and state diagrams

4.1.2 Transition tables, Redundant states

4.1.3 Binary assignment

4.1.4 Use of flip-flops in realizing the models

4.2 Asynchronous machines

4.2.1 Hazards in asynchronous systems and use of
redundant branch

4.2.2 Allowable transitions

4.2.3 Flow tables and merger diagrams

4.2.4 Excitation maps and realization of the model

1
4.0 Sequential Machine

In sequential machines, the current output depends upon
previous as well as present inputs

Sequential machines can be categorized into two types:
1. Synchronous: all events occur on the edge of a clock
2. Asynchronous: there are no clocks, a change in state / output
only caused by change in inputs.

A synchronous machine can only be as fast as the clock,

whereas, asynchronous machines are the fastest you can build
because they are never waiting for the clock.

4.1 Synchronous Machines

Consider a machine that has a single
control input X and the CLOCK, and
two outputs A and B. On consecutive
rising edges of the CLOCK, the code
on A and B changes from 00 to 01 to
10 to 11 and then repeats itself if X is
ENABLED. If at any time X is
DISABLED, this machine is supposed
to hold its present state. This machine
can be described graphically with the
aid of the figure

The State Diagram

Each STATE of the STATE DIAGRAM
provides us with the following
information:

1. Symbol or code to identify the state.

2. The PREVIOUS STATE

3. The INPUT conditions leading to the
state of interest

4. The OUTPUT specifications for the
state of interest
5. The NEXT STATES and NEXT
STATE branching conditions (if any)

2
The Transition Table

Example

Consider another system that has two inputs, x1
and x2, which are in the form of three bit words.
The output of the machine, z, goes high when any
three bit message contains 101 for both inputs, x1
and x2.

x1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 ……
x2 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 ……
z 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ……

State Diagram
Transition Table

3
Redundant States

Two states are
equivalent if they have
the same next state
and output conditions.
If they are equivalent,
one of them is
redundant.

The figure illustrates
the tabular method for
checking for redundant
states

The New State Diagram

and Transition Table

Example

A machine has two
serial inputs x1
and x2, and one
output z. The
machine is
required to give an
output z = 1 when
both x1 and x2
contain the
message 011.

4
Transition Table

Pure Binary Assignment

Circuit Realization
Using SR Flip-flop

5
 Circuit Realization
Contd.

Circuit Diagram

Exercise

More Don’t Cares make
the Karnaugh map simpler,
which, in turn, results in a simpler circuit.

Design the same circuit using JK Flip-flop

6
4.2 Asynchronous Machines

Hazard in asynchronous system and use

of redundant branch
Consider that we do not take the covering AD, because all 1s have already been
covered by AB’ + BD, and build the circuit as indicated above. In such a case
suppose A = 0, B = 1, D = 1

As A’ + B = 1, and B’ + D’ = 0; the output is 1.

Next suppose A and B both change state at the same time, making A = 1, B = 0,
D = 1 as the input state.
This time, A’ + B = 0 and B’ + D’ = 1, so the output is 1 again.

But, as we know, there will be a small delay in the NOT gate when the input
changes, and the input B will not reach the input terminal of N at the same time
as the input A. For a time equal to the propagation delay of the NOT gate, after
the input changes, A = 1, B = 1; giving A’ + B = 1. Hence the output is 0. Due to
this reason, we encounter a glitch at the time when such inputs are changed.

Hazard Free Covering

The glitch may cause a big problem in
asynchronous system because the level is
continuously monitored. Whereas, in
synchronous system the clock can be
controlled so as to read either side of the
glitch, but not the glitch itself. To solve such a
race condition, we take one more covering,
i.e., AD. This branch holds the output to 1
despite the glitch. However, the boolean
output is still equivalent. This branch is called
redundant branch and the covering is called
hazard free covering

7
Allowable Transitions

When a change in input occurs, there will
be a small delay before there is a
corresponding change in state, due to the
propagation delay. Consider a change in
state from 00 to 11. In reality, both bits
cannot change at exactly the same time.
So the transition will be as shown in the
figure

00 → 0 1 or 1 0 → 11

Such a transition may affect our design.

So, with asynchronous machines, we
make the rule that we may change only
one input at a time

Example
Consider the design of
a divide by 2 counter

Primitive Flow Table

A circle in the
primitive flow table
specifies the stable
state. Each stable
state has its own row
in the primitive flow
table

8
Assigned Flow Table

To ensure only a single secondary a → b
variable change, we must place the b → c
rows in the allowable transitions c → d
d → a
into adjacent squares. This ensures
that we do not have the uncertainty
of not knowing which secondary
variable will change first as would
be the case if two or more
secondary variables changed at a
transition.

Excitation Map

Example

Now consider another sequential machine that has
two inputs x1 and x2, and one output z. The
system output will become logic 1 whenever the
sequence x1 = 001, x2 = 011 appears on the
inputs. Using a non redundant flow table and valid
assignment, a hazard free system is to be
designed, which will produce the output as long as
possible (holds output to 1 during unstable stage).

9
Primitive Flow Table

States are redundant under the
same conditions as for
synchronous machines. States
can only be equivalent if they are
in the same column of the flow
table, otherwise they have
different input conditions. State 1
cannot be equivalent to any other
state because it is the only one
with the input 00. 4 and 7 are
equivalent, 5 and 8 are
equivalent.

Non Redundant Flow Table

10
Merger Diagram

3 cannot be merged because it has
different output condition.

1 and 2 can be merged because

they have similar conditions. For
the same reason, 4, 5 and 6 can be
merged

1,2 → a

3 → b

4,5,6→ c

Allowable Transitions

a → b, c
(transition of 3, 5)

b → c
(transition of 4, 5)

c → a
(transition of 1)

Assigned Flow Table

11
Excitation Maps

Circuit Diagram

Exercises to Try

A sequential machine has two inputs x1 and x2
and one output z. The system provides an output
when the input has the following sequence:
01 11 10
Design a hazard free system to produce output as
long as possible.

A machine has two serial inputs x1 and x2 and one
output z. The machine is to provides an output of
z=1 if only x1 contains the message 011.

12