Unit IV: State Machines

5.20 Clocked Sequential Circuit

The clocked sequential circuit is synchronous circuit. In clocked synchronous circuit,
the flip-flops are the basic elements. All the flip-flops those are used in circuit are clocked
simultaneously. The next state of clocked synchronous circuits depends on present input (s)
and present state of clocked circuits. The output of clocked synchronous circuit may or may not
be function of present input; therefore the clocked synchronous circuits are classified into two
types such as 1) Moore circuit and 2) Mealy circuit.
5.20.1 Moore Circuit:
The clocked synchronous circuit is said to be Moore circuit, in which the output Y
depends only on the present state of the flip-flops, it is independent on present input(s). Fig.
5.103 shows the general block diagram of Moore circuit.

General block diagram of Moore circuit.

Where X1, X2 ------- Xi are the inputs. I1, I2 ------- In are the outputs of next state decoder,
which control the next state of memory elements. The I 1, I2 ------- In are the function of inputs
and present output state of memory elements. Y1, Y2 ------- Ym are the outputs, which are the
function of present output state of memory elements only.
i.e. Next state = F (present state, inputs)
Output = F (present state)
For example:
The Moore circuit is shown in Fig. 5.104.

(4.1)
 Fig. 5.104: Moore circuit
Clock is given simultaneously to both the flip-flops. Therefore the circuit is said to be

clocked circuit. The output Y= QB. Q A . It is a function of present state of the circuit only; it is

independent on input X.
5.20.2 Mealy Circuit:
The clocked sequential circuit is said to be mealy circuit, in which output depends on
present state of flip-flop(s) and on the input(s). Fig. 5.105 shows the general block diagram of
Mealy circuit.

Fig. 5.105: General block diagram of Mealy circuit.

Where X1, X2 ------- Xi are the inputs. I1, I2 ------- In are the outputs of next state decoder,
which control the next state of memory elements. The I 1, I2 ------- In are the function of inputs

2
and present output state of memory elements. Y1, Y2 ------- Ym are the outputs, these are the
function of present output state of memory elements and inputs.
i.e. Next state = F (present state, inputs)
Output = F (present state, inputs)
For example:
The mealy circuit is shown in Fig.5.106.

Fig. 5.106: mealy circuit

Clock is given simultaneously to both the flip-flops; therefore the circuit is said to be

clocked circuit. The output Y= QB. Q A . X . It is a function of present state of the circuit and

input.
5.21 Analysis Of Clocked Sequential Circuit:
In sequential circuit, the output and next state of the flip-flops are the function of
input(s) and present state, it is depends on type of the circuit Moore or Mealy. The analysis of
clocked sequential circuit is nothing but to find the output and next state for all possible
combinations of input(s) and present states, which are shown by table or diagram. Such a table
is referred as state table and diagram is referred as state diagram.
5.21.1 State Table:
State table shows the output and next state of sequential logic circuit for all possible
combination of input(s) and present state(s). The procedure to find the state table is:
1. For given circuit diagram; find the expression for the inputs of flip-flops.
2. Assume input X is equal to 0 and find the next state and output for all possible
combinations of present state.
3. Assume input X is equal to 1, and find the next state and output for all possible
combinations of present state.
3
 4. Draw the table which shows present state, next state for input X is equal to 0, next
state for input X is equal to 1, output for input X is equal to 0 and output for input X
is equal to 1.
For example:
Consider the sequential logic circuit as shown in Fig. 5.107.

Fig. 5.107: sequential logic circuit

Fig. 5.107consists of two flip-flops i.e. flip-flop A and flip-flop B. The Boolean equations
for the inputs JA, KA, JB, KB and output Y are

JA = X. Q B ; KA = X QB ; JB = X QA; KB = Vcc X Q A and

Y = QB QA .
Present state; next state and output of the sequential logic circuit for X=0 is given in table
5.60.
Table 5.60: Present state; Next state and output of
Sequential logic circuit of Fig. 5.107 for X=0
The present state Next state output
QA QB JA KA JB KB QA QB Y
0 0 0 1 0 1 0 0 0
0 1 0 1 0 1 0 0 0
1 0 0 1 1 0 0 1 1
1 1 0 1 1 0 0 1 1
When present state is 0, 0; the input of flip-flop A is 0, 1 and next state of flip-flop is 0; the input
of flip-flop B is 0, 1; and next state is 0 and output is ‘0’.
When present state is 0, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0,
the input of flip-flop B is 0, 1 and next state is 0 and output is ‘0’.
When present state is 1,0; the input of flip-flop A is 0 1 and next state of flip-flop is 0;
the input of flip-flop B is 1, 0 ;and next state is 1 and output is ‘1’.

4
 When present state is 1, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0;
the input of flip-flop B is 1 ,0 and next state is 1 and output is ‘1’;
Present state; next state and output of the sequential logic circuit for X=1 is
given in table 5.61.
Table 5.61: Present state; Next state and output of
Sequential logic circuit of Fig. 5.107 For X=1.
The present state Next state output
QA QB JA K A JB K B QA QB Y
0 0 1 0 0 1 1 0 0
0 1 0 1 0 1 0 0 0
1 0 1 0 0 1 1 0 0
1 1 0 1 0 1 0 0 0
When present state is 0, 0; the input of flip-flop A is 1, 0 and next state of flip-flop is 1;
the input of flip-flop B is 0, 1 and next state is 0; and output is ‘0’;
When present state is 0, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0;
the input of flip-flop B is 1, 0 and next state is 0; and output is ‘0’.
When present state is 1, 0; the input of flip-flop A is 1, 0 and next state of flip-flop is 1;
the input of flip-flop B is 0, 1 and next state is 0 ;and output is ‘0’.
When present state is 1, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0;
the input of flip-flop B is 0 ,1 and next state is 0; and output is ‘0’.
The state table for given sequential circuit is given in table 5.62
Table 5.62: state table for sequential circuit 0f Fig. 5.107
Next state Output
Present state
X=0 X=1 X=0 X=1
QA QB QA QB QA QB Y Y
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 1 1 0 1 0
1 1 0 1 0 0 1 0

Example 5.19 : Draw the state table for the following circuit.

5
 Fig. 5.108: Given Sequential circuit

Solution:
Fig. 5.108 consists of two flip-flops i.e. flip-flop A and flip-flop B. The Boolean equation for the
inputs JA, KA, JB, KB and output Y is

JA = X.QB KA = XQB JB = X QA KB = Vcc and Y = QA QB X

