

CS302 
Digital Logic & Design
Lesson
No. 32
D FLIPFLOP
BASED IMPLEMENTATION
FlipFlop
Transition Table
To implement
the counter using D
flipflops instead of JK
flipflops, the D
transition
table is
used. The D flipflop only
has a single input and
the output of the D
flipflop follows the
input.
The D flipflop transition
table is shown. Table
32.1
Flipflop
Output
Inputs
Transitions
D
Qt+1
1
1
0
0
Table
32.1
D flipflop
Transition table
Karnaugh
Maps
The D
input table is shown in
table 32.2. The Karnaugh
maps for the input
expressions
are
also derived from the
input table.
Present
State
Next
State
D flipflop
inputs
Q2
Q1
Q0
Q2
Q1
Q0
D2
D1
D0
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
Table
32.2
D flipflop
input table
Q2Q1/Q0
0
1 Q2Q1/Q0
0
1
Q2Q1/Q0
0
1
00
0
1
00
1
0
00
0
0
01
1
0
01
1
0
01
0
1
11
1
0
11
1
0
11
1
0
10
0
1
10
1
0
10
1
1
D 2 = Q 2 ⊕Q1Q 0
D1 = Q 0 ⊕Q1
D0 = Q0
Table
32.3
Karnaugh Map
for D2, D1 and
D0 inputs
Logic
expressions for Flipflop
Inputs
Simplified
expressions for D2, D1 and D0
are
obtained from the Karnaugh
maps. The
expressions
are shown along with
the Karnaugh maps.
327
CS302 
Digital Logic & Design
Sequential
Circuit Implementation
The
first D flipflop is connected to
toggle at each clock
transition. The second
flipflop
sets
its output depending on the
D input. The input to the
second flipflop is determined by
the
expression
D1 = Q 0 ⊕Q1 , thus at
intervals t1, t4, t5 and t8 the input D1 is at logic 1 therefore
on
the
clock transition the output
Q1 is also set to
logic 0. At intervals t2, t3, t6 and
t7 the output
Q1
is set to
logic 1 as the input D1 is at logic 1. The input to
the second flipflop is
determined by
the
expression D
2 = Q 2 ⊕Q1Q 0 , thus at
intervals t1, t2, t3 and t8 the output Q2 is set to 0 as D2
input is at
logic 0. At intervals t4, t5, t6 and
t7 the output
Q2 is set to logic 1
as D2 input is at
logic
1. Figure
32.1
Figure
32.1a D flipflop based
implementation of 3bit Synchronous
Counter
Figure
32.1b Timing diagram of the
D flipflop based 3bit
Synchronous Counter
Implementing a
3bit Up/Down
Counter
328
CS302 
Digital Logic & Design
7. State
Diagram
The
state diagram of a 3bit
Up/Down Synchronous Counter is
shown in the figure.
32.2.
X=0 and X =1 indicates that
the counter counts up when
input X = 0 and it counts
down
when X
=1. X is used as input
variable to configure the
counter as up or down
counter.
Figure
32.2
State
diagram of a 3bit
UpCounter
8. NextState
Table
The
next state is the state to
which the sequential circuit
switches when a clock
transition
occurs. Table 32.4. The
next state outputs for
X=0 and X=1 are
shown separately.
Present
State
Next
State X=0
Next
State X=1
Q2
Q1
Q0
Q2
Q1
Q0
Q2
Q1
Q0
0
0
0
0
0
1
1
1
1
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
1
0
1
0
1
1
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
0
0
1
1
0
Table
32.4
NextState
Table for a 3bit
UpCounter
9. Flipflop
Transition Table
The
flipflop transition table is
based on the JK flipflop.
Table 32.5
Flipflop
Inputs
Output
Transitions
J
K
Qt
Qt+1
0
x
0
0
1
x
0
1
329
CS302 
Digital Logic & Design
x
1
1
0
x
0
1
1
Table
32.5
JK
flipflop Transition
table
10.
Karnaugh Maps
The
JK flipflop inputs when
state variables change when
X=0 and X=1 are
shown in
the
table 32.6. The JK
inputs can be directly
mapped to 4Variable Karnaugh
maps. Table
32.7
Present
State
Next
State X=0
JK
flipflop inputs
Q2
Q1
Q0
Q2
Q1
Q0
J2
K2
J1
K1
J0
K0
0
0
0
0
0
1
0
x
0
x
1
x
0
0
1
0
1
0
0
x
1
x
x
1
0
1
0
0
1
1
0
x
x
0
1
x
0
1
1
1
0
0
1
x
x
1
x
1
1
0
0
1
0
1
x
0
0
x
1
x
1
0
1
1
1
0
x
0
1
x
x
1
1
1
0
1
1
1
x
0
x
0
1
x
1
1
1
0
0
0
x
1
x
1
x
1
Table
32.6a JK flipflop
input table for
X=0
Present
State
Next
State X=1
JK
flipflop inputs
Q2
Q1
Q0
Q2
Q1
Q0
J2
K2
J1
K1
J0
K0
0
0
0
1
1
1
1
x
1
x
1
x
0
0
1
0
0
0
0
x
0
x
x
1
0
1
0
0
0
1
0
x
x
1
1
x
0
1
1
0
1
0
0
x
x
0
x
1
1
0
0
0
1
1
x
1
1
x
1
x
1
0
1
1
0
0
x
0
0
x
x
1
1
1
0
1
0
1
x
0
x
1
1
x
1
1
1
1
1
0
x
0
x
0
x
1
Table
32.6b JK flipflop
input table for
X=1
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
x
x
x
x
00
0
1
0
0
01
x
x
x
x
01
0
0
0
1
11
0
0
0
1
11
x
x
x
x
10
0
1
0
0
10
x
x
x
x
J0 = 1
K0 = 1
Table
32.7a
Karnaugh Map
for J2 and K2 inputs
Q2Q1/Q0X
00
01
11
10
330
CS302 
Digital Logic & Design
Q2Q1/Q0X
00
01
11
10
00
0
1
0
1
00
x
x
x
x
01
x
x
x
x
01
0
1
0
1
11
x
x
x
x
11
0
1
0
1
10
0
1
0
1
10
x
x
x
x
J1 = Q 0 X + Q 0 X
K1 = Q0 X + Q0 X
Table
32.7b
Karnaugh Map
for J1 and K1 inputs
Q2Q1/Q0X
00
01
11
10
Q2Q1/Q0X
00
01
11
10
00
x
x
1
1
00
1
1
x
x
01
x
x
1
1
01
1
1
x
x
11
x
x
1
1
11
1
1
x
x
10
x
x
1
1
10
1
1
x
x
J2 = Q1Q 0 X + Q1 Q 0 X
K 2 = Q1Q 0 X + Q1 Q 0 X
Table
32.7c
Karnaugh Map
for J0 and K0 inputs
11.
Logic expressions for
Flipflop Inputs
Simplified
expressions for J2K2, J1K1 and
J0K0 are
directly obtained from
the
Karnaugh
maps. The expressions are
shown along with the
Karnuagh maps.
12.
Sequential Circuit
Implementation
The
Boolean expressions obtained in
the previous step are
implemented using
logic
gates.
The sequential circuit
implemented is shown in figure
32.3
X=0
(up)
Q0
Q1
Q2
X=1
(down)
1
SET
SET
SET
J
Q
J
Q
J
Q
flipflop
2
flipflop
1
flipflop
3
K
Q
K
Q
K
Q
CLR
CLR
CLR
CLK
Figure
32.3
Implementation
of the Sequential
Circuit
331
CS302 
Digital Logic & Design
State
Reduction
A state
diagram show the sequence of
current and next states
through which the
state
machine
sequences. Figure 32.4. The
transition from a current
state to the next state
is
determined by
current state and the
inputs. The outputs of the
state machine may also
change
during
the transition from the
current state to the next
state. The outputs may
depend only on
the
current state (Moore
Machine) or a combination of current
state and the inputs
(Mealy
Machine). It is
possible that two or more
states are equivalent. Two
states are considered
equivalent if
for the same set of
inputs the states change to
the same next state or
equivalent
next
states and give identical
outputs. If equivalent states
exist then one of the
equivalent state
is removed.
Reduction in the number of
state results in fewer
flipflops and a simpler
circuit.
1/0
0/1
a
0/0
b
e
0/0
0/0
1/1
1/0
f
1/1
c
1/0
0/1
1/1
0/0
d
0/0
g
1/0
Figure
32.4
State
diagram
Reduction in
the number of states is
possible if one is interested
only in the input
and
output
relationship, that is, input
and outputs remain
unchanged. When external
outputs are
taken
directly from flipflops,
the output must be
independent of the number of
states before
state
reduction algorithms are
applied. Consider the
sequence a, b, c, f, d, d, e, g, e, g, d, e, a,
f, d, e, a
starting from the initial
state a. The inputs and
the corresponding outputs
are shown
in the
table. Table 32.8
state
a
b
c
f
d
d
e
g
d
e
a
f
d
e
a
Input
1
1
1
0
1
0
1
0
0
0
0
0
0
0
Output
0
1
1
0
0
1
1
0
1
0
0
0
1
0
Table
32.8
The
input and output
sequence
In the
next state table the
state `f' is equivalent to state
`g' as for each set of
inputs
states `f'
and `g' change to states
`d' and `e' respectively.
Table 32.9a. Similarly, the
outputs
also
remain identical. Therefore
state `g' can be eliminated
and in the state table
all instances
of state
`g' are replaced by state
`f'.
332
CS302 
Digital Logic & Design
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
a
f
b
0
0
b
b
c
1
1
c
a
f
0
1
d
e
d
1
0
e
a
g
0
1
f
d
e
0
0
g
d
e
0
0
Table
32.9a
NextState
table
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
a
f
b
0
0
b
b
c
1
1
c
a
f
0
1
d
e
d
1
0
e
a
f
0
1
f
d
e
0
0
Table
32.9b
Next
State table, with state
`g' eliminated and instances
of state `g' replaced
by
state
`f'
In the
next state table state
`c' is equivalent to state
`e' as for each input,
the current
state
changes to the same next
states. Table 32.9b. The
outputs are also identical
when
changing
from the present state to
the next state. The
state table is simplified by
eliminating
state e
and replacing all instances
of state `e' with state `c'.
table 32.9c. The State
diagram
represented by
the simplified state table
is shown. Figure
31.7.
Present
Next
State
Output
State
X=0
X=1
X=0
X=1
a
f
b
0
0
b
b
c
1
1
c
a
f
0
1
d
c
d
1
0
f
d
c
0
0
Table
32.9c
Next
State table, with state
`e' eliminated and instances
of state `e' replaced
by
state
`c'
333
CS302 
Digital Logic & Design
1/0
0/1
a
b
0/0
0/0
1/1
1/0
f
1/1
c
0/0
0/1
d
1/0
Figure
32.5
Simplified
State diagram
Reconsider
the initial sequence a, b, c, f, d, d, e,
g, e, g, d, e, a, f, d, e, a starting
from
the
initial state a. The inputs
and outputs for the
state sequence derived from
the simplified
State
diagram are shown in table
32.10.
state
a
b
c
f
d
d
c
f
d
c
a
f
d
c
a
Input
1
1
1
0
1
0
1
0
0
0
0
0
0
0
Output
0
1
1
0
0
1
1
0
1
0
0
0
1
0
Table
32.10
The
input and output sequence
obtained from the simplified
state diagram
Elimination of
equivalent states results in
the reduction in the number
of flipflops. In
the
example described, the
elimination of two states
reduces the total number of
unique states
from
seven to five, however the
number of flipflops remain
the same which is three. If
the
number of
states had been reduced to
four then only two
flipflops would be
required.
334
Table of Contents:

