Multiplexors

Sequential Circuits and

Finite State Machines
Prof. Sin-Min Lee
Department of Computer Science
 Two-Level NAND Gate Implementation
Example 1  
 Two-Level NAND Gate Implementation

Example 1  
 Design Procedure

• Determine the required number of inputs and

outputs and assign letter symbols to them.
• Derive the truth table that defines the required
relationship between inputs and outputs.
• Obtain the Boolean function.
• Draw the logic diagram.
• Verify the correctness of the design.
 Example
• Design a circuit that converts a BCD
codeword to its corresponding excess-3
codeword. We need 4 input variables and
4 output variables. Let us designate the 4
input binary variables by the symbols A, B,
and C and D, and the four output variables
by w, x, y, and z. The truth table relating
the input and output variables is shown
below:
Note that the outputs for inputs 1010 through 1111 are don't care.
 Two-Lvel NOR Gate Implementation

Example 2  
e
 Multiplexers
• A combinational circuit that selects info
from one of many input lines and directs it
to the output line.
• The selection of the input line is controlled
by input variables called selection inputs.
• They are commonly abbreviated as
“MUX”.
 Combinational circuit
implementation using MUX
• We can use Multiplexers to express
Boolean functions also.
• Expressing Boolean functions as
MUXs is more efficient than as
decoders.
• First n-1 variables of the function
used as selection inputs; last
variable used as data inputs.
• If last variable is called Z, then each
data input has to be Z, Z’, 0, or 1.
Karnaugh Map Method of Multiplexer Implementation
Consider the function:

A is taken to be the data variable and B,C to be the select variables.

Example of MUX combo circuit
• F(X,Y,Z) = m(1,2,6,7)
 Sequential Logic
• Combinatorial components: the output values
are computed only from their present input
values.
• Sequential components: their output values
are computed using both the present and past
input values.
• Sequential circuits can contain only a finite
number of states finite state machines
• Synchronous and Asynchronous
 Sequential Circuits
• Contains Memory Elements
• Asynchronous sequential circuits change their state
and output values when input changes
• Synchronous sequential circuits change their output
values at fixed points of time, which are specified by the
rising or falling edge of a clock signal
• Clock period is the time between successive transitions
in the same direction
• Active high – state changes occur at the clock’s rising
edge( on higher voltage)
• Active low – state changes occur at the clock’s falling
edge( on lower voltage)
 4 Basic types of Flip-Flops
• SR, JK, D, and T
• JK ff has 2 inputs, J and K need to be
asserted at the same time to change the
state
• D ff has 1 input D (DATA), which sets the ff
when D = 1 and resets it when D = 0
• T ff has1 input T (Toggle), which forces the
ff to change states when T = 1
• SR ff has 2 inputs, S (set) and R (reset)
that set or reset the output Q when
asserted
 Gated D-Latch
• Ensures S and R inputs never equal to 1 at the
same time
• Useful in control application where setting or
resetting a flag to some condition is needed
• Stores bits of information
• Constructed from a gated SR latch and a Data
latch
 Recap - Sequential Systems

• Example:
– Design a D FF with a JK FF and AND, OR, NOT gates:

D J Q
To Be CLK
Designed
K Q’
Sequential Systems - Cont.

D(t)

0 1
0-
1--1
-0
JK
Sequential Systems - Cont.

D D

0 1 - -

Q - - Q 1 0

J=D K = D’

D • J Q
CLK

K Q’
 Analysis of Sequential Systems
• Goal:
– Decide the timing and functional behavior from the implementation
of a sequential system composed of FFs and logic gates
• Types:
– Functional analysis
– Timing analysis
Characteristic Equation of FFs
 D Flip-Flop
D Q+
0 0
1 1
Q+ = Next State
Characteristics :
Synchronous
Avoids the instability of RS flip-flop
Retains its last input value

To set the ff, place 1 on D input and pause the CK input

To reset, place 1 on D input and pause the CK input
T Flip-Flop
SET
D
T Q

CLR
Q

T Q+
0 Q
1 Q’

T = 1 force the state change

T = 0 state remain the same
 JK – Flip Flop

