Chapter 2

Synchronous Sequential Circuit analysis and Design

2.1 Sequential circuit analysis
Sequential circuits are also called finite state machines (FSM), which is a more formal
name that often found in technical literature. The name derives from the fact that the
functional behavior of these circuits can be represented using a finite number of
states. A sequential circuit or finite state machine (FSM) can be described or specified
in three ways:
a) Algebraically using Boolean equations called Flip-flop input equations.
b) State Table.
c) State Diagram.
These three representations of a sequential circuit can be determined from the inputs,
outputs, and present state of the circuit. As stated in chapter 1, there are two
fundamental types of finite-state machines: Mealy and Moore. Sequential circuits, in
which the outputs depend on the inputs as well as on the states, are referred to as
Mealy model whereas if the outputs depend only on the states they are referred to as
Moore model. Analysis of a sequential circuit (Mealy or Moore) starts from a given
sequential logic diagram or flip-flop input equations of a sequential circuit and asks to
obtain the state table or the state diagram that specifies the behavior of the sequential
circuit. In this section, first we introduce an algebraic representation for specifying the
logic diagram of a sequential circuit. We then present a state table and state diagram
that describe the behavior of the circuit. Specific examples will be used throughout
the discussion to illustrate the various procedures.
2.1.1 Flip-flop Input Equations
The logic diagram of a sequential circuit consists of memory elements (flip-flops) and
often a combinational circuit. The part of the combinational circuit that generates the
signals for the inputs of the flip-flops can be described by a set of Boolean functions
called flip-flop input equations. These equations fully specify and represent the logic
diagram of a sequential circuit. An example of a sequential circuit (Meal circuit) is
shown in Figure 2.1. The circuit consists of two RS-type flip-flops labeled A and B,
one input variable X, and one output variable Y. it can be specified by the following
Boolean equations:
S B = X  A, RB = X  A, S A = X  B, R A = X  B, Y = X  A B

As a second example consider the Mealy type sequential circuit shown in Figure 2.2.
The circuit consists of two D-type flip-flops labeled A and B, one input variable X,
and one output variable Y. It can be specified by the following Boolean equations:

D A = AX + BX , DB = AX , Y = ( A + B)  X

1
X
Y

S Q B

B
B
R Q

S Q A
A
A
R Q

clk

Figure 2.1 SR-type sequential circuit

Figure 2.2 a D-type Sequential Circuit

2.1.2 State Table

The functional relationships between the inputs, outputs, and flip-flop states of a
sequential circuit can be enumerated in state table as shown in Table 2.1 for the

2
sequential circuit shown in Figure 2.2. The state table consists of four sections labeled
present state, input, next state, and output. The present state reflects the states of the
flip-flops before the occurrence of a clock pulse. The next state shows the states of the
flip-flops after the application of a clock pulse and the input and the output sections
list the values of the input and the output variables during the present state.

Table 2.1 State Table for of Figure 2.2

Present state Input Next state output
A B X A B Y
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 0 0 1
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 0
1 1 0 0 0 1
1 1 1 1 0 0

The state table shown above is one dimensional since the input is in a separate
column. A two-dimensional state table having the present state tabulated in the left
column and the inputs tabulated across the top row is also frequently used. Table 2.2
shows a two-dimensional state representation of Table 2.1.

Table 2.2 Two-dimensional State Table for the Circuit of Figure 2.2
Present Next state Output
state X=0 X=1 X=0 X=1
A B A B A B Y Y
0 0 0 0 0 1 0 0
0 1 0 0 1 1 1 0
1 0 0 0 1 0 1 0
1 1 0 0 1 0 1 0

As an example of a Moore model circuit, suppose we want to obtain the logic

diagram and state table of a sequential that is specified by the flip-flop input equation:
DA = A  X  Y
And output equation
Z=A
The DA symbol implies a D-type flip-flop with output designated by the letter A. The
X and Y variables are taken as inputs and Z as the output. The logic diagram and state
table for this circuit are shown in Figure 2.3. The state table has one column for the
present state and one column for the inputs. The next state and output are also in
single columns. The next state is derived from the flip-flop input equation. The output
column is simply a copy of the column for the present-state variable A.

3
2.1.3 State Diagram
The information available in state table can be represented graphically in the form of a
state diagram. In this type of diagram, a state is represented by a circle, and transitions
between states are indicated by directed lines connecting the circles. Examples of
state diagrams are show in Figure 2.4. The diagram in Figure 2.4(a) is for the
sequential circuit of Figure 2.2 and it derived from its state table of Table 2.1. The
state diagram provides the same information as the state table and is obtained directly
from it. The binary number inside each circle identifies the state of the flip-flops. For
Mealy model circuits, the directed lines are labeled with two binary number separated
by a slash. The input value during the present state precedes the slash, and the value
following the slash gives the output value during the present state with the given input
applied. For example, the directed line from the state 00 to state 01 is labeled 1/0,
meaning that when the sequential circuit is in the present state 00 and the input is 1,
the output is 0. After the next clock transition, the circuit goes to the next state, 01. If
the input changes to 0, then the output becomes 1, but if the input remains at 1, the
output stays at 0. This information is obtained from the state diagram along the two
directed lines emanating from the circle with state 01. A directed line connecting a
circle with itself indicates that no change of state occurs.

The state diagram of Figure 2.4(b) is for the Moore sequential circuit of Figure
2.3. The circuit has only one flip-flop with two states, two binary inputs, and one