Present state; next state and output of the sequential logic circuit for X=0 is given in table
5.63.
Table 5.63: Present state; Next state and output of
Sequential logic circuit of Fig. 5.108 for X=0
The present state Next state output
QA QB JA KA JB KB QA QB Y
0 0 0 1 0 1 0 0 0
0 1 0 1 0 1 0 0 0
1 0 0 1 1 1 0 1 0
1 1 0 1 1 1 0 0 0
When present state is 0, 0; the input of flip-flop A is 0,1 and next state of flip-flop is 0;the input of
flip-flop B is 0, 1 and next state is 0; and output is ‘0’.
When present state is 0, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0;
the input of flip-flop B is 0, 1 and next state is 0; and output is ‘0’.
When present state is 1, 0 ; the input of flip-flop A is 0, 1 and next state of flip-flop is
0; the input of flip-flop B is 1 ,1 and next state is 1 ;and output is ‘0’.
When present state is 1, 1; the input of flip-flop A is 0, 1 and next state of flip-flop is 0;
the input of flip-flop B is 1, 1 and next state is 0; and output is ‘0’.
Present state; next state and output of the sequential logic circuit for X=1 is given in table
5.64.
Table 5.64: Present state; Next state and output of
Sequential logic circuit of Fig. 5.108 for X=1
6
 Next state
The present state
output
QA QB JA KA JB KB QA QB Y
0 0 0 1 0 1 0 0 0
0 1 1 0 0 1 1 0 1
1 0 0 1 0 1 0 0 0
1 1 1 0 0 1 1 0 1
When present state is 0 ,0; the input of flip-flop A is 0 ,1 and next state of flip-flop is
0; the input of flip-flop B is 0 ,1 and next state is 0; and output is ‘0’.
When present state is 0 ,1; the input of flip-flop A is 1, 0 and next state of flip-flop is 1;
the input of flip-flop B is 0 ,1 and next state is 0; and output is ‘1’.
When present state is 1 ,0; the input of flip-flop A is 0 ,1 and next state of flip-flop is 0;
the input of flip-flop B is 0, 1 and next state is 0; and output is ‘0’.
When present state is 1, 1; the input of flip-flop A is 1, 0 and next state of flip-flop is 1;
the input of flip-flop B is 0 ,1 and next state is 0 ;and output is ‘1’.
The sate table for given sequential circuit is given in table 5.65
Table 5.65: State table for sequential circuit (Fig. 5.108)
Next state Output
Present state
X=0 X=1 X=0 X=1
QA QB QA QB Q A QB Y Y
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 1
1 0 0 1 0 0 0 0
1 1 0 0 1 0 0 1

5.21.2 State Diagram:

State diagram is graphical representation of state table. The state is represented by
circle, with the state indicated inside the circle and directed lines connecting the states
indicated the transition between the states; when input is applied and circuit is clocked. The
input and output conditions are labeled with two binary numbers separated by the symbol ‘/’
along with directed lines. The first bit indicates the input and bit after the symbol ‘/’ indicates
the output. The state diagram for three bit up counter is shown in Fig. 5.109. When present
state is 000, next state is 001; the next state is 010 and so on. This state diagram shows that
next state depends on present state only.

7
 Fig. 5.109: State diagram for three bit up counter
The state diagram of three-bit up/down is shown in Fig.5.110. The sequential circuit
acts as up counter; if X is equal to 0 otherwise circuit acts as down counter. When present state
000, the next state is 001 for X is equal to 0 and next state is 111 for X is equal to 1

Fig. 5.110: State diagram for three-bit up/down

The state diagram of three-bit up/down counter is shown in Fig. 5.111. The circuit acts,
as up counter when X is equal to 0 and output is ‘1’. The circuit acts as down counter with X is
equal to 1 and output is ‘0’.

Fig. 5.111: state diagram for three-bit up/down counter

When present state is 010; next states is 011 for input X is equal to 0; and Y is equal to 1; the
next state is 001 for input X is equal to 1 and Y is equal to 0.
8
 In case of Moore circuit the output is not the function of input, therefore the directed
lines are located with only one binary number, which represent the state of the input and
output state is indicated within the circle below the present state as shown in Fig. 5.112.

Fig. 5.112 Given Sequential circuit

5.22 Design of Clocked Sequential Circuit:
The clocked sequential circuit is defined by the set of statements or state table or state
diagram.
1. When the clocked sequential circuit is defined by the set of statements, then the
first step of design of clocked sequential circuit is to prepare the state table from
the set of statements.
2. From the state table draw the state diagram.
3. Using the state reduction technique reduce the number of states.
4. If states are not given in binary, assign the binary values to each state in the state
table, as explain in section 5.22.5.
5. Determine the number of flip-flops required to implement the given state table..
6. Draw the excitation table for circuit as per the state table and selection of flip-
flops.
7. Using K-map simplifies and writes the Boolean equations for inputs of flip-flops
and output(s).
8. Draw the logic diagram.
5.22.1 State Diagram:
State diagram is graphical representation of state table, in analysis of clocked
sequential circuit; the state table is obtained from the state diagram. But in design of clocked
sequential circuit, the problem is defined in terms of state diagram or in set of statements.

9
 The state is represented by circle, with the state indicated inside the circle and directed
lines connecting the states indicated the transition between the states; when input is applied
and circuit is clocked. The binary numbers or variable inside the circle represent the state of
circle. The directed lines are labeled with single or two binary numbers separated by a symbol
‘/’. When directed lines are labeled by a single value. The single value shows the input value
that causes the state transition. When directed lines are labeled with two binary numbers.
The value before the symbol ‘/’ is the input value that causes the state transition and the value
after the symbol ‘/’ is the output value.
For example:

Consider design of clocked sequential circuit which generates the sequence 0 2 4 6 1 3

5 7, when input is ‘0’ and output is ‘1’ and circuit generates the sequence 7 5 3 1 6 4 2 0, when
input is 1 and the output is ‘0’. Fig. 5.114 shows the state diagram for the desired clock sequential
circuit.

Fig. 5.113 :State diagram for clock sequential circuit.

5.22.2 State table:
State table shows the output and next state of sequential logic circuit for all possible
combinations of present state and input(s). In analysis of clocked sequential circuit the state
table is obtained from the logic circuit and procedure is explained in section 5.20.1.
In design of clocked sequential circuit the state table is obtained from the state diagram.
For example:
a) The state table for the state diagram of Fig. 5.113 is given in table 5.66.

Table 5.66: state table for state diagram (Fig. 5.109)

10
 Next state Output
Present state
X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 0 1 0 1 1 1 1 0
0 0 1 0 1 1 1 1 0 1 0
0 1 0 1 0 0 0 0 0 1 0
0 1 1 1 0 1 0 0 1 1 0
1 0 0 1 1 0 0 1 0 1 0
1 0 1 1 1 1 0 1 1 1 0
1 1 0 0 0 1 1 0 0 1 0
1 1 1 0 0 0 1 0 1 1 0

b) The state table for the state diagram shown in Fig. 5.114 is given in table 5.67

Fig. 5.114: state diagram

