Chapter 05

Synchronous Sequential Logic

Synchronous Sequential Logic
Digital circuit
Combinational Circuit
Sequential Circuit
 Consists of a combinational circuit to which storage elements
are connected to form a feedback path.
 Outputs and the next state of the storage elements are a
function of the inputs and the present state of the storage
elements.
Synchronous Sequential Logic
Two types of sequential circuits
 Asynchronous Sequential Circuit
whose behavior depends on the input signals at any instant of
time and the order in which the inputs change. Thus, an
asynchronous sequential circuit may be regarded as a
combinational circuit with feedback. It may become unstable
at times
 Synchronous Sequential Circuit

whose behavior can be defined from the knowledge of its

signals at discrete instants of time.
synchronization is achieved by a timing device called a clock
generator that provides a periodic train of clock pluses.
the storage elements are affected only with the arrival of each
pulse.
Synchronous Sequential Logic
Synchronous sequential circuits that use clock pulses in
the inputs of storage elements are called clocked
sequential circuits
The storage elements (memory) used in clocked
sequential circuits are called flip-flops. Flip-flop is a
binary storage device capable of storing one bit of
information
Synchronous Sequential Logic
Prior to the occurrence of the clock pulse, the
combinational logic forming the next value of the flip-
flop must have reached a stable value. Consequently,
the speed at which the combinational logic circuits
operate is critical.
Propagation delays play an important role in
determining the minimum interval between clock
pulses that will allow the circuit to operate correctly.
State of the flip-flops can change only during a clock
pulse transition.
When a clock pulse is not active, the feedback loop is
broken.
Synchronous Sequential Logic
Storage elements that operate with signal levels are
referred to as latches; those controlled by a clock
transition are flip-flops.
The two types of storage elements are related because
latches are the basic circuits from which all flip-flops
are constructed.
Latch is useful for the design of asynchronous
sequential circuits, not practical for use in
synchronous sequential circuits.
Synchronous Sequential Logic
 SR Latch
 Two cross-coupled NOR, or two cross-coupled NAND
 S for set, R for reset

Q=1, Q’=0 → set state

Q=0, Q’=1 → reset state
S=1, R=1 → undefined state → both outputs are 0
If both inputs are then switched to 0 simultaneously, the device will enter
an unpredictable or undefined state. Consequently, in practical
applications, setting both inputs to 1 is forbidden.
Synchronous Sequential Logic
 SR latch with two cross-coupled NAND

 S=0 causes Q=1 → set state → S =1 then the circuit remains in

the set state
 R=0 causes Q=0 → reset state → R =1 then the circuit remains

in the reset state

Synchronous Sequential Logic
 Because NAND latch requires a 0 signal to change its state,
sometime it is referred as an S’R’ latch
 SR latch with control input
 With two additional NAND and a control input C

 When C=1, S/R inputs could affect the SR latch

Synchronous Sequential Logic
 S=1 R=0 C=1 → set state
 S=0 R=1 C=1 → reset state

 C=0 → the circuit remains in its current state

 S=1 R=1 C=1 → indeterminate state

Synchronous Sequential Logic
 D latch
 Eliminate the undesirable condition of the indeterminate

state

 Only two inputs: D (data) and C (control)

 Output follows changes in the data input as long as the

control input is enabled → transparent latch

Synchronous Sequential Logic
Graphic symbols
Synchronous Sequential Logic
When latches are used for the storage elements, a serious
difficulty arises.
 The state transitions of the latches start as soon as the clock pulse
changes to the logic-1 level. The new state of a latch appears at the
output while the pulse is still active. This output is connected to
the inputs of the latches through the combinational circuit. If the
inputs applied to the latches change while the clock pulse is still at
the logic-1 level, the latches will respond to new values and a new
output state may occur. The result is an unpredictable situation.
The key to the proper operation of a flip-flop is to trigger it
only during a signal transition. This can be accomplished
by eliminating the feedback path that is inherent in the
operation of the sequential circuit using latches.
Synchronous Sequential Logic
The problem with the latch is that it responds to a
change in the level of a clock pulse
Key solution is to trigger it only during a signal
transition (clock pulse when 0→1 or 1→0)
Synchronous Sequential Logic
Two ways that a latch can be modified to form a flip-
flop.
 Employ two latches in a special configuration that isolates