4
output that depends only on the state of the flip-flop. For such a Moore model circuit,
the slash on the directed lines is not included, since the outputs depend only on the
state and not on the input values. Instead, the output is written inside a circle after a
slash as (state/output). There are two input conditions for each state transition in the
diagram, and they are separated by a comma. When there are two input variables,
each state may have up to four directed lines coming out of the corresponding circle,
depending upon the number of states and the next state for each binary combination of
the input values.

There is no difference between a state table and a state diagram, except for
their manner of representation. The state table is easier to derive from a given logic
diagram or input equations. The state diagram follows directly from the state table.

Example 2.1
A Moore sequential circuit with two JK flip-flops A and B and one input X is
specified by the following flip-flop input equations

J A = B, KA = BX
JB = X, K B = A X + AX = A  X
And output equation
Y = AB

a) Draw the logic diagram.

b) Derive the state table.
c) Obtain the state diagram.

Solution
Figure 2.5 shows the logic diagram, the state table, and state diagram of the sequential
circuit.

5
 A
J Q
A
X k Q Present Next
state Input state Output
Y A B X A B Y
0 0 0 0 1 0
B 0 0 1 0 0 0
J Q 0 1 0 1 1 0
B 0 1 1 1 0 0
1 0 0 1 1 0
k Q 1 0 1 1 0 0
1 1 0 0 0 1
clk 1 1 1 1 1 1

(a) Logic diagram (b) State Table

1

00/0 0 01/0

0 0
1

1 11/1 10/0 1
0

(c) State Diagram

Figure 2.5 Logic diagram, state table, and state diagram of Example 2.1

2.2 Sequential Circuit Design

The design of clocked sequential circuits starts from a set of specifications and
culminates in a logic diagram or a list of Boolean functions from which the logic
diagram can be obtained. In contrast to a combinational circuit, which is fully
specified by a truth table, a sequential circuit requires a state table or state diagram for
its specification. Thus, the first step in the design of a sequential circuit is to obtain a
state diagram or an equivalent representation such as a state table from the problem
statement.

A synchronous sequential circuit is made up of flip-flops and combinational

gates. The design of the circuit consists of choosing the flip-flops and finding a
combinational circuit structure which, together with the flip-flops, produces a circuit
that fulfils the stated specifications. The number of flip-flops is determined from the
number of states in the circuit; n flip-flops can represent up to 2n binary states. The
combinational circuit is derived from the state table by evaluating the flip-flop input
equations and output equations. In fact, once the type and the number of flip-flops are
determined, the design process involves a transformation from a sequential circuit
problem into a combinational circuit problem. In this way, the techniques of
combinational circuit design can be applied.

6
2.2.1 Sequential Circuit Design Procedure
The following is a procedure for the design of sequential circuits:
1. Obtain either the state diagram or state table from the statement of the
problem.
2. If only a state diagram is available from step 1, obtain the state table.
3. Assign binary codes to the states.
4. Derive the flip-flop input equations from the next state or flip-flop input
conditions entries in the encoded state table.
5. Derive output equations from the output entries in the state table.
6. Simplify the flip-flop input equations and output equations
7. Draw the logic diagram with flip-flops and combinational gates, as specified
by the flip-flop input equations and output equations.

The sequential circuit design process will be demonstrated by means of examples.

.
Example 2.2

Design a Mealy sequential circuit whose state diagram is given in Figure 2.6(a) using
Jk flip-flops.

Solution:
The first step in the design of a sequential circuit when the state diagram is given is to
obtain the design state table. The design state table, in addition to having columns for
present state, input, next state, and output, as in conventional state table, it also
includes a new column labeled flip-flop input conditions, from which the flip-flop
input equations are obtained. The flip-flop inputs in the table are derived using the
excitation table (Table 1.2) for JK flip-flop.
Figure 2.6(b) shows the design state table for the example derived from the
state diagram. Note that, in the table, the present state and input variable are arranged
in a form of a truth table having a column labeled inputs of combinational circuit and
outputs of combinational circuit which transform a sequential circuit problem into a
combinational circuit problem from which the flip-flop input equations and output
equation can be directly derived. K-maps are used to obtain the simplified flip-flop
input equations and output equation as shown in Figure 2.6(c). The sequential circuit
logic diagram is then drawn as shown in Figure 2.6(d) using the simplified flip-flop
input equations and the output equation.
Example 2.3
Design example 2.2 again using T flip-flops.
Solution:
The design procedure for sequential circuit with T flip-flips is the same as that for the
sequential circuits with JK flip-flops. Thus, following the same procedure, the
solution shown in Figure 2.7 is obtained.

7
 Inputs of Outputs of
combinational combinational
circuit circuit
0/0 0/1
Present Next
Flip-flop Inputs
state Input state Output
00 1/0 11 A B X A B JA KA JB KB Y
0 0 0 0 0 0 X 0 X 0
0 0 1 0 1 0 X 1 X 0
1/0 1/1 0 1 0 1 0 1 X X 1 0
0 1 1 0 1 0 X X 0 0
1 0 0 1 0 X 0 0 X 1
1/0 0/1 1 0 1 1 1 X 0 1 X 1
01 10
0/0 1 1 0 1 1 X 0 X 0 1
1 1 1 0 0 X 1 X 1 0

(a) State Diagram (b) State Table

BX BX BX
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 1 0 X X X X 0 1 X X
1 X X X X 1 1 1 1 X X