The state table for the state diagram of Fig. 5.114 is shown in table 5.67.
Table 5.67: State table for state diagram (Fig. 5.114)
Next state Output
Present state
X=0 X=1 X=0 X=1
a d b 0 1
b e d 0 0
c c b 0 1
d c e 0 1
e e a 0 1

5.22.3 State Reduction:

The design procedure start with determination of number of flip-flops required. It is
dependents on number of state. Using the state reduction techniques we can reduce the
number of states. The state reduction technique avoids the redundancy of the states. For
11
purpose of state reduction we have to identify the equivalent state. The two states are said to
be equivalent; if the output(s) and next state are same for each input condition, Once the
equivalent state is found, one of them may be eliminated without altering the input and output
relations.
For Example:
Consider the state diagram of clocked sequential circuit as shown in Fig.5.115

Fig. 5.115 State diagram of clocked sequential circuit

The state table for the state diagram of Fig. 5.115 is shown in table 5.68
. Table 5.68: State table for state diagram (Fig. 5.115)
Next state Output
Present state
X=0 X=1 X=0 X=1
a c b 0 0
b d c 0 0
c g d 1 1
d e f 1 0
→e f a 0 1
f g f 1 0
→g f a 0 1
The states ‘e’ and ‘g’ are equivalent because the next state and outputs are same for the
input X is equal to 0 as well as X is equal to 1; and hence ‘g’ is replaced by ‘e’ and the state ‘g’
is removed from the table as shown in table 5.69

Table 5.69: State table with ‘g’ is replaced by ‘e’

12
 Next state Output
Present state
X=0 X=1 X=0 X=1
a c b 0 0
b d c 0 0
c (g)e d 1 1
→d e f 1 0
e f a 0 1
→f (g)e f 1 0
The states ‘d’ and ‘f’ are equivalent because the next state and output are same for the
input X is equal to 0 and X is equal to 1;and hence ‘f’ is replaced by ‘d’ and the state ‘f’ is
removed from the table as shown in table 5.70.

. Table 5.70: State table with ‘f’ is replaced by ‘d’

Next state Output
Present state
X=0 X=1 X=0 X=1
a c b 0 0
b d c 0 0
c e d 1 1
d e (f)d 1 0
e (f)d a 0 1
The state ‘c’ and ‘d’ are not equivalent because next state is same for input X is equal
to 0 and X is equal to 1, but outputs are not same.
5.22.4 State Assignment:
The clocked sequential circuit is defined in terms of present state next sate and output
for different input conditions. The input for flip-flops are calculated to get the desired next
state for the present state and input(s), hence there is need to specify the present state and
next state in terms of binary. If the present state and next state is specified by alphabets then
the binary values are assigned for the alphabets. Number of bits are used to assign the binary
value to alphabets is depends on number of alphabets used. If numbers of alphabets are M
then the n-bits are required to represent the alphabets in binary, such that 2 n  M. Selection
of value of n is as minimum as possible.
For example; the state table shown in table 5.70 includes the five alphabets and hence
number of bits required to represent the alphabets in binary is three. The assigned values for
the alphabets using three –bits are given below
Variable Assign value
a 000
b 001
c 010
13
 d 011
e 100

The value assigned to the alphabets may be any combination for desired length. Only
condition is that same value should not be assigned for more than one variable.
Example 5.20: Design the sequential circuit for the state diagram shown in Fig. 5.116 using
J-K flip-flops

Fig. 5.116: State diagram of sequential circuit

Solution: The state table which shows the present state, next state for input X = 0 and X = 1
and output for X = 0 and X = 1 given in a table 5.71.
Table 5.71: State table for state diagram (Fig. 5.116)
Next state Output
Present state
X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 1 1 0 0 0 1 0 1
0 0 1 0 1 0 1 0 0 0 1
0 1 0 0 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 1
1 1 0 1 0 0 0 1 0 0 1
State reduction:
From the state table; it is observed that all the states are different; there is no
possibility to reduce the state table.

14
 The excitation table for the given state diagram using J-K flip-flop is given in the table
5.72
Table 5.72: Excitation table for the state diagram(5.71) using J-K flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 Y J0 K0 J1 K1 J2 K2
0 0 0 0 1 1 0 0 0 X 1 X 1 X
0 0 1 0 0 1 0 0 X 1 1 X 0 X
0 1 0 0 0 1 0 0 0 X X 0 0 X
1 0 0 0 1 0 0 0 0 X 0 X X 0
1 1 0 0 1 0 0 0 0 X X 1 X 0
0 0 0 1 0 0 1 1 1 X 0 X 0 X
0 0 1 1 1 0 0 1 X 1 0 X 1 X
0 1 0 1 0 0 0 1 0 X X 1 0 X
1 0 0 1 0 0 1 1 1 X 0 X X 1
1 1 0 1 0 1 0 1 0 X X 0 X 1

15
The logic diagram for the given state table using J-K flip-flop is shown in Fig. 5.117

Fig. 5.113: Logic diagram for state table (fig.5.112) using J-K flip-flop
Example 5.21: With the help of state table and state diagram design a MOD 5 up/down
counter.
Solution:
The MOD-5 counter count 0-1-2-3-4 during the up counter; and in down counter it counts 4-
3-2-1-0. Let us consider X is an input signal, which control the direction of up/down counter.
When X = 0 circuit acts as an up counter and when X = 1 circuit acts as a down counter. The
state diagram is shown in Fig 5.118

16
 Fig. 5.118: State diagram of MOD- 5 up/down counter.
The state table which shows the present state, next state for input X = 0 and X = 1 given in a
table 5.73.
Table 5.73: State table of MOD- 5 up/down counter
Next state
Present state
X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 0 1 1 0 0
0 0 1 0 1 0 0 0 0
0 1 0 0 1 1 0 0 1
0 1 1 1 0 0 0 1 0
1 0 0 0 0 0 0 1 1

State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
The excitation table for the given state diagram using the J-K flip-flop is given in the
table 5.74.
Table 5.74: Excitation table for the state table (5.73) using J-K flip-flop
Present state Input Next state Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 J0 K0 J1 K1 J2 K2
0 0 0 0 0 0 1 1 X 0 X 0 X
0 0 1 0 0 1 0 X 1 1 X 0 X

17
0 1 0 0 0 1 1 1 X X 0 0 X
0 1 1 0 1 0 0 X 1 X 1 1 X
1 0 0 0 0 0 0 0 X 0 X X 1
0 0 0 1 1 0 0 0 X 0 X 1 X
0 0 1 1 0 0 0 X 1 0 X 0 X
0 1 0 1 0 0 1 1 X X 1 0 X
0 1 1 1 0 1 0 X 1 X 0 0 X
1 0 0 1 0 1 1 1 X 1 X X 1

18
The logic diagram for the given state diagram using J-K flip-flop is shown in Fig.5.19

Fig. 5.119: Logic diagram of MOD- 5 up/down counter using J-K flip-flop
Example 5.22: Design the clocked sequential circuit for the state diagram shown in Fig. 5.120
using J-K flip-flop.