the output of the flip-flop from being affected while the input
to the flip-flop is changing
 Another way is to produce a flip-flop that triggers only
during a signal transition (0→1 or 1→0) of the synchronizing
signal (clock) and is disabled during the rest of the clock
pulse.
Synchronous Sequential Logic
Master-slave D flip-flop
 Two D latches and a inverter
 The circuit samples the D input and changes its output Q
only at the negative-edge of the controlling clock (the
transition of the clock from 1 to 0)
Synchronous Sequential Logic
 D type Positive-Edge-Triggered Flip-Flop

 Three SR latches
 Two latches respond to the external D and Clk

 the third latch provides the outputs for the flip-flop

 The S and R inputs of the output latch are maintained at the

logic-1 level when Clk=0. This causes the output to remain in

its present state.
Synchronous Sequential Logic
 When CLK=1 and D = 0 → R changes to 0 → go to reset state
→ making Q =0
if there is a change in the D input, R remains at 0, thus the
flip-flop is locked out and is unresponsive to further changes
in the input.
when clock returns to 0, R goes to 1, placing the output in the
quiescent condition without changing the output.
 Similarly, when CLK goes from 0 to 1, if D=1 → S changes to 0
→ go to set state and making Q =1
any change in D while CLK=1 does not affect the output
Synchronous Sequential Logic
The minimum time during which the D input must be
maintained at a constant value prior to the occurrence
of the clock transition is called setup time.
The minimum time during which the D input must not
change after the application of the positive transition of
the clock is called the hold time.
The propagation delay time of the flip-flop is defined as
the time interval between the trigger edge and the
stabilization of the output to a new state.
Synchronous Sequential Logic
Arrowhead-like symbol indicates a dynamic input
responding to the edge transition of the clock
Synchronous Sequential Logic
Other Flip-Flops
 Most economical and efficient flip-flop constructed in the
manner is the edge-triggered D flip-flop because it requires
the smallest number of gates.
 Other types of flip-flops can be constructed by using the D
flip-flop and external logic
 Two widely used flip-flops are
 JK flip-flop

 T flip-flop
Synchronous Sequential Logic
JK flip-flop

Three operations
 Set to 1
 Reset to 0
 Complement its output
Synchronous Sequential Logic
 D = JQ’ + K’Q
 J = 1, K=0 sets the flip-flop to 1

 K = 1, J=0 resets the flip-flop to 0

 When J=1 and K =1, output is complemented

 When J=0 and K =0, output is unchanged

Synchronous Sequential Logic
T(toggle) Flip-Flop

A complementing flip-flop and can be obtained from a

JK flip-flop when J/K are tied together
useful for designing binary counters
D = T ⊕ Q = TQ’ + T’Q
Synchronous Sequential Logic
Characteristic Tables
 Define the logical properties of a flip-flop by describing its
operation in tabular form.
 Define the next state as a function of its inputs and present
state.
Synchronous Sequential Logic
Characteristic Equations
 D flip-flop
Q(t+1) = D
 Q(t+1) = JQ’+K’Q

 Q(t+1) = T⊕Q = TQ’+T’Q

Synchronous Sequential Logic
Direct Inputs
 Some flip-flops have asynchronous inputs to force the flip-
flop to a particular state independent to the clock
 Input that sets the flip-flop to 1 is called preset or direct set

 Input that clears the flip-flop to 0 is called clear or direct

reset
 When power is on, the status is unknown

 The direct inputs are useful for bringing all flip-flops to a