J A = BX K A = BX JB = X
BX BX
A 00 01 11 10 A 00 01 11 10
0 X X 1 0
1 X X 1 1 1 1 1

K B = AX + A X = A  X Y = AB + A X = A( B + X ) = A( BX )

(c) K-maps for inputs and output equations

X
J A
Q
A
k Q

B
J Q Y
B
k Q

clk

(d) Logic diagram

Figure 2.6 State diagram, state table, and Logic diagram for Example 2.2
.

8
 Inputs of Outputs of
combinational combinational
circuit circuit
0/0 0/1
Present Next
Flip-flop Inputs
state Input state Output
00 1/0 11 A B X A B TA TB Y
0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
1/0 1/1 0 1 0 1 0 1 1 0
0 1 1 0 1 0 0 0
1 0 0 1 0 0 0 1
1/0 1/0 1 0 1 1 1 0 1 1
01 10
0/0 1 1 0 1 1 0 0 1
1 1 1 0 0 1 1 0

(a) State Diagram (b) State Table

BX BX BX
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 1 0 1 1 0
1 1 1 1 1 1 1 1 1

T A = AB X + ABX TB = B X + AX + AB X Y = AB + A X
T A = B( A X + AX ) TT = X ( B + A) + AB X Y = A( B + X ) = A( BX )
TA = B( A  X )

(c) K-maps for inputs and output equations

T A
X Q
A
Q A

B
T Q Y
B
B
Q

clk
(e) Logic diagram

Figure 2.7 State diagram, state table, and Logic diagram for Example 2.3

Example 2.4
Design a sequential circuit for the state diagram shown in Figure 2.8(a) using D flip-
flops. The sequential circuit has two flip-flops A and B, an input X, and an output Y.
Solution:
The state table of the circuit is listed in Figure 2.8(b) and it is derived directly from
the state diagram. The flip-flop input equations are obtained from the next state values
as listed in the table. Note that the values listed in the column labeled next state are

9
 Inputs of Outputs of
combinational combinational
circuit circuit
Present Next
Flip-flop Inputs
state Input state Output
A B X A B DA DB Y
0/0 0/1 0 0 0 0 0 0 0 0
00 1/0 01 0 0 1 0 1 0 1 0
0 1 0 0 1 0 1 1
1/0 0 1 1 1 0 1 0 0
0/1 1 0 0 0 0 1
0/1 0 0
1/0 1 0
1 0 0 1 0 1
1 1 0 0 1 0 1 1
10 11 1 1 1 1 0 1 0 0
1/0

(a) State Diagram (b) State Table

BX BX BX
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 1 0 1 1 0 1
1 1 1 1 1 1 1 1

D A = BX DB = B X + B X Y = B X + AX
DB = X  B Y = X ( A + B)

(c) K-maps for inputs and output equations

X A
D Q
A
Q A

Y
B
D Q
B
B
Q

clk
(d) Logic diagram

Figure 2.8 State diagram, state table, and Logic diagram for Example 2.4

identical to the values listed in the column labeled flip-flop inputs. Thus, when
designing with D flip-flops the column labeled flip-flop inputs can be eliminated. The
complete design appears in Figure 2.8.

Example 2.5
Design a Moore sequential circuit with D flip-flops whose state diagram is shown in
Figure 2.9(a). The circuit consists of two flip-flops, one input X, one output Y.
Solution: The complete design is shown in Figure 2.9.

10
 Present Next
0 state Input state Output
1 0 A B X A B Y
00/1 01/0
0 0 0 0 1 1
1 0 0 1 0 0 1
0 1 0 0 1 0
1 1 0 1 1 0 0 0
1 0 0 1 1 0
1 0 1 0 1 0
11/0 10/0
0 1 1 0 1 1 0
0 1 1 1 0 0 0

(a) Moore State Diagram (b) State Table

BX BX BX
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 0 1 1 0 1 1
1 1 1 1 1 1 1 1

DA = A X DB = X + AB Y = AB = ( A + B)

(c) K-maps for inputs and output equations

D A
X Q
A
Q A

B Y
D Q
B
B
Q

clk
(d) Logic diagram

Figure 2.9 State diagram, state table, and Logic diagram for Example 2.5

2.2.2 Design with Unused States

A circuit with n flip-flops would have maximum 2n states. There are occasions when a
sequential circuit may use less than this maximum number of states. State that are not
used in specifying the sequential circuit are not listed in the state table or state
diagram. When simplifying the flip-flop input equations and output equations, the
unused states can be treated as don't-care conditions. This idea is illustrated in the
following example.