Fig 5.120: state diagram of clocked sequential circuit

Solution:
The state table which shows the present state, next state for input X = 0 and X = 1 and
output for X = 0 and X = 1 given in a table E 5.8
State table for the state diagram of Fig 5.120 is shown in table 5.75.

19
 Table 5.75: State table for the State diagram (Fig 5.120)
Next state Output
Present state
X=0 X=1 X=0 X=1
a b a 0 0
b b c 0 0
c d a 0 0
d b c 0 1
State reduction:
The state ‘b’ and‘d’ are not equivalent because next state is the same for input X is
equal to 0 and X is equal to 1, but outputs are not same. From the state table it is observed
that all the states are different, there is no possibility to reduce the state table.
State Assignments:
The state table includes the four alphabets and hence number of bits required to
represent the alphabets in binary is two. The assign values for the alphabets using two–bits
are given below

State table for the state diagram of Fig 5.120 in binary is shown in table 5.76
Table 5.76: State table for the State diagram (Fig 5.120) in binary
Next state Output
Present state
X=0 X=1 X=0 X=1
Q1 Q0 Q1 Q0 Q1 Q0 Y Y
0 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
1 0 1 1 0 0 0 0
1 1 0 1 1 0 0 1
The excitation table for the given state diagram using J-K flip-flop is given in the table 5.77.
Table 5.77: Excitation table for the state table (5.76) using J-K flip-flop
Present Next Input of the flip-
Input Output
state state flops
20
 Q1 Q0 X Q1 Q0 Y J0 K0 J1 K1
0 0 0 0 1 0 1 X 0 X
0 1 0 0 1 0 X 0 0 X
1 0 0 1 1 0 1 X X 0
1 1 0 0 1 0 X 0 X 1
0 0 1 0 0 0 0 X 0 X
0 1 1 1 0 0 X 1 1 X
1 0 1 0 0 0 0 X X 1
1 1 1 1 0 1 X 1 X 0

Y = Q1Q0X
The logic diagram for the given state diagram using J-K flip-flop is shown in Fig. 5.121

21
 Fig. 5.121: Logic diagram for state diagram (fig.120) using J-K flip-flop
Example 5.23: Design a sequential generator to generate the sequence using T flip-flop
0→2→4→5→1→7→6
Solution:
State diagram for the given sequence is shown in Fig 5.122.

Fig. 5.122: State diagram for the given sequence

State table, which shows the present state, next state is given in table 5.78.
Table 5.78: State table for the State diagram( Fig 5.122)

Present state Next state

Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 1 0
0 1 0 1 0 0
1 0 0 1 0 1
1 0 1 0 0 1
0 0 1 1 1 1
1 1 1 1 1 0
1 1 0 0 0 0
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
22
 The excitation table for the given state diagram using the J-K flip-flop is given in the table
5.79

Table 5.79: Excitation table for the state table (5.78) using J-K flip-flop
Present state Next state Input of the flip-flops
Q2 Q 1 Q0 Q2 Q1 Q0 J0 K0 J1 K1 J2 K2
0 0 0 0 1 0 0 X 1 X 0 X
0 1 0 1 0 0 0 X X 1 1 X
1 0 0 1 0 1 1 X 0 X X 0
1 0 1 0 0 1 X 0 0 X X 1
0 0 1 1 1 1 X 0 1 X 1 X
1 1 1 1 1 0 X 1 X 0 X 0
1 1 0 0 0 0 0 X X 1 X 1

The
logic diagram for the given sequence using J-K flip-flop is shown in Fig. 5.123.

23
 Fig. 5.123: Logic diagram for state diagram (fig.122) using J-K flip-flop
Example 5. 24: Implement the following state diagram using
i) D –flip-flop ii) T-flip-flop iii) R-S flip-flop

Fig. 5.124: state diagram

Solution: Solution:
State table which shows the present state, next state for input X = 0 and X = 1 and output
for X = 0 and X = 1 given in a table 5.80.
Table 5.80: State table for the State diagram( Fig 5.124)
Next state Output
Present state
X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 1 1 0 0 0 1 0 1
0 0 1 0 1 0 1 0 0 0 1
0 1 0 0 1 0 0 0 0 0 1
1 0 0 1 0 0 0 0 1 0 1
1 1 0 1 0 0 0 1 0 0 1

24
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
i) Design using D-FF
The excitation table for the given state diagram using D flip-flop is given in the table 5.81

Table 5.81: Excitation table for the state table (5.80) using D flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 Y D0 D1 D2
0 0 0 0 1 1 0 0 1 1 0
0 0 1 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0
1 0 0 0 1 0 0 0 1 0 0
1 1 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 1 1 0 0 1
0 0 1 1 1 0 0 1 1 0 0
0 1 0 1 0 0 0 1 0 0 0
1 0 0 1 0 0 1 1 0 0 1
1 1 0 1 0 1 0 1 0 1 0

Q2Q1 Q2Q1
Q0X Q0X

25
The logic diagram for the given state table using D flip-flop is shown in Fig. 5.125.

Fig. 5.125: Logic diagram for state diagram (fig.120) using D flip-flop
ii) Design using T-FF
The excitation table for the given state diagram for the T flip-flop is given in the table 5.82

26
Table 5.82: Excitation table for the state table (5.80) using T flip-flop
Present state Input Next state Output Input of the flip-flops

Q2 Q1 Q0 X Q2 Q1 Q0 Y T0 T1 T2

0 0 0 0 1 1 0 0 0 1 1
0 0 1 0 0 1 0 0 1 1 0
0 1 0 0 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 1 1 1 0 0
0 0 1 1 1 0 0 1 0 0 1
0 1 0 1 0 0 0 1 1 1 0
1 0 0 1 0 0 1 1 1 0 1
1 1 0 1 0 1 0 1 1 0 1

27
The logic diagram for the given state table using T flip-flop is shown in Fig. 5.126

Fig. 5.126: Logic diagram for state diagram (fig.124) using T flip-flop
iii) Design using S-R FF
The excitation table for the given state diagram for the S-R flip-flop is given in the table 5.83
Table 5.83: Excitation table for the state table (5.80) using S-R flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 Y S0 R0 S1 R1 S2 R2
0 0 0 0 1 1 0 0 0 X 1 0 1 0
0 0 1 0 0 1 0 0 0 1 1 0 0 X
0 1 0 0 0 1 0 0 0 X X 0 0 X
1 0 0 0 1 0 0 0 0 X 0 X X 0
1 1 0 0 1 0 0 0 0 X 0 1 X 0
0 0 0 1 0 0 1 1 1 0 0 X 0 X
0 0 1 1 1 0 0 1 0 1 0 X 1 0
0 1 0 1 0 0 0 1 0 X 0 1 0 X
1 0 0 1 0 0 1 1 1 0 0 X 0 1
1 1 0 1 0 1 0 1 0 X X 0 0 1