known starting state prior to the clocked operation.
Synchronous Sequential Logic
E.g. positive-edge
-triggered D
flip-flop with
asynchronous
reset
Synchronous Sequential Logic
 The above Fig. is the same as Fig.5-10, except for the
additional reset input connects to three NAND gates
 When reset=0 → force Q’=1 → clear Q to 0 → reset

 Two connections from reset input ensure that S of the third

SR latch stays at 1 while reset=0 regardless of the values of D
and CLK
 Direct reset is marked as R, and the bubble indicates the
reset is active at logical 0 level
Synchronous Sequential Logic
Analysis of Clocked Sequential Circuits
Clock sequential circuit is determined from the inputs,
outputs, and the state of its flip-flop.
Analysis of a sequential circuit consists of obtaining a
table for the time sequence of inputs, outputs and its
internal states
A logic diagram is recognized as a clocked sequential
circuit if it includes flip-flops with clock inputs
Synchronous Sequential Logic
State Equations
 State equation (transition equation) specifies the next state
as a function of the present state and inputs

Omit (t)

Omit (t)
Synchronous Sequential Logic
State Table (Transition Table)
 Consists of present state, input, next state, output
Synchronous Sequential Logic
 m flip-flops, n inputs needs 2m+n rows in the state table, the
next-state section has m columns, one for each flip-flop
 Another form of the state table
Synchronous Sequential Logic
State Diagram
 Represented graphically
 0/1 means input is 0, and output is 1

 From state 00, input 1 → output 0, enter state 01

 From state 00, input a string of 1’s, then output 0’s and enter
state 10, if input 0
now, then output 1 and back
to state 00
Detect a zero in the bit stream
of data
Synchronous Sequential Logic
Output equations
 the part of combinational circuit that generates external
outputs
Flip-Flop Input Equations
 D type flip-flop with input x, y and output Q

 Fig 5-15, two D type flip-flops A, B, and input x, output y

Synchronous Sequential Logic
Analysis with D Flip-Flops
when
we know it implies a D flip-flop with output A
the next state could be obtained as
Synchronous Sequential Logic
Analysis with JK Flip-Flops
Procedures

E.g.
Synchronous Sequential Logic
 No outputs, therefore, the state table does not need an
output column, then we could obtain the follows
Not part of the state table, but
they are needed for evaluating
the next state in step 2

Next state of A remains 1

Synchronous Sequential Logic
 Next state could be obtained as the following steps

 Use A or B for the Q in flip-flop

(D=JQ’+K’Q)

 Use JA, KA for the inputs

→
 Use J , K for the inputs
B B
→
Synchronous Sequential Logic
Synchronous Sequential Logic
Analysis with T Flip-Flops
 T Flip-Flop:
 In Fig. 5-20, there are two flip-flops A and B
Synchronous Sequential Logic
 Two input equations and one output equation

 Next state could be obtained by substituting TA, TB

Synchronous Sequential Logic
 As long as x = 1, states 00→01→10→11→00→…
 When x=0, the circuit remains in the same state
Synchronous Sequential Logic
Mealy and Moore Models
Two models for sequential circuits
Difference in the way to generate output
 Mealy model
 Output is a function of both the present state and input

 Moore model
 Output is a function of the present state only

Finite State Machine (FSM)

 Mealy FSM
 Moore FSM
Synchronous Sequential Logic
Mealy model
 function of both the present state and input, Fig 5-15
Synchronous Sequential Logic
Moore model
 function of the present state only, Fig. 5-18
Synchronous Sequential Logic
 Another example, Fig.20
output y depends only on flip-flop values.
Synchronous Sequential Logic
 In Moore model, the outputs are synchronized with the
clock. Because they depends on only flip-flop outputs that
are synchronized with the clock.
 In Mealy model, the outputs may change if the inputs change
during the clock cycle
 The outputs may be momentary false because of the delay

time that the inputs change and the time that the flip-flop
outputs change
 in order to synchronize a Mealy type circuit, the inputs must

be synchronized with the clock and the outputs must be