11
Example 2.6
Design the sequential circuit whose state diagram is shown in Figure 2.10(a) using RS
flip-flops.
Solution:
The state diagram shown in Figure 2.10(a) consists of five states and that means it
would require three flip-flops to implement the sequential circuit. In the state table
(Table 2.10(b), the three flip-flops are defined as A, B, and C and the input as X. With
three flip-flops, it is possible to specify eight states, but in this example the state
diagram and the state table list only five states. There are three unused states which
are 101, 110, and 111 that are not included in the state table. When the input X, with
value 0 or 1, is taken into account with the present state values, we obtain six unused
states for the present state and input columns: 1010, 1011, 1100, 1101, 1110, and
1111. These six combinations (or minterms) are not listed in the state table and hence
can be treated as don't-care minterms.
The flip-flop input equations and the output equation which form the
combinational circuit part of the sequential circuit are simplified in the K-maps of
Figure 2.10(c) and the logic diagram is shown in Figure 2.10(d). Note that the six
don't-care minterms are used in all k-maps and are marked as X in their corresponding
squares: 10, 11, 12, 13, 14, and 15.
One factor neglected up to this point in the design is the initial state of a
sequential circuit. When power is first turned on in a digital system, one does not
know in what state the flip-flops will settle. It is customary to provide a master-reset
input whose purpose is to initialize the states of all flip-flops in the system. Typically,
the master reset is a signal applied to all flip-flops asynchronously before the clocked
operations start. In most cases flip-flops are cleared to 0 by the master-reset signal,
but some may be set to 1.
It is possible that outside interference (noise) or malfunction will cause the
circuit to enter one of the unused states. Thus, it is sometimes desirable to specify
fully or at least partially the next state values or output values for the unused states. If
the sequential circuit circulates among invalid states, there will be no way to bring it
back to its intended sequence of state transitions. Although one can assume that this
undesirable condition is not supposed to occur, a careful designer must ensure that
this situation never occurs. Depending on the function and application of the circuit, a
number of ideas may be applied. First, the outputs for the unused states may be
specified so that any actions that result from entry into and transitions between the
unused states are not harmful. Second, an additional output may be provided or an
unused output code employed which indicates that the circuit has entered an incorrect
state. Third, to ensure that a return to normal operation is possible without resetting
the entire system, the next state behavior for the unused states may be specified.
Typically, next states are selected such that one of the normally occurring states is
reached regardless of the input values within a few clock cycles. The decision as to

12
 P-state Input N-state Flip-flop Inputs Output
0/0
000 A B C X A B C S A RA S B RB SC RC Y
0 0 0 0 0 0 0 0 X 0 X 0 X 0
0/0 0/0
1/0 0 0 0 1 0 0 1 0 X 0 X 1 0 0
0 0 1 0 0 1 0 0 X 1 0 0 1 0
100 0/0 0 0 1 1 0 1 1 0 X 1 0 X 0 0
001 010
1/1 0 1 0 0 0 0 0 0 X 0 1 0 X 0
0 1 0 1 0 1 1 0 X X 0 1 0 0
1/0 0 1 1 0 1 0 0 1 0 0 1 0 1 0
0/0 1/0 0 1 1 1 0 1 1 0 X X 0 X 0 1
011 1 0 0 0 0 0 0 0 1 0 X 0 X 0
1 0 0 1 0 1 1 0 1 1 0 1 0 1
1/1 1 0 1 0 0 1 1 0 1 1 0 X 0 1

(a) State Diagram (b) State Table

CX CX CX
AB 00 01 11 10 AB 00 01 11 10 AB 00 01 11 10
00 00 X X X X 00 1 1
01 1 01 X X X 01 X X
11 X X X X 11 X X X X 11 X X X X
10 X X 10 1 1 X X 10 1 X X

S A = BC X RA = C S B = BC + AX
CX CX CX
AB 00 01 11 10 AB 00 01 11 10 00 01 11 10
00 X X 00 1 X 00
01 1 1 01 1 X 01 1
11 X X X X 11 X X X X 11 X X X X
10 X X X 10 1 X X 10 1 X X

RB = B X SC = AX + A X = A  X RC = X
CX
(c) K-maps for inputs and output equations 00 01 11 10
00
B A
C S Q 01 1
X 11 X X X X
A
C R Q 10 1 X X
A
X Y = A X + CX
B
C S Q B

B B X Y
B
R Q
X X
A
S Q C
X
C
X C
R Q
clk
(d) Logic diagram
Figure 2.10 State diagram, state table, and Logic diagram for Example 2.6

which of the three options to apply, either individually or in combination, is based on

the application of the circuit or the policies of a particular design group. Therefore, if
a circuit contains unused states, the circuit must be investigated to determine the

13
effect of these unused states. The next state from invalid states can be determined
from the analysis of the circuit as is illustrated in the following example.
Example 2.7
Analyze the sequential circuit obtained in example 2.6 and determine the effect of the
unused states.
Solution:
The map of Figure 2.10 can be used to find the next state from each of unused states.
Take, for instance, the unused state 101. If the circuit, for some reason, happen to be
in the present state 101, an input X = 0 will transfer it to another (or the same) next
state. We first investigate minterm ABCX = 1010. From the maps, we see that this
minterm is included in the functions for SB, SC and Y. Therefore, flip-flops B and C
and function Y will be set to 1 but flip-flop A will not change (remains at 1). Since the
present state is ABC = 101, the next state will be ABC = 111. The maps also show
that the minterm ABCX = 1011 is included in the functions for SB and RC. Therefore,
flip-flop B will be set to1, flip-flop C will be reset to 0, and flip-flop A will remain at
1 while Y will be 0. Since the present state is ABC = 101, the next state will be ABC
= 110. Similarly, the next states for the remaining two unused states (110 and 111)
can be determined.
The result of the analysis is shown in the state diagram shown in Figure 2.11.
The circuit operates as intended, as long as it stays within the states 000, 001, 010,

0/0
000
0/0
0/0 1/0
0/0 010
001
100 1/0
1/1
1/0 0/1
1/0 110
0/0 011 1/1
1/0
0/1
0/1 111
1/1
101
0/1

Figure 2.11 State Diagram for example 2.7

011, and 100. If it ever finds itself in one of the invalid states 101, 110, or 111, it goes
to one of the valid state within one, two, or three clock pulses. Thus, the circuit is self-
starting and self-correcting, since it eventually goes to a valid state from which it
continues to operate as required.
A final observation would be necessary concerning the state diagram of Figure
2.11. When the state diagram enters either state 101 or 111 it is possible the state

14
diagram circulates between state 101 and 111 for several clock cycles if the input
becomes 0 for a long period of time. If this situation seems unacceptable, one possible
modification would be as follows. When the state diagram is in state 101 and the
input is 0, the next state can be forced to 011 instead of 111. This modification is
indicated by a dotted line in the state diagram of Figure 2.11 whereas in the state table
of Figure 2.10 a new raw is added (the last raw) that begins with minterm 1010 to
incorporate this modification. With help of k-maps of Figure 2.10 it can be easily
determined that all flip-flop input equations remain unchanged except the flip-flop
input for RA will be changed to
RA = A

2.2.3 Derivation of State Diagram

In the previous section, we have introduced the design procedure for obtaining a
sequential circuit starting from a given state diagram. Often a sequential circuit
specification is given in a form of a written statement describing the require behavior
of the circuit. Then from the written statement the designer derives the state diagram
for the sequential circuit. Formulation of a state diagram from a written description is
the most creative part of the design procedure which requires ingenuity and
intuitiveness in the part of the designer and the most important part of a sequential
circuit design. Once, the state diagram is derived from the written description, the
design procedure processes as in the previous section.
The technique for deriving a state diagram from a written specification will be
illustrated by means of sequence recognizers. A sequence recognizer is a circuit that
recognizes the occurrence of a particular sequence of bits anywhere in a long
sequence and it has the form shown in Figure 2.12. The circuit will examine a string
of 0's and 1's applied to the X input and generate an output Z = 1 only when a
prescribed input sequence occurs. Derivation of state diagrams for sequence
recognizers and their design will be illustrated by examples.

X Z
Sequence recognizer

Clock

Figure 2.12 Model for a sequence recognizer

Example 2.8
Design a sequential circuit with one input X and one output Y that recognizes
(detects) the sequence 110 applied to its input X by asserting its output Y high
whenever the sequence is detected. Design the circuit with Mealy and Moore models.

15
A sample input/output trace for a Mealy circuit:
X: 1011000100011010110110111100001101110
Y: 0000100000000100001001000010000010001
A sample input/output trace for a Moore circuit:
X: 10110001000110101101101111000011011100
Y: 00000100000000100001001000010000010001
A key factor in the formulation of any state diagram is to recognize that states
are used to "remember" something about the history of the input. For example, for the
sequence 110, to be able to produce the output value 1 coincident with the final 0 in
the sequence, the circuit must be in a state that "remembers" that the previous two
inputs were 11. With this concept in mind, we begin the formulation of the state
diagram by defining an arbitrary initial state A as the starting point for deriving the
state diagram. If the input X is 1 while the circuit in state A, the output Y is 0
indicating that the sequence has not occurred. After a clock pulse a transition from
state A to state B occurs to remember the occurrence of the first 1 in the sequence and
the output Y remains at 0. On the other hand, if the input X is 0, while the circuit in
state A, the output Y is 0 and when a clock pulse occurs the circuit remains in state A.
While the circuit in state B, if the input X is 1, a transition to a third state C occurs
after the second clock pulse to confirm that the first two 1's of the sequence have
occurred. On other hand, a 0 on the input X, while the circuit in state B, returns the
circuit to state A to indicate that the first 1 does not constitute the first bit in the
sequence. While the circuit in state C, if the input X is 0, the output Y is asserted high
to indicate that the complete sequence has occurred and when a clock pulse occurs, a
transition from state C to state A would take place. On the other hand, if the input X is
1, while the circuit in state C, the output Y is 0 and when a clock pulse occurs the
circuit remains in state C and it remains in that state as long as the input X is 1. While
the circuit in state C it remembers the occurrence of the first two 1's in the sequence.
The final Mealy state diagram is shown in Figure 2.13(a). Similarly, the Moore state
diagram can be obtained as shown in Figure 2.13(b). The simplified flip-flop input
equations and output equations for both Mealy and Moore models are given by the k-
maps shown in Figure 2.13 from which the logic diagrams, not shown here, can be
drawn.
In order to understand the difference between Mealy and Moore Model
circuits, the timing diagrams for example 2.8 for both models, showing the
input/output waveforms, are shown in Figure 2.14. The differences can be
summarized as follow:
1. Mealy circuit produces the output at the time of the last specified input
sequence, whereas, Moore circuit produces the output after the completion of
sequence, that is, one clock cycle later than Mealy as indicated in Figure 2.14.
2. Moore model requires more states than the corresponding Mealy model.

16
 0
A/0
A 0/0 00/0
0
00 0
0/0 1
1/0 B/0
0/1 01/0 1 D/1
B
10/1
01
C 1 C/0 0
1/0 11 11/0

1/0 1

(a) Mealy State Diagram for sequence 110 (b) Moore State Diagram for sequence 110

Present Next Present Next

state Input state Output
state Input state Output
A B X A B Y A B X A B Y
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 1 0 1 0
0 1 0 0 0 0 0 1 0 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0
1 0 0 X X X 1 0 0 0 0 1
1 0 1 X X X 1 0 1 0 1 1
1 1 0 0 0 1 1 1 0 1 0 0
1 1 1 1 1 0 1 1 1 1 1 0

(c) Mealy State Table (d) Moore State Table

BX BX BX BX
A 00 01 11 10 A 00 01 11 10 A 00 01 11 10 A 00 01 11 10
0 1 0 1 1 0 1 0 1 1
1 X X 1 1 X X 1 1 1 1 1 1 1

D A = BX DB = X DA = AB + BX DB = X
DA = B( A + X )
BX
A 00 01 11 10
0
1 X X 1 Y = AB

Y = AX

(e) K-maps for inputs (f) K-maps for inputs

and output equations for and output equations for
Mealy Circuit Moore Circuit

Figure 2.13 Sequence recognizer design for for Example 2.8

17
 1 2 3 4 5 6 7

clock

Mealy B

Moore
B

Figure 2.14 Mealy and Moore input/output waveform for sequence 110
.
Example 2.9
Design a sequential circuit with one input X and one output Y that recognizes
(detects) the sequence 10010 applied to its input X. The circuit should be able to
recognize the sequence anywhere in a long input sequence by asserting its output Y
high whenever the sequence is detected. Derive only the state diagrams for Mealy and
Moore models by considering the following two cases:
a) Overlapping is allowed.
b) Overlapping is not allowed.
Solution:
a) Overlapped case
The following is a sample input/output trace for overlapped case
X = 010100101011001001010100100
Y = 000000010000000100100000010 Mealy output
Y = 000000001000000010010000001 Moore output
Note that sequences leading to an output can overlap i.e., the final ---10 in the
above sequence can form the beginning of a new sequence as indicated by double line
in the input X. The overlapped state diagrams for Mealy and Moore can be derived as
shown in Figure 2.15.
b) No overlapped case
The following is a sample input/output trace for no overlapped case