28
29
The logic diagram for the given state table using S-R flip-flop is shown in Fig. 5.127.

Fig. 5.127: Logic diagram for state diagram (fig.124) using S-R flip-flop
Example 5.25: Design the circuit to generate the sequence 0→2→5→4→7
Solution: The state diagram for the given sequence is shown in Fig, 5.128.

30
Fig. 5.128: State diagram for the given sequence
State table of state diagram of fig.5.124 is given in table 5.84.
Table 5.84: State table for the State diagram (Fig 5.128)

Present state Next state

Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 1 0
0 1 0 1 0 1
1 0 1 1 0 0
1 0 0 1 1 1
1 1 1 0 0 0
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
The excitation table for the given state diagram using the J-K flip-flop is given in table 5.85
Table 5.85: Excitation table for the state table (5.84) using J-K flip-flop
Present state Next state Input of the flip-flops
Q2 Q1 Q0 Q2 Q1 Q0 J0 K0 J1 K1 J2 K2
0 0 0 0 1 0 0 X 1 X 0 X
0 1 0 1 0 1 1 X X 1 1 X
1 0 1 1 0 0 X 1 0 X X 0
1 0 0 1 1 1 1 X 1 X X 0
1 1 1 0 0 0 X 1 X 1 X 1

31
 The
logic diagram for the given sequence using J-K flip-flop is shown in Fig. 5.129

Fig. 5.129: Logic diagram for state diagram (fig.128) using J-K flip-flop
5.23 Lockout condition:
In example number 5.25 the clocked circuit is designed to generate the sequence
0→2→5→4→7→0, the states 1, 3 and 6 are the unused states. If by chance the sequence
generator to find it self in any one of the unused states, the next state is unknown. It may
possible that the sequence generator go from one unused state to another unused states, it
32
never arrive at the used state. The circuit is said to be locked. To avoid the condition of lockout,
there is need to design the circuit such that, when the circuit found in unused state the next
state should be known and it must be used state. The state diagrams of sequence generate to
generate the sequence 0→2→5→4→7→0 with lock out condition as shown in Fig. 5.130 and
Fig. 5.131.

Fig. 5.130: State diagrams of sequence generate to generate the sequence

0→2→5→4→7→0 with lock out condition
Fig. 5.131: State diagrams of sequence generate to generate the sequence
0→2→5→4→7→0 with lock out condition
when sequence generator found in unused states, the next state is used state ‘0 in Fig.
5.130’;and when sequence generator found in unused states, the next state is nearest used
state in Fig.5.131,. For example if unused state ‘1’, then next state is 2, if unused state 3, then
next state is 4 and for unused state 6 the next state is 7.
Example 5.26 : Design the sequence generator to generate the sequence 0→2→5→4→7 and
avoid the lockout condition using J-K flip-flops.
Solution:
The state diagram to generate the sequence 0→2→5→4→7 with avoid the lockout condition
using J-K flip-flops is shown in Fig. 5.132.

33
 Fig. 5.132: State diagram to generate the sequence 0→2→5→4→7 with avoid the
lockout condition using J-K flip-flops

The state table for the State diagram (Fig. 5.132) is given in table 5.86
Table 5.86: The state table for the State diagram (Fig. 5.132)

Present state Next state

Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 1 0
0 1 0 1 0 1
1 0 1 1 0 0
1 0 0 1 1 1
1 1 1 0 0 0
0 0 1 0 1 0
0 1 1 1 0 0
1 1 0 1 1 1
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
The excitation table for the given state table for the J-K flip-flop is given in the table
5.87
Table 5.87: Excitation table for the state table (5.86) using J-K flip-flop
Present state Next state Input of the flip-flops
Q2 Q1 Q0 Q2 Q1 Q0 J0 K0 J1 K1 J2 K2
0 0 0 0 1 0 0 X 1 X 0 X
0 1 0 1 0 1 1 X X 1 1 X
1 0 1 1 0 0 X 1 0 X X 0
1 0 0 1 1 1 1 X 1 X X 0
1 1 1 0 0 0 X 1 X 1 X 1
0 0 1 0 1 0 X 1 1 X 0 X
0 1 1 1 0 0 X 1 X 1 1 X
1 1 0 1 1 1 1 X X 0 X 0

34
The logic diagram for the given sequence using J-K flip-flop is shown in Fig.5.133

Fig. 5.133: Logic diagram for state diagram (fig.132) using J-K flip-flop

5.24 Sequence Generator:

The circuit which generates the desired sequence of bits in synchronous with a clock is
known as sequence generator. The basic block diagram of sequence generator is shown in Fig.
5.134.

35
 Fig. 5.134.: The basic block diagram of sequence generator
For the design of sequence generator first calculate the number of flip-flops required and
then design the next state decoder to generate the desired sequence. The procedure to design
the sequence generator is
1. Find the minimum number of flip-flops required.
The minimum number of flip-flops required is depends on the nature of
sequence. The required number of flip-flops is calculated from the equation
Max (C0, C1)  2n-1
Where n is number of flip-flops required, C0 is the count of ‘0’ in the given
sequence and C1 is the count of ‘1’ in the given sequence.
2. Draw the state table as per the following procedure.
a).Assign the desired sequence (start from LSB) to the output of the flip-flops, which
produces the output.
b).Assign the output to the other flip-flops 0 or 1, such that all the states are
different.
3. Draw the state diagram from the state table.
4. Prepared the excitation table on the basis of present state and next state.
5. Draw the K-map and simplify the same.
6. Draw the logic diagram.
For example:
Suppose we have to design the sequence generator to generate the sequence
11001011.
Number of ‘1’s in the sequence is five (C1 = 5)
Number of ‘0’s in the sequence is three (C0 = 3)

36
 Max (3,5)  2n-1
5  2n-1
n=4
The state table to generate the desired sequence is given in table 5.88
Table 5.88: State table to generate the sequence 11001011

Q3 Q2 Q1 Q0 State
0 0 0 1 1
0 0 1 1 3
0 0 0 0 0
0 1 0 1 5
0 1 0 0 4
0 0 1 0 2
0 1 1 1 7
1 0 0 1 9

The desired sequence (start from LSB) is assigned under the column of Q 0 and the
value of Q3, Q2 and Q1 are assigned as ‘0’ or ‘1’ such that all the state gets different values.
For the above state table the state diagram is shown in Fig. 5.131

Fig. 5.135: state diagram for state table (table 5.88)