J – Set
K – Reset
J = K = 0 – output does not change
J = K = 1 – invert the outputs
Clocked JK – Flip Flop
D and JK Flip-Flop
SET
D Q D Q+
0 0
CLR
Q 1 1

SET J K Q+
J Q
0 0 Q
0 1 0
K Q
CLR
1 0 1
1 1 Q’
X Y

2 – TO –1
F
MUX

Z
 T

CLK

Q1
 T

CLK

Q1
 J

CLK

Q1
How to use JK to implement D Flip-Flop
D ff’s property:
J K Q+
When in = 0, the out(Q+) = 0.
D Q+ 0 0 Q When in = 1, the out(Q+) is 1

0 0  0 1 0  invert K

1 1  1 0 1  invert K

1 1 Q’

SET
D J Q

K CLR
Q
 How to use JK to implement T Flip-Flop
T ff’s property:
When in = 0, the out(Q+) = no change
J K Q+ When in = 1, the out(Q+) is = complement
0 0 Q  No change

0 1 0
1 0 1
1 1 Q’  State change
J
SET
Q
T Q+ T
0 Q K CLR
Q
1 Q’
 How to use D to implement JK Flip-Flop

J K Q+
0 0 Q
KQ 00 01 11 10
0 1 0
J 0 0(Q) 1(Q) 0 0
1 0 1
1 1 1 0(Q’) 1(Q’)
1 1 Q’
(Q ) = no state change
D Q+ (Q’) = state change

0 0
D = JQ’ + K’Q
1 1
How to use D to implement JK Flip-Flop

D = JQ’ + K’Q

J
SET
D Q

K
CLR
Q
How to use T to implement JK Flip-Flop
J K Q+
0 0 Q KQ 00 01 11 10
0 1 0 J
1 0 1 0 0 0 1 0
1 1 Q’ 1 1 0 1 1

T Q+
0 Q T = KQ + JQ’
1 Q’
How to use T to implement JK Flip-Flop

T = KQ + JQ’

SET
D
T Q

CLR
Q
How to use D to implement T Flip-Flop

Q+ 0 1
D Q+ T0 0 1
0 0 1 1 0
1 1

T Q+ D = TQ’ + T’Q
0 Q
1 Q’
How to use D to implement T Flip-Flop

D = TQ’ + T’Q

T
SET
D Q

CLR
Q
How to use T to implement D Flip-Flop
T Q+
0 Q Q+ 0 1
1 Q’ D
0 0 1
1 1 0
D Q+
0 0
T = DQ’ + D’Q
1 1
How to use T to implement D Flip-Flop

T = DQ’ + D’Q

SET
D
T Q

D
CLR
Q
SR-Flip Flop
S R Q Q’
0 0 Q Q’
1 0 1 0 SET
0 1 0 1 RESET
1 1 0 0

S R Q Q’
1 1 Q Q’
0 1 1 0 SET
1 0 0 1 RESET
0 0 1 1
 SR-Flip Flop
• Asynchronous
• If S=0 and R=1, Q is set to 1, and Q’ is
reset to 0
SET
• IF R=0 and S=1, Q is reset to 0, and Q’ S Q
is set to 1
• If S=1 and R=1, Q and Q’ maintain their
R Q
previous state CLR

• If S=0 and R=0, a transition to S=1,

R=1 will cause oscillation
 Instability
• RS flip-flops can become unstable if both
R and S are set to 0
• All sequential elements are fundamentally
unstable under certain conditions
– Invalid transitions
– Transitions too close together
– Transitions at the wrong time
Edge and level-triggered Flip Flop
• Digital circuit often form loops, flip-flops
oscillations can
• Oscillation will not occur because by
the time an output change cause an
input change, the activating edge of the
CK signal will be gone
• Positive edge triggered – ff responds to
a positive going edge of clock
• Negative edge triggered – responds to
a negative-going edge
Positive-edge-triggered D Flip-Flop

When CLK=0 the

master latch is open
and the content of D is
transferred to QM
When CLK=1 the
master is closed and
its output is transferred
to the slave
Master and slave
latches are never
enabled at the same
time