18
 X = 010100101011001001010100100
Y = 000000010000000100000000010 Mealy output
Y = 000000001000000010000000001 Moore output
Mealy and Moore state diagrams for no overlapped case are shown in Figure 2.16.
1 0
1/0 0/0
1
B/0 A/0
1/0
B A
1
F/1
1/0 0 1 0
0/0 1/0 0/0 0
E 0
0/1 1 E/0
C D 1/0 C/0 D/0
0/0 0 1

(a) Mealy State Diagram (b) Moore State Diagram

Figure 2.15 Overlapped State Diagrams for sequence 10010

1 0
1/0 0/0
1
B/0 A/0
1/0 0
B A
1
0/1 F/1
0 1
0/0 1/0 0/0 0
1/0 E 0
1 E/0
C D 1/0 C/0 D/0
0/0 0 1

(a) Mealy State Diagram (b) Moore State Diagram

Figure 2.16 No overlapped State Diagrams for sequence 10010

Example 2.10
Derive Mealy and Moore state diagrams that capable of detecting either sequence 010
or 1001 anywhere in a long input sequence. Assume sequence overlap.
Solution:
The construction of the state diagram for this example is somewhat more complex
than the ones we have encountered in the previous examples. The circuit to be
designed again has the form shown in Figure 2.12. The output Y should be 1 if either
sequence 010 or 1001 is detected by the circuit. Before attempting to derive the state
diagrams, we will work out some typical input/output sequences to aid us for deriving
the Mealy and Moore state diagrams.