Excitation table which shows the present state, next state and possible inputs of the flip-flops
is shown in Table 5.89
Table 5.90: Excitation table for the state diagram (Fig. 5.135) using J-K flip-flop
Present state Next state Input Of Flip-flops
Q3 Q2 Q 1 Q0 Q3 Q2 Q1 Q0 J0 K0 J1 K1 J2 K2 J3 K3
0 0 0 1 0 0 1 1 X 0 1 X 0 X 0 X
0 0 1 1 0 0 0 0 X 1 X 1 0 X 0 X
0 0 0 0 0 1 0 1 1 X 0 X 1 X 0 X
0 1 0 1 0 1 0 0 X 1 0 X X 0 0 X
0 1 0 0 0 0 1 0 0 X 1 X X 1 0 X
37
 0 0 1 0 0 1 1 1 1 X X 0 1 X 0 X
0 1 1 1 1 0 0 1 X 0 X 1 X 1 1 X
1 0 0 1 0 0 0 0 X 1 X 0 0 X X 1

Q3Q2
Q1Q0

38
The logic diagram to generate the given sequence is shown in Fig. 5.136

Fig. 5.136: Logic diagram to generate the sequence 11001011

Example 5.27: Design the sequence generator to generate the sequence using D flip-flop.
………… 101100110………..
Solution:
Given sequence is ………… 101100110………..
Number of ‘1’s in the sequence is five (C1 = 5)
Number of ‘0’s in the sequence is four (C0 = 4)
Max (4,5)  2n-1
5  2n-1
n=4
The state table to generate the desired sequence is given in table 5. 91
Table 5.91: State table to generate the sequence 101100110
Q3 Q2 Q1 Q0 State
0 0 0 0 0
0 0 1 1 3
0 0 0 1 1
0 1 0 0 4
0 1 1 0 6
0 1 1 1 7
1 0 0 1 9
1 0 0 0 8
0 1 0 1 5

The desired sequence (start from LSB) is assigned under the column of Q 0 and the
value of Q3, Q2 and Q1 are assigned as ‘0’ or ‘1’ such that all the state have different values.
The state diagram for the above state table is shown in Fig.5.137

39
 Fig. 5.137: state diagram for state table (table 5.91)
Excitation table which shows the present state, next state and possible inputs of the
flip-flops is shown in Table 5.92
Table 5.92: Excitation table for the state diagram (Fig. 5.137)
using D flip-flop
Present state Next state Input Of Flip-flops
Q3 Q2 Q1 Q0 Q3 Q2 Q 1 Q0 D0 D1 D2 D3
0 0 0 0 0 0 1 1 1 1 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0 0 0 1 0
0 1 0 0 0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 1 1 1 1 0
0 1 1 1 1 0 0 1 1 0 0 1
1 0 0 1 1 0 0 0 0 0 0 1
1 0 0 0 0 1 0 1 1 0 1 0
0 1 0 1 0 0 0 0 0 0 0 0

40
The logic diagram to generate the given sequence is shown in Fig. 5.138.

Fig. 5.138: Logic diagram to generate the sequence 101100110

5.25 Sequence Detector
The sequence detector is logic circuit, which detects the desired sequence. The
procedure to detect the desired sequence is
1. Draw the state diagram for the desired sequence. The procedure to draw the state
diagram is explained in example.
2. Draw the state table from the state diagram.
3. Fine the required number of flip-flops.
4. Draw the excitation table for the state table.
5. Draw the K-map and simplify the same.
6. Draw the logic diagram.
For example:
Design the sequence detector to detect the sequence 101011.
The number of states of state diagram is equal to the number of bits of desired
sequence. In given sequence number of the bits is six and therefore numbers of states are six.
The state diagram for the correct sequence is shown in Fig. 5.135. The states of the state
diagram are defined by the alphabets a, b, c, d, e and f. The output will be considered as ‘0’
when the complete correct sequence is not detected. Once detector detects the correct sequence
the output becomes ‘1’.

41
 Fig. 5.139: State diagram for the correct sequence 101011.
Present State a:
The initial state is ‘a’. When input is ‘1’ then output is ‘0’ and next state is ‘b’, because
the first bit of the desired sequence is ‘1’. If the input is ‘0’ then output must be ‘0’ and next
state is ‘a’.

Fig. 5.140
Present State b:
When input is ‘1’ the next state is ‘c’ and output is ‘0’, because the second bit of the
sequence is correct (11). When input is ‘0’, the output is ‘0’ and next state is ‘a’ because the
second bit of the sequence is wrong.

Fig. 5.141
Present state c:
When input is ‘0’, the next state is‘d’ and output is ‘0’ because the third bit of the
sequence is correct. When input is ‘1’, the third bit is not correctly detected, but there is no
need to go to the initial state ‘a’. We assume that the first bit is wrong and third bit is correct,
111, we considered 11 and hence next state is ‘b’ and output is ‘0’.
42
 Fig. 5.142
Present state d:
When input is ‘1’, the next state is ‘e’ and output is ‘0’, because fourth bit of sequence
is correctly detected, when input is ‘0’ the fourth bit is wrong and next state must be ‘a’ and
output is ‘0’ because whole sequence is wrong.

Fig. 5.143
Present state e:
When input is ‘0’, the next state is ‘f’ and output is ‘0’, because the fifth bit is correctly
detected. When input is ‘1’ the next state is ‘c’. The sequence 11011 will be treated as 1 1 and
output is ‘0’.

Fig. 5.144
Present state f:
When input is ‘1’, the next state is ‘a’ and output is ‘1’, because last bit of sequence is
correctly detected, when input is ‘0’ the last bit is wrong and next state must be ‘a’ and output
is ‘0’ because whole sequence is wrong.
43
 Fig. 5.145
State table:
The state table for the state diagram of Fig. 5.141is given in table 5.93.
Table 5.93: State table for state diagram (Fig. 5.141)
Next state Output
Present state
X=0 X=1 X=0 X=1
A a b 0 0
B a c 0 0
C d b 0 0
D a e 0 0
E f c 0 0
F a a 0 1

State reduction:
From the state table; it is observed that all the states are different, there is no
possibility to reduce the state table.
State Assignment:
The state table shown in table 5.93 includes the six alphabets and hence number of
bits required to represent the alphabets in binary is three. The assigned values for the
alphabets using three-bits are given below

The state table which shows the present state, next state for input X = 0 and X = 1 and
output for X = 0 and X = 1 given in a table 5.94
44
 Table 5.94: State table for state diagram (Fig. 5.145) in binary
Next state Output
Present state
X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0 0
0 1 0 0 1 1 0 0 1 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 1 0 1 0 1 0 0 0
1 0 1 0 0 0 0 0 0 0 1

