Sequential Circuits
Page 1 on 23
1. Introduction
Combinatory circuits are based on Boolean algebra, while sequential circuits use memory
elements called flip-flops in addition to combinatory circuits, adding a time dimension
(sequential circuits are often said to remember their previous states).
Combinatory Circuit
INPUT OUTPUT
Memory (FLIP-FLOP)
Sequential Circuit
There are two types of sequential circuits:
-Asynchronous sequential circuits: in this type of circuit, the outputs change
instantaneously as the inputs change.
-Synchronous sequential circuits: in this type of circuit, the outputs can only
change under the control of a clock signal.
2. Bistables (flip-flops)
2.1 RS flip-flop (Asynchronous)
a- The RS flip-flop represents a memory equal in size to one bit. It has two
inputs, S and R. The S input (set to one) sets the flip-flop to one, while the R
input (reset) sets the flip-flop to zero. The flip-flop also has two
complementary outputs 𝑸 and 𝑸̅. The state of the bit is always Q.
The diagram below illustrates the operation of this flip-flop.
Page 2 on 23
S
Q
R Q
Asynchrone Bistable RS
b- How the flip-flop works :
The future state 𝑸+ of the RS flip-flop is a Boolean function with parameters
S, R and Q.
If S=0 and R=0, the future state 𝑸+ of the flip-flop remains equal to Q (bit
stored).
For S=0 and R=1 the future state 𝑸+ of the flip-flop will be equal to 0 (clear)
For S=1 and R=0 the future state 𝑸+ of the flip-flop would be equal to 1 (set)
For S=1 and R=1 this configuration is strictly forbidden in the latch input.
Note: The synchronous RS flip-flop operates under the control of the clock signal,
often referred to as "CLK". RS flip-flops are generally represented in one of two
ways: synchronous or asynchronous
S Q S Q
CLK
R Q R Q
Bistable RS asynchronous Bistable RS synchronous
Page 3 on 23
c- Characteristic equation of the asynchronous RS flip-flop
The following truth table summarises the operation of the asynchronous RS flip-flop:
S R 𝑸 𝑸+
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 d
1 1 1 d
By applying Karnaugh's method for simplifying the 𝑸+ function
RQ 00 01 11 10
S
0
1
1 1 1 d d
𝑹𝑺= S+ 𝑹
The result is: 𝑸+ ̅ 𝑸
d- Characteristic equation of the synchronous RS flip-flop
The flip-flop operates under the control of the clock signal clk. When the signal
clk=0 the flip-flop operates as a memory element (𝑸+= 𝑸) and when the signal
clk=1 the flip-flop operates as an RS flip-flop.
The following truth table summarises the operation of the synchronous RS flip-flop:
Page 4 on 23
clk S R 𝑸 𝑸+
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 d
1 1 1 1 d
By applying Karnaugh's method for simplifying the function 𝑸+
RQ 00 01 11 10
Clk S
00 1 1
01 1 1
11 1 1 d d
10 1
The result is :
Page 5 on 23
2.2 JK flip-flop (asynchronous)
a. The JK flip-flop represents a memory of size equal to one bit. It has two
inputs J and K, input J (set to one) for setting the latch to one while input K
(reset) allows the latch to be set to zero. The flip-flop also has two
complementary outputs 𝑸 and 𝑸+. The state of the bit is always 𝑸.
b. How the flip-flop works :
The future state 𝑸+of the JK flip-flop is a Boolean function with parameters
J, K and 𝑸.
For J=0 and K=0, the future state 𝑸+of the flip-flop remains equal to 𝑸 (bit
stored).
For J=0 and K=1 the future state 𝑸+of the flip-flop will be equal to 0 (clear)
For J=1 and K=0 the future state 𝑸+of the flip-flop would be equal to 1 (set)
For J=1 and K=1 the future state 𝑸+of the latch would be equal to 𝑸̅ (invert
the bit content)
Note: The JK flip-flop presented in this course is simplified for teaching
purposes. There are also synchronous JK flip-flops. In general, JK flip-flops are
represented in one of two ways: synchronous or asynchronous.
J Q J Q
CLK
K Q K Q
Bistable JK asynchronous Bistable JK synchronous
Page 6 on 23
C- Characteristic equation of the asynchronous JK flip-flop
The following truth table summarises the operation of the asynchronous JK flip-
flop:
J K 𝑸 𝑸+
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
By applying Karnaugh's method for simplifying the function 𝑸+
KQ 00 01 11 10
J
1 1 1 1
The result is :
d-Characteristic equation of the synchronous JK flip-flop
The flip-flop operates under the control of the clock signal clk. When the signal
clk=0 the flip-flop operates as a memory element(𝑸+ = 𝑸) and when the signal
clk=1 the flip-flop operates as a JK flip-flop.
The following truth table summarises the operation of the synchronous JK flip-flop:
Page 7 on 23
clk J K 𝑸 𝑸+
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
By applying Karnaugh's method for simplifying the function 𝑸+
KQ 00 01 11 10
Clk J
00 1 1
01 1 1
11 1 1 1
10 1
The result is :
Page 8 on 23
2-3 T (Trigger) flip-flop
a. The T flip-flop represents a memory of size equal to one Bit. It has one input T
and two complementary outputs 𝑸 and 𝑸̅.
b. How the flip-flop works :
The future state 𝑸+ of the flip-flop T is a Boolean function of parameters T and 𝑸.
For T=0 the future state 𝑸+ of the latch remains equal to 𝑸 (bit memorised).
For T=1 the future state 𝑸+of the flip-flop will be equal to 𝑸̅ (bit content inverted)
Note:
There are also synchronous T flip-flops. Generally, T flip-flops are represented in
one of two ways: synchronous or asynchronous.
T Q T Q
CLK
Q Q
Bistable T asynchronous Bistable T synchronous
c- Characteristic equation of the asynchronous T flip-flop
The following truth table summarises the operation of the asynchronous T flip-
flop:
Page 9 on 23
T 𝑸 𝑸+
0 0 0
0 1 1
1 0 1
1 1 0
From the truth table we can deduce the characteristic equation of the flip-flop T :
𝑸+= 𝑻𝑸̅ + 𝑻̅ 𝑸 thus 𝑸+= 𝑻 ⊕ 𝑸
𝑻 𝑻
d- Characteristic equation of the synchronous T flip-flop
The following truth table summarises the operation of the asynchronous T flip-
flop:
clk T 𝑸 𝑸+
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
By applying Karnaugh's method for simplifying the function 𝑸+
Page 10 on 23
TQ 00 01 11 10
clk
0
1 1
1 1 1
The result is : 𝑸+
T =
2.4 D (Data) Flip-flop
a. The D flip-flop represents a memory of size equal to one Bit. It has one D
input and two complementary outputs 𝑸 and 𝑸̅. The state of the bit is
always 𝑸.
b. How the flip-flop works :
The future state 𝑸+of the D flip-flop is a Boolean function with parameters
D,Q and clk for the synchronous flip-flop. On the other hand, the future state
𝑸+of the D flip-flop depends only on the D input for the asynchronous flip-
flop.
D Q D Q
CLK
Q Q
Bistable T asynchrone Bistable T synchrone
Page 11 on 23
c- Characteristic equation of the asynchronous D flip-flop
+= 𝑫
𝑸𝑫
d- Characteristic equation of the synchronous D flip-flop
The following truth table summarises the operation of the synchronous D flip-
flop:
clk D 𝑸 𝑸+
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
By applying Karnaugh's method for simplifying the function 𝑸+
DQ 00 01 11 10
clk
0
1 1
1 1 1
𝑫=
The result is : 𝑸+
Page 12 on 23
3 Sequential circuits
A sequential circuit consists of a combinatory part and memory elements (flip-
flops). The study of combinatory circuits is based on Boolean algebra. The study of
sequential circuits is based on the theory of finite state automata.
3-1 Finite state automata
In this chapter, we introduce finite state automata for the purpose of synthesising
and analysing sequential circuits.
a- Principle:
An automaton is made up of a set of pairs (state, transition): The state of an
automaton represents the state (content) of the circuit's memories. Since the
memory elements are flip-flops (bits), the maximum number of states in a
sequential circuit containing K flip-flops is 2K.
Graphically, a state is represented by a circle containing a label representing
the name of the state.
State i
A transition in the automaton is a directed arc linking two states (the arc
transits from the start state with which it is associated to the end state).
Graphically, this arc is a one-way arrow labelled with the circuit's input
variables and possibly output variables.
Input variables / Output variable
b. Illustrative examples:
b-1 - Automaton associated with the T flip-flop
Page 13 on 23
We assume that the sequential circuit is an asynchronous flip-flop T. The truth
table associated with this flip-flop is :
T 𝑸 𝑸+
0 0 0
0 1 1
1 0 1
1 1 0
The circuit contains one bit, so the automaton will have a maximum of two
states.
We call e0 the state of the automaton associated with the state Q = 0 of the flip-
flop and e1 the state of the automaton associated with the state Q = 1 .
According to the truth tale :
If the automaton is in state e0 and T=0 (input variable) then the future state is
e0. In this case there are no output variables. The output is confused with the
future state of the flip-flop.
If the automaton is in state e0 and T=1 (input variable) then the future state is
e1.
If the automaton is in state e1 and T=0 then the future state is e1.
If the automaton is in state e1 and T=1, then the future state is e0.
0 𝒆𝟎 𝒆𝟏 0
1
Automaton describing the operation of the flip-flop T
Mohamed Redha Page 14 on 23
b-2 - Automaton associated with the JK flip-flop
We assume that the sequential circuit is an asynchronous JK flip-flop. The
truth table associated with this flip-flop is :
J K 𝑸 𝑸+
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
The circuit contains one bit, so the automaton will have a maximum of two
states.
We call 𝒆𝟎 the state of the automaton associated with the state Q = 0 of the
flip-flop and 𝒆𝟏 the state of the automaton associated with the state Q = 1 .
According to the truth tale :
If the automaton is in state 𝒆𝟎 and JK=00 (input variable) then the future
state is 𝒆𝟎 (storage). In this case there are no output variables. The output is
confused with the future state of the flip-flop.
If the automaton is in state 𝒆𝟎 and JK=01, then the future state is 𝒆𝟎 (the
contents of the flip-flop are erased, future state 𝑄+ = 0).
If the automaton is in state 𝒆𝟎 and JK=10, then the future state is 𝒆𝟏 (set the
flip-flop to 1, future state 𝑄+ = 1).
If the automaton is in state 𝒆𝟎 and JK=11 then the future state is𝒆𝟏. (invert
the contents of the flip-flop, future state 𝑄+ = 1)
If the automaton is in state 𝒆𝟏and JK=00 then the future state is𝒆𝟏.
If the automaton is in state 𝒆𝟏and JK=01 then the future state is 𝒆𝟎 .(clearing
the contents of the flip-flop, future state 𝑄+ = 0)
Page 15 on 23
If the automaton is in state 𝒆𝟏and JK=10, then the future state is 𝒆𝟏 (set the
flip-flop to 𝟏, future state 𝑸+ = 1).
If the automaton is in state 𝒆𝟏 and JK=11 then the future state is 𝒆𝟎 .(invert the
contents of the flip-flop, future state 𝑸+ = 0)
10
00 11 00
𝒆𝟎 𝒆𝟏
01 11 10
01
Automaton describing the operation of the flip-flop JK
3-2 Synthesis of sequential circuits
Creating a sequential circuit to solve a problem involves applying a synthesis
procedure as follows:
a. Understand the problem.
b. Synthesise any combinatory part of the circuit.
c. Create the finite state automaton that solves the problem.
[Link] the number of flip-flops to be integrated into the sequential
circuit.
[Link] the automaton into a table of transitions and future states (a truth
table), based on the characteristic tables of the flip-flops used in the circuit.
[Link] the functions relating to the triggering of the flip-flops and any
functions relating to the outputs of the circuit.
g. Draw the sequential circuit.
Page 16 on 23
Example:
Make a sequential circuit that recognises the string 1011 with overlay
(the string is read bit/bit from right to left), the output is equal to 1 if the string
is recognised (use JK flip-flops).
1 In this example, the circuit does not include an independent combinatory
part.
2 Creation of the finite state automaton to solve the problem:
Each bit in the chain will be represented by states in the automaton. The
automaton will be modelled by four(4) states (number of states n=4).
To draw the raw automaton :
Each bit in the string read is associated with a state responsible for
recognising that bit.
The first bit on the right will be associated with state e0 (1011): state e0
will be responsible for recognising the reading of the first "1" in the
string and will hand over to state e1 for recognising the second bit in the
string (1011).
The transition from e0 to e1 will be labelled I/O (I for the bit read and O
for the output), the output S=1 only if the string is completely read.
If en is in a state ei of the automaton and the bit read does not correspond
to the bit in the string, then en must restart from the initial state e0.
Diagram of the crude automaton:
Page 17 on 23
0/0
1/1
𝒆𝟎 1/0
0/0 0/0
𝒆𝟑 1/0 𝒆𝟏
0/0 𝒆𝟐 1/0
Note:
the crude automaton developed above does not meet the description of the problem
posed. In fact, the crude automaton does not achieve the required overlap (a new
correct string can start before the end of a string currently being recognised). In order
to create the sequential circuit, the crude automaton must be corrected to solve the
problem.
Diagram of the improved Automaton
0/0
0/0
𝒆𝟎 1/0
0/0
𝒆𝟑 1/1 𝒆𝟏
1/0
0/0
𝒆𝟐 1/0
Page 18 on 23
3 Determining the number of flip-flops required to complete the circuit :
The number of flip-flops P is given by the formula: : 2P-1< n <= 2P
Where: n represents the number of states in the automaton.
In the example shown, 2P-1< 4 <= 2P P=2..
The circuit then consists of two JK type flip-flops (the type of flip-flop is
indicated in the problem statement).
4 Building the table of future states, transitions and outputs (truth table) :
To construct this table we will need to encode the states of the automaton
using the states of the flip-flops in the circuit. We will also use the
transition state tables of the asynchronous JK flip-flop to construct the
truth table.
The circuit has two JK flip-flops:
𝑸𝟏represents the state of the first flip-flop and 𝑸𝟐 represents the state of the
second flip-flop.
Thus:
Automaton State 𝑸𝟏 𝑸𝟐
e0 00
e1 01
e2 10
e3 11
Page 19 on 23
JK flip-flop transition table:
𝑸 𝑸+ J K
0 0 0 d
0 1 1 d
1 0 d 1
1 1 d 0
Table of future states, transitions and outputs :
Entrée Etat Etat futur Entrée Entrée Sortie
bascule 1 bascule2
E 𝑸𝟏 𝑸𝟐 𝑸+
𝟏
𝑸+
𝟐 𝐽1 𝐾1 𝐽2 𝐾2 S
0 0 0 0 0 0 d 0 d 0
0 0 1 0 0 0 d d 1 0
0 1 0 1 1 d 0 1 d 0
0 1 1 0 0 d 1 d 1 0
1 0 0 0 1 0 d 1 d 0
1 0 1 1 0 1 d d 1 0
1 1 0 1 0 d 0 0 d 0
1 1 1 0 1 d 1 d 0 1
The variables J1, K1, J2, K2 and S will be considered as functions in the truth
table and will be simplified using Karnaugh's method.
5- Simplification:
𝑱𝟏 = 𝑬𝑸𝟐 ; 𝑲𝟏 = 𝑸𝟐 ; 𝑱𝟐 = 𝑬 ⊕ 𝑸𝟏 ; 𝑲𝟐 = 𝑬 + 𝑸 𝟏 ; 𝑺 = 𝑬𝑸 𝟏𝑸 𝟐
Page 20 on 23
6- The sequential circuit
𝑺
𝑬
𝑱𝟏 𝑸𝟏 𝑱𝟐 𝑸𝟐
𝑲𝟏 ̅𝑸̅𝟏̅ 𝑲𝟐 ̅𝑸̅𝟐̅
𝑪𝑳𝑲
Page 21 on 23