19
Clock cycle: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
X: 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 0
Y: 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 Mealy output
Y: 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 Moore output
The state diagrams for Mealy and Moore capable of recognizing sequence 010 or
1001are shown in Figure 2.17.
A
0 1 1
0
A
0/0 0/0 1/0
1/0 H/0
B/0
B F 0 0
1
1/0 1
1/0 0/0 G/0
C/0 1
0
C 0/1 1/0 E 1
0
F/0
0/0 1 0
1/1
D D/1 1
0/0 E/1
0

(a) Mealy State Diagram (b) Moore State Diagram

Figure 2.17 State Diagrams for example 2.10

. .

Example 2.11
Design a sequential circuit that monitors a senor through an input X as shown in
Figure 2.18. The sensor asserts its output X high for one clock cycle whenever it
senses unusual activity. When the sequential circuit sees that its input X is asserted
high by the sensor it raises its output Z high to turn on an alarm. To keep the alarm
on, output Z remains high until input Y is asserted high which causes the circuit to pull
its output Z low to turn off the alarm. Design Mealy and Moore models of the
sequential circuit.

X
sensor Sequential Z
alarm
circuit

Y
Figure 2.18 System of example 2.11

Solution:
The state diagrams for Mealy and Moore are shown in Figure 2.19(a) and (b),
respectively. Note that in the state diagrams, both inputs X and Y has don't-care

20
conditions denoted by x, which means a transition to a state occurs regardless of the
input denoted by x if the other input condition is satisfied. The logic diagrams for
Mealy and Moore are shown in Figure 2.19(e) and (f), respectively. The logic
diagrams for both models are identical but they only differ in the output section where
output Z in Moore circuit is taken directly from the flip-flop output.

0x/0 XY/Z XY/Z

x0/1 0x x0
x1/0 x1
a b a/0 b/1

1x/1 1x

(a) Mealy State Diagram (b) Moore State Diagram

Present Next Present Next

state Input state Output Input Output
state state
A X Y A Y A X Y A Y
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 1 1 0 1 0 1 0
0 1 1 1 1 0 1 1 1 0
1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 1 0 1 0 1
1 1 0 1 1 1 1 0 1 1
1 1 1 0 0 1 1 1 0 1