The excitation table for the given state diagram for the J-K flip-flop is given in the table 5.95
Table 5.95: Excitation table for state table (Table 5.94) using J-K flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 Y J0 K0 J1 K1 J2 K2
0 0 0 0 0 0 0 0 0 X 0 X 0 X
0 0 1 0 0 0 0 0 X 1 0 X 0 X
0 1 0 0 0 1 1 0 1 X X 0 0 X
0 1 1 0 0 0 0 0 X 1 X 1 0 X
1 0 0 0 1 0 1 0 1 X 0 X X 0
1 0 1 0 0 0 0 0 X 1 0 X X 1
0 0 0 1 0 0 1 0 1 X 0 X 0 X
0 0 1 1 0 1 0 0 X 1 1 X 0 X
0 1 0 1 0 0 1 0 1 X X 1 0 X
0 1 1 1 1 0 0 0 X 1 X 1 1 X
1 0 0 1 0 1 0 0 0 X 1 X X 1
1 0 1 1 0 0 0 1 X 1 0 X X 1

45
The logic diagram for the given state table using J-K flip-flop is shown in Fig. 5.146.

46
 Fig. 5.146: Logic diagram for the sequence (101011) detector
Example 5.28: Design and implement the following sequence detector using clock sequence
circuit a) using R-S FF.
…… 1 1 0 1 0 1 1 ……
Solution:
In given sequence; number of the bits is seven and therefore numbers of states are
seven. The state diagram for the correct sequence is shown in Fig. 5.143.The states of the state
diagram are define by the alphabets a, b, c, d, e, f and g. The output will be considered as ‘0’
when the complete correct sequence is not detected. Once detector, detects the complete correct
sequence the output becomes ‘1’.

Fig. 5.147: State diagram for the correct sequence 1 1 0 1 0 1 1.

Present State a:
When input is ‘1’then output is ‘0’ and next state is ‘b’, because the first bit of the desired
sequence is ‘1’. If the input is ‘0’, then output must be ‘0’ and next state is ‘a’.

47
 Fig. 5.148:
Present State b:
When input is ‘1’ the next state is ‘c’ and output is ‘0’, the second bit (11) of the sequence
is correct. When input is ‘0’, the output is ‘0’ and next state is ‘a’; because detected second bit
of the sequence is wrong.

Fig. 5.149:
Present state c:
When input is ‘0’, then next state is‘d’ and output is ‘0’; because the third bit of the
sequence is correct. When input is ‘1’, the third bit of the sequence is not correctly detected,
but there is no need to go to the initial state ‘a’. We assume, the first bit is wrong and third bit
is correct, 111, we considered 11 and hence next state is ‘b’ and output is ‘0’.

Fig. 5.150:
Present state d:
When input is ‘1’, the next state is ‘e’ and output is ‘0’, because fourth bit of sequence
is correctly detected, when input is ‘0’ the fourth bit of the sequence is wrong and next state
must be ‘a’ and output is ‘0’ because whole sequence is wrong.

48
 Fig. 5.151:
Present state e:
When input is ‘0’, the next state is ‘f’ and output is ‘0’, because the fifth bit is correctly
detected. When input is ‘1’ the next state is ‘c’. The sequence 11011 will be treated as 1 1 and
output is ‘0’.

Fig. 5.152:
Present state f:
When input is ‘1’, the next state is ‘g’ and output is ‘1’, because sixth bit of the sequence
is correctly detected, when input is ‘0’ the sixth bit of the sequence is wrong and next state
must be ‘a’ and output is ‘0’ because whole sequence is wrong.

Fig. 5.153:
Present state g:

49
 When input is ‘1’, the next state is ‘a’ and output is ‘1’, because last bit of sequence is
correctly detected. When input is ‘0’ the last bit of the sequence is wrong and next state must
be ‘a’ and output is ‘0’ because whole sequence is wrong.

Fig. 5.154:
State table:
The state table for the state diagram of Fig5.154 is shown in table 5.96
Table 5.96: State table for state diagram (Fig. 5.154)
Next state Output
Present state
X=0 X=1 X=0 X=1
a a b 0 0
b a c 0 0
c d b 0 0
d a e 0 0
e f c 0 0
f a g 0 0
g a a 0 1
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
State Assignment:
The state table shown in table 5.96 includes the seven alphabets and hence number of
bits required to represent the alphabets in binary is three. The assigned values for the
alphabets using three-bits are given below

50
The state table which shows the present state, next state for input X = 0 and X = 1 and output for
X = 0 and X = 1 given in a table 5.97
Table 5.97: State table for state diagram (Fig. 5.150) in binary
Next state Output
Present state
X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0 0
0 1 0 0 1 1 0 0 1 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 1 0 1 0 1 0 0 0
1 0 1 0 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 0 0 1
The excitation table for the given state diagram using S-R flip-flop is given in the table 5.98
Table 5.98: Excitation table for state table (Table 5.97) using J-K flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q 0 X Q2 Q1 Q0 Y S0 R0 S1 R1 S2 R2
0 0 0 0 0 0 0 0 0 X 0 X 0 X
0 0 1 0 0 0 0 0 0 1 0 X 0 X
0 1 0 0 0 1 1 0 1 0 X 0 0 X
0 1 1 0 0 0 0 0 0 1 0 1 0 X
1 0 0 0 1 0 1 0 1 0 0 X X 0
1 0 1 0 0 0 0 0 0 1 0 X 0 1
1 1 1 0 0 0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 1 0 1 0 0 X 0 X
0 0 1 1 0 1 0 0 0 1 1 0 0 X
0 1 0 1 0 0 1 0 1 0 0 1 0 X
0 1 1 1 1 0 0 0 0 1 0 1 1 0
1 0 0 1 0 1 0 0 0 X 1 0 0 1
1 0 1 1 1 1 1 0 X 0 1 0 X 0
1 1 1 1 0 0 0 1 0 1 0 1 0 1

51
The logic diagram for the given state table using S-R flip-flop is shown in Fig. 5.155

52
 Fig. 5.155: Logic diagram for the sequence (101011) detector

Example 5.29: Design and implement the following sequence detector using clock sequence
circuit using D FF.
…… 1 1 0 1 0 0 1 ……
Solution:
In given sequence, number of the bits is seven and therefore numbers of states are
seven. The state diagram for the correct sequence is shown in Fig5.156 .The states of the state
diagram are define by the alphabets a, b, c, d, e, f and g. The output will be considered as ‘0,’
when the complete correct sequence is not detected. Once detector detects the complete correct
sequence the output becomes ‘1’.

Fig. 5.156: State diagram for the correct sequence …… 1 1 0 1 0 0 1 ……

53
Present State a:
When input is ‘1’ then output is ‘0’, and next state is ‘b’; because the first bit of the
desired sequence is ‘1’. If the input is ‘0’; then output must be ‘0’ and next state is ‘a’.

Fig. 5.157:
Present State b:
When input is ‘0’ the next state is ‘c’ and output is ‘0’, because the second bit of the
sequence is correct. When input is ‘1’, the output is ‘0’ and next state is ‘b,’ because second bit
is not correctly detected, but there is no need to go to the initial state ‘a’. We assume that the
first bit is wrong and second bit is correct first bit, 11, we considered 1 and hence next state is
‘b’ and output is ‘0’.