sampled only during the clock edge.
Synchronous Sequential Logic
The analysis of sequential circuits starts from a circuit
diagram and culminates in a state table or diagram. The
design of a sequential circuit starts from a set of
specifications and culminates in a logic diagram.
Two sequential circuits may exhibit the same input-output
behavior, but have a different number of internal states in
their state diagram.
State Reduction and Assignment
 State reduction problem
 reducing the number of states in a state table, while keeping the
external input-output requirements unchanged.
 m flip-flops produces 2m states, a reduction in the number of
states may reduce the number of flip-flops. An unpredictable
effect is that sometimes it may require more combinational
gates.
Synchronous Sequential Logic
E.g. Fig.5-25, only care the input/output sequences
when input 01010110100 from a
Synchronous Sequential Logic
 If identical input sequences are applied to two circuits and
identical outputs occur for all input sequences, then the two
circuits are said to be equivalent
 To reduce the states, it is more convenient to use a state table
rather than a diagram.
 Two states are said to be equivalent if, for each member of the set
of inputs, they give exactly the same output and send the circuit
either to the same state or to an equivalent state.
Synchronous Sequential Logic
Synchronous Sequential Logic
Synchronous Sequential Logic

A state table which has been reduced to fewer states

does not guarantee a saving in the number of flip-flops
or the number of gates
Synchronous Sequential Logic
State Assignment
 Assign coded binary values to states
m states → at least n bits, 2n ≧ m
then 5 states need 3 bits Only one bit is 1
One-hot encoding usually leads to simpler decoding
logic for the next state and output. One-hot machines
can be faster than machines with sequential binary
encoding, and the silicon area required by the extra
flip-flops can be offset by the area saved by using
simpler decoding logic. This trade-off is not
guaranteed, so it must be evaluated for a given design.
The binary form of the state table is used to derive
the next-state and output-forming combinational
logic part of the sequential circuit. The complexity of
the combinational circuit depends on the binary state
assignment chosen.
Synchronous Sequential Logic
Design Procedure

Need experience
Synchronous Sequential Logic
Example
design a circuit that detects three or more consecutive
1’s in a string of bits coming through an input line
Start from S0,
if input=0, then stays at S0, else go to S1
When at S1
if input=0, then go to S0, else go to S2
When at S2
if input=0, then go to S0, else go to S3
When at S3
if input=0, then go to S0, else stays at S3 and output 1
Synchronous Sequential Logic
Synthesis using D Flip-Flop
 Because there are four states → needs 2 D Flip-Flops
 Let outputs of 2 D flip-flops be A and B

 one input x, and one output y

Synchronous Sequential Logic
Synchronous Sequential Logic
Designing a sequential circuit with flip-flops other than
D type is complicated by the fact that the input
equations for the circuit must be derived indirectly
from the state table.
Input equations of D type flip-flop are derived from the
next state
During the design process we usually know the
transition from present state to next state, and wish to
find the flip-flop input conditions that will cause the
required transition
A table that lists the required inputs for a given change
of state is called an excitation table.
Synchronous Sequential Logic

There are four possible transitions from present state to

next state
E.g., if JK flip-flop is to have a transition from 0 to 1, J
must be 1, and K may be 0 or 1
E.g., if T flip-flop has T=1, then set the state to be
complemented; T=0, then the state remains unchanged
Synchronous Sequential Logic
Synthesis using JK Flip-Flops

By excitation table
Synchronous Sequential Logic
Synchronous Sequential Logic
Synchronous Sequential Logic
Synthesis using T Flip-Flops
 E.g. 3 bits binary counter
 no input and output

 state transition in clocked sequential circuits occurs during a

clock edge
 Flip-flops remain in their present states if no clock is applied
Synchronous Sequential Logic
 The only input is clock, outputs are specified by the present
states
 Binary counters are most efficiently constructed with T flip-
flops because of their complement property
Synchronous Sequential Logic

By excitation table
Synchronous Sequential Logic