(c) Mealy State Table (d) Moore State Table

XY
A 00 01 11 10
0 1 1
Z=A
1 1 1

DA = AX + AY Z = DA

X Z
X
D Q A D Z
Y Y Q A
A A
clock Q A clock Q A

(e) Mealy Logic Diagram (f) Moore Logic Diagram

Figure 2.19 State Diagrams and Logic Diagrams for Example 2.11

Example 2.12
Design a sequential circuit with two T flip-flops A and B, two inputs E and W, and
one output Z. if E = 0, the circuit remains in the same state regardless of the value of
W. When E = 1 and W = 1, the circuit goes through the state transitions from 00 to 01
to 10 to 11, back to 00 and then repeats. When E = 1 and W = 0, the circuit goes
through the state transitions from 00 to 11to 10 to 01, back to 00, and then repeats.
Anytime the circuit goes through one complete transition it asserts its output Z high
Solution:
The state diagram, the state table, and the logic diagram of the sequential circuit are
shown in Figure 2.20.

21
 Inputs of Outputs of
0X/0 0X/0 combinational combinational
circuit circuit
Present Next Flip-flop
11/0
00 01 state Input state Inputs Output

10/1 A B E W A B TA TB Z
0 0 0 0 0 0 0 0 0
11/1 10/0 10/0 11/0 0 0 0 1 0 0 0 0 0
0 0 1 0 1 1 1 1 0
0 0 1 1 0 1 0 1 0
0X/0 10/0 0X/0 0 1 0 0 0 1 0 0 0
11 10
0 1 0 1 0 1 0 0 0
11/0 0 1 1 0 0 0 0 1 1
0 1 1 1 1 0 1 1 0
(a) State Diagram 1 0 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0 0
1 0 1 0 0 1 1 1 0
1 0 1 1 1 1 0 1 0
1 1 0 0 1 1 0 0 0
1 1 0 1 1 1 0 0 0
1 1 1 0 1 0 0 1 0
1 1 1 1 0 0 1 1 1

EW EW (b) State Table

AB 00 01 11 10 AB 00 01 11 10
00 1 00 1 1

01 1 01 1 1

11 1 11 1 1

10 1 10 1 1

TA = BEW + BEW Z = ABEW + ABEW

TB = E
TA = E ( BW + BW ) Z = BE ( AW + AW )
TA = E ( B  W ) Z = BE ( A  W )

(c) K-maps for inputs and output equations

T A
W Q
E A

T Q B

B
Q

clk
(e) Logic diagram
Figure 2.20 State diagram, state table, and Logic diagram for
Example 2.12

22
Example 2.13
When a certain serial binary communication channel is operating correctly, all blocks
of 0's are of even length and all blocks of 1's are of odd length. Find the state diagram
of a circuit that will produce an output Z = 1 whenever a discrepancy from the above
pattern is detected.
Example: X: 00100011101100
Z: 00000010001010
Note that the example shows the output Z is identical for both Moore and Mealy
models but their state diagrams are different as shown below. The solutions show that
Moore state diagram contains 6 states whereas Mealy state diagram contains 4 states
and that makes the Mealy state diagram the preferable choice for this problem.
Solution:

S0/0
1
0 s0
0 0 S3/0 0/0 1/0
S1/0 1 0/0
1/1 s2
0 1 s1
1 S4/0 0/0 1/0
S2/1 1 0/1 1/0
0 0 s3
1 S5/1

Moore state diagram Mealy state diagram

2.3 Flip-flop Conversion

It is possible to convert any given flip-flop to other flip-flops using sequential
technique presented in the previous sections. This will be illustrated by means of
examples.
Example 2.14
Convert a D flip-flop (FF) to a JK FF and a T FF.
Solution:
This example, in other words, ask you to design a JK FF and a T FF using D FF as a
memory element where J, K, and T are external inputs to the combinational circuit
that is part of the sequential circuit that implements these two FFs as shown in the
block diagram of Figure 2.21. Figure 2.1 consists of a memory element (DFF) and a
combinational circuit. The problem is to obtain the combinational circuit. To do that
first, construction two state tables, one for JK FF and another one for T FF. From
these state tables determine the FF input equations which specify the combinational
part of the sequential circuit. Use these equations to draw the logic diagram of the
circuit.

23
 K D Q A
Combinational
circuit A
J
Q A
clock

Combinational
D Q A
T
circuit A
Q A
clock

Figure 2.21 Block Diagrams

Present Next Present Next

state Input state Input
state state
A J k A A T A
JK
0 0 0 0 A 00 01 11 10 0 0 0
0 0 1 0 0 1 1 0 1 1
0 1 0 1 1 0 1
0 1 1 1 1 1 1 1 1 0
1 0 0 1
1 0 1 0 D A = AJ + A K
1 1 0 1 (b) T State Table
1 1 1 0

(a) JK State Table D A = AT + AT = A  T

K
D Q A D Q A
J T
A A
clock Q A Q A
clock

(c) JK FF Logic Diagram (d) T FF Logic Diagram

Figure 2.22 State Diagrams and Logic Diagrams for Example 2.13

The state tables for JK FF and T FF can be obtained as shown in Figure

2.22(a) and (b), respectively. From the state tables the FF input equations are obtained
and these equations are used to draw the logic diagrams for JK FF and T FF as shown
in Figure 2.22(c) and (d), respectively.