. Fig. 5.158:
Present state c:
When input is ‘0’, the next state is‘d’ and output is ‘0’ because the third bit of the
sequence is correct. When input is ‘1’, the third bit is not correctly detected, but there is no
need to go to the initial state ‘a’. We assume that the first bit is wrong and third bit is correct,
101, we considered 1 and hence next state is ‘b’ and output is ‘0’.

Fig. 5.159:
Present state d:

54
 When input is ‘1’, the next state is ‘e’ and output is ‘0’, because fourth bit of the
sequence is correctly detected. When input is ‘0’, the fourth bit is wrong and next state must
be ‘a’ and output is ‘0’; because whole sequence is wrong.

Fig. 5.160:
Present state e:
When input is ‘0’, the next state is ‘f’ and output is ‘0’, because the fifth bit is correctly
detected. When input is ‘1’ the next state is ‘b’. The sequence 11001 will be treated as 1 and
output is ‘0’.

Fig. 5.161:
Present state f:
When input is ‘1’, the next state is ‘g’ and output is ‘1’, because sixth bit of the sequence
is correctly detected. When input is ‘0’ then sixth bit of the sequence is wrong and next state
must be‘d’ and output is ‘0’. The sequence 001001 will be treated as 001 and output is ‘0’.

Fig. 5.162:
Present state g:
55
 When input is ‘1’, the next state is ‘a’ and output is ‘1’, because last bit of sequence is
correctly detected. When input is ‘0’ the last bit is wrong and next state must be ‘c’ and output
is ‘0’. The sequence 0101001 will be treated as 01 and output is ‘0’.

Fig. 5.163:
State table:
The state table for the state diagram of Fig.5.159 is shown in table 5.99.
Table 5.99: State table for state diagram (Fig. 5.163)
Next state Output
Present state
X=0 X=1 X=0 X=1
a a b 0 0
b c b 0 0
c d b 0 0
d a e 0 0
e f b 0 0
f d g 0 0
g c a 0 1
State reduction:
From the state table it is observed that all the states are different, there is no
possibility to reduce the state table.
State Assignment:
The state table shown in table 5.99 includes the seven alphabets and hence number of
bits required to represent the alphabets in binary is three. The assigned values for the
alphabets using three-bits are

56
 The state table which shows the present state, next state for input X = 0 and X = 1 and
output for X = 0 and X = 1 given in a table 5.100
Table 5.100: State table for state diagram (Fig. 5.163) in binary
Next state Output
Present state X=0 X=1 X=0 X=1
Q2 Q1 Q0 Q2 Q1 Q0 Q2 Q1 Q0 Y Y
0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 1 0 0 0 1 0 0
0 1 0 0 1 1 0 0 1 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 1 0 1 0 0 1 0 0
1 0 1 0 1 1 1 1 1 0 0
1 1 1 0 1 0 0 0 0 0 1
Table E 5.15 (b)
Excitation table: The excitation table for the given state diagram for the D flip-flop is given
in the table5.101
Table 5.101: Excitation table for state table (Table 5.100) using D flip-flop
Present state Input Next state Output Input of the flip-flops
Q2 Q1 Q0 X Q2 Q1 Q0 Y D0 D1 D2
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 1 0
0 1 0 0 0 1 1 0 1 1 0
0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 1 0 1
1 0 1 0 0 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 0
0 0 0 1 0 0 1 0 1 0 0
0 0 1 1 0 0 1 0 1 0 0
0 1 0 1 0 0 1 0 1 0 0
0 1 1 1 1 0 0 0 0 0 1
1 0 0 1 0 0 1 0 1 0 0
1 0 1 1 1 1 1 0 1 1 1
1 1 1 1 0 0 0 1 0 0 0

57
The logic diagram for the given state table using D flip-flop is shown in Fig.5.64.

Fig. 5.160: Logic diagram for the sequence (1 1 0 1 0 0 1 ) detector

58
5.27 EXERCISE

59
OBJECTIVE TYPE QUESTION
Select the correct alternative :
1. By placing an inverter between both inputs of an S-R flip-flop, it becomes .......
(a) J-K (b) D
(c) T (d) Master slave J-K flip-flop
2. The output Qn of a J-K flip-flop is zero. It changes to 1 when a clock pulse is applied.
The inputs Jn and Kn are respectively .......
(a 1 and X (b) 0 and X
(c) X and 0 (d) X and 1 (X-Don’t care )
3. The characteristic equation of the T-flip-flop is given by .......
+ – – + – –
(a) Q = T Q + TQ (b) Q = TQ + QT
+ + –
(c) Q = TQ (d) Q = TQ
4. An R-S latch is a .......
(a) combinational circuit (b) synchronous sequential circuit
(c) one bit memory element (d) one clock delay element
5. A Mod-2 counter followed by a Mod-5 counter is ........
60
 (a) Same as a Mod-5 counter followed by a Mod-2 counter.
(b) a decade counter
(c) Mod-7 counter
(d) none of the above.
6. A 4-bit modulo-16 ripple counter uses J-K flip-flop.If the propagation delay of each
flip-flop is 50 ms, the maximum clock frequency is equal to .......
(a) 20 MHz (b) 10 MHz
(c) 5 MHz (d) 4 MHz
7. A pulse train with a frequency of 1 MHz is counted using a modulo 1024 ripple-counter
built with J-K flip-fop. For proper operation of the counter the maximum permissible
propagation delay per flip-flop stage is .......... ns.
(a) 100 (b) 50 (c) 20 (d) 10
8. The Q-output of J-K flip-flop is “1”. The output does not change when a clock-pulse is
applied. The inputs J and K will be respectively .......... (where ’X’-don’t care state)
(a) 0 and X (b) X and 0 (c) 1 and 0 (d) 0 and 1
9. A divide by 78 counters can be realized by using .......
(a) 6 numbers of mod-13 counters
(b 13 numbers of mod-6 counters
(c) one mod-13 counter followed by one mod-6 counter
(d) 13 numbers of mod-13 counters.
10. In sequential circuits, their outputs at any instant of time depends ........
(a) only on the inputs present at that instant of time.
(b) on past output as well as present inputs.
(c) only on the past inputs.
(d) only on the past outputs.
12. A ring counter is same as
(a) up-down counter (b) parallel counter
(c) shift registers (d) none of these
13. The number of flip-flops are required to build a mod-15 counter is ........
(a) 4 (b) 5 (c) 6 (d) 7
14. How many flip-flops are required for dividing the frequency by 64?
(a) 4 (b) 5 (c) 6 (d) 8
15. An n-stage ripple counter can count upto ........
n n n–1
(a) 2 (b) 2 – 1 (c) n (d) 2
Answers :
1. (b) 2. (a) 3. (b) 4. (c) 5. (b)
6. (c) 7. (a) 8. (a) 9. (b) 10. (b)
12. (c) 13. (a) 14. (c) 15. (b)

61