Example 2.15
Convert a JK flip-flop (FF) to a D FF.
Solution:
In this example, we need to obtain a D flip-flop using JK flip-flop as a memory
element. First, the state table is constructed considering D as an external input as
shown in Figure 2.23 (a) from which the flip-flop input equations are obtained. Using
these equations the logic diagram of the D flip-flop is drawn as in Figure 2.23 (b).

24
 Present Next
Flip-flop Inputs
state Input state D D
A D A JA KB A 0 1 A 0 1
0 0 0 0 X 0 1 0 X X
0 1 1 1 X 1 X X 1 1
1 0 0 X 1
1 1 1 X 0
JA = D KA = D

(a) State Table

D J Q
A

K Q

clk
(b) D FF Logic diagram

Figure 2.23 State Table and Logic Diagram for Example 2.14
. .

Example 2.16
Derive two state diagrams one for Mealy and another for Moore with one input X
and one output Y that recognizes the two sequence 01010 and 0100 anywhere on the
input sequence X. When the circuit recognizes any of the two sequences it asserts its
output Z high. Assume sequences overlap.
Solution:
1

S0/0

0 0
1
S1/0

1
1/0 1

S0 S2/0
0
0/0 1/0
0/0
0
S1
S4 1 S5/0
S3/0
1/0
1/0 0/1 1 1
1/0 0 0
0/1
S2 S4/1 S6/1
0
0/0 S3

Mealy state diagram Moore state diagram

25
 Assignment # 2
2.1 A sequential circuit with two D flip-flops A and B, two inputs X and Y, and one
output Z is specified by the following input equations:
DA = X A + X A
DB = X A + XB
Z = XB
(a) Draw the logic diagram of the circuit
(b) Derive the state table
(c) Derive the state diagram

2.2 A sequential circuit has three JK flip-flops A, B, and C, and input X. The circuit is
specified by the following flip-flop input equations:
J A = K A = (B  C) + (B  C) X
J B = KB = A
J C = KC = B
(a) Draw the logic diagram of the sequential circuit specified by the above
Boolean equations.
(b) Derive the state table.
(c) Derive the state diagram.

2.3 Starting from state 00 in the state diagram given below determine the state
transitions and output sequence that will be generated when an input sequence of
10011011110 are applied.

2.4 Design a sequential circuit with two D flip-flop A and B and one input X. When
X = 0, the state of the circuit remains the same. When X = 1, the circuit goes through
the state transitions from 00 to10 to 11 to 01, back to 00, and then repeats. (Design
and test the circuit in the lab).
2.5 Design a sequential circuit specified by the state table shown below using D FFs.

26
2.6 A sequential circuit has two flip-flop A and B, one input X and one output Y. The
state diagram is shown in the figure below. Design the circuit with JK and T flip-
flops.
1 0

0
00/0 01/0

1
0 1
1
11/1 10/1
0

2.7 Design a Mealy sequential circuit with one input X and one output Y that
recognizes the sequence 1101 anywhere on the input sequence X. When the circuit
recognizes the sequence it asserts its output Z high. Design the circuit with T flip-
flops.

2.8 Design a circuit with JK flip-flops that implements the following state diagram.
Also determine the effect of unused state.

27
2.9 Derive two state diagrams one for Mealy and another for Moore that has one input
X and one output Z. The circuit should be capable of detecting the occurrence of
either sequence 1001or 1101 anywhere in a long input sequence X and asserts its
output Z high when one of the sequences occurs. Assume sequence overlap. The
following is a sample input/output
X: 0101101001100110100011010
Z: 0000001001000100100000010
2.10 Derive two state diagrams one for Mealy and another for Moore that capable of
recognizing the occurrence of either sequence 110 or 0110 anywhere in a long input
sequence.
2.11 A sequential circuit has two inputs, X1 and X2, and one output Z. The circuit
function is to compare the two input sequences occurring along its inputs X1 and X2.
If X1 = X2 during any four consecutive clock cycles, the circuit asserts its output Z
high to indicate that two identical sequences have occurred. Derive only the state
diagram for the circuit. The following is a sample input/output:
X1: 011011100011011101
X2: 111010100011101101
Z: 000010000111000001
2.12 Design a serial two’s complement circuit with one input X and one output Z. An
arbitrary length binary number is entered one bit at a time through input X, starting
with the least significant bit. The circuit yields the two's complement at output Z on
the same cycle.
2.13 Design a sequential circuit which produces an output Z = 1 whenever any of the
following input sequences occur: 1100, 1010, or 1001. The circuit resets to its initial
state after a 1 output is generated. Find the state diagram.
2.14 When a certain serial binary communication channel is operating correctly, all
blocks of 0's are of even length and all blocks of 1's are of odd length. Find the state
diagram of a circuit that will produce an output Z = 1 whenever a discrepancy from
the above pattern is detected.
Example: X: 00100011101100
Z: 00000010001010
2.15 Design a Mealy and a Moore circuits whose output is 1 iff (if and only if) the
input has been 1 for at least three consecutive clock cycles. The following is a sample
input/output for both models:

Input X: 01111111011011101
Output Z: 000011111000000100 Moore output
Z: 00011111000000100 Mealy output

28
2.16 Design a sequential circuit with T flip-flops that implements the following state
diagram. Also determine the effect of the unused states.

1/0

S0
0/0 1/0
0/0
S1
S4
1/0
1/0 0/1
1/0 0/1
S2
0/0 S3

29