Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.

0/ Digital Circuits

Design of Clocked Synchronous Sequential Circuits Steps of sequential circuit design (cont'd)
The design of a sequential circuit starts with the problem statement which specifies
the desired relationship between the input and output sequences (scenario). 4. Assigning codes to each state: A binary code is assigned to each state. If
there are n states, the number of variables (number of flip-flops) m is
The process of designing a circuit to perform a given logical function is quite similar
computed as follows:
to the process of designing a computer program to perform a given task.
First, we should describe and appropriately model the real-world problem. m= log2n
Then, we should design a circuit to solve the problem. where x denotes the ceiling function. For example, 4.1 = 5 and 4.0 = 4.
5. We construct the state transition and output table based on the values of
Designing a sequential circuit consists of the following steps:
the state variables.
1. We describe the problem (functional requirements of the circuit) verbally. We
6. We decide what type of flip-flops we will use.
can use timing diagrams to avoid uncertainties.
7. Using the transition table for the selected flip-flop type, we determine the
2. We decide which design model (Mealy/Moore) would better represent the circuit.
inputs of the flip-flops. We obtain the function (F) that drives the flip-
3. We determine the states that will make up the finite state machine (FSM). flops.
a) We determine the state transitions based on the inputs and current states.
8. From the output table, we obtain the output function (G).
b) We construct the state transition and output tables. We can use a state diagram if
it makes the design easier. 9. We design combinational circuits for the functions (F and G) and implement
each with the minimum cost.
c) We reduce the number of states in the state table (if applicable). The purpose is to
build a correctly functioning machine with the fewest possible number of states.
d) This process is similar to the process of designing a computer program; that is why
it requires an intuitional approach.
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.1 2011 - 2023 Feza BUZLUCA 10.2
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

Synchronous Circuit Design Example: 1. We construct the state diagram based on the problem statement (timing
Problem: diagrams). This step requires an intuitional approach and experience.
We will design a sequential circuit with a single input (X) and single output (Z). We can design the machine using three states: 1/0
After the input remains at "0" for two consecutive clock cycles, the output will be A: No zeros have been received 1/0
"1" as long as a "0" is read at the input. A
B: First zero has been received
We can use a timing diagram to show the state machine's expected behavior for a X=0/Z=0
sequence of inputs. C: Second zero has been received 1/0
1st 0 2nd 0 1st 0 Not 0 1st 0 2nd 0
2. We construct the state, output 0/1 0/0 B
Clock table. C
S+,Z
X
X 0 1 State transition, output table:
S Q1+Q0+,Z (in Karnaugh map format)
State coding: X
A B,0 A,0 0 1
A: 00 Q 1Q 0
Z B C,0 A,0 (Alternative coding
C C,1 A,0
B: 01 is possible) 00 01,0 00,0
C: 11 Gray 01 11,0 00,0
Current Next States, State variables: Code 11 11,1 00,0
The design should follow the Mealy model so that the circuit can function as States Outputs Q1 , Q0 10 øø,ø øø,ø
shown in the above timing diagram.
Alternative state codings are possible. For example, A:00, B: 10, C:01.
This is because the output which corresponds to a given input appears immediately In that case, the internal structure of the circuit will be different.
following the application of that input (before the active edge of the clock signal).
However, the functionality of the circuit will be the same.
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.3 2011 - 2023 Feza BUZLUCA 10.4
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

Q1+Q0+,Z State transition table 4. We determine the input functions of the flip-flops:
3. We determine the transitions of X
state variables: Q 1Q 0 0 1
We will use D flip-flops in this example.
Using the state transition table of the 00 01 00
circuit, we determine the transitions of 01 11 00 In the previous (3.) step, we determined transitions for all flip-flops.
each state variable (flip-flop) separately. 11 11 00 In this step, we will investigate the values that must be applied to the inputs of
For this solution, we need two flip-flops, 10 øø øø the flip-flops to make the required transitions.
i.e., Q1 and Q2. Q0 transitions: We will use the transition table of the flip-flop for this purpose.
Q 1Q 1+ Q 0Q 0+ (Q0→Q0+)
Q1 transitions: X X D flip-flop transition table:
Q 1Q 0 0 1 0 1
(Q1→Q1 )+ Q 1Q 0
symbol QQ+ D
00 00 00 00 01 00
To simplify notation, symbol QQ+ 0 00 0 This table shows the value that must be applied to the
01 01 00 01 11 10
we assign symbolic α 01 1 input of a D flip-flop for a given transition.
0 00 11 11 10 11 11 10
names to transitions α 01 10 ø ø 10 ø ø β 10 0 Different types of flip-flops have different transition
and reorganize the β 10 1 11 1 tables.
tables with these Q 1Q 1+ Q 0Q 0+
1 11 X X
symbols. Q 1Q 0 0 1 Q 1Q 0 0 1
00 0 0 00 α 0 The transition table of the D flip-flop is simple. The value that must be applied to
Thus, we have determined what transition 01 α 0 01 1 β the input of the D flip-flop is equal to the next value of its state variable.
each state variable (flip-flop) will make for 11 1 β 11 1 β
each input value and state. 10 ø ø 10 ø ø
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.5 2011 - 2023 Feza BUZLUCA 10.6
http://www.buzluca.info http://www.buzluca.info
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

We derive the required inputs for the flip-flops using the transition tables. 5. Using the output table, output function (G) is obtained.
Q1 transitions (Q1→Q1+) : Q0 transitions (Q0→Q0+) : Z
X When designing functions F and G, design methods for
Q 1Q 1+ Q 0Q 0+ D flip-flop transition table: Q 1Q 0 0 1
X X combinational circuits (prime implicants, prime implicant
Q 1Q 0 0 1 Q 1Q 0 0 1 symbol QQ+ D 00 0 0 chart, minimization) that were covered in the first part
00 0 0 00 α 0 0 00 0 01 0 0 of the course should be used.
01 α 0 01 1 β α 01 1 11 1 0 There is no need to minimize the functions in this
11 1 β 11 1 β β 10 0 10 ø ø example because they are simple.
10 ø ø 10 ø ø 1 11 1
Z = X'Q1 Z = G(Input "X" , State "Qi")
Input of D1 : Input of D0 : 6. We implement and draw the designed circuit using logic gates.
D1 D0
X X
Q 1Q 0 0 1 Q 1Q 0 0 1 To obtain expressions easily, D0 Q0
tables are formed as Karnaugh X D Q
00 0 0 00 1 0 CLK
01 1 0 01 1 0 maps. Z
11 1 0 11 1 0 Rows and columns follow the order
10 ø ø 10 ø ø of the Gray code. D1 Q1
D Q
CLK
D1 = X'Q0 D0 = X' {D1 , D0 } = F(Input "X" , State "Qi")

We have thus obtained the state transition function (F) that drives the inputs of
Clock
the flip-flops to determine the next state (See slide 8.1).
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.7 2011 - 2023 Feza BUZLUCA 10.8
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

Example: Same circuit designed using J-K flip-flops We derive the required input values for the flip-flops using the transition tables.
Q1 transitions: Q0 transitions: Transition table for JK flip-flop:
The first three steps are the same.
Q 1Q 1+ Q 0Q 0+
4. In this example, we will use positive edge-triggered J-K flip-flops. X X
Q 1Q 0 0 1 Q 1Q 0 0 1 symbol QQ+ J K
J-K flip-flop transition table: 00 0 0 00 α 0 0 00 0 ø
symbol QQ+ J K 01 α 0 01 1 β α 01 1 ø
Using J-K flip-flops instead of D flip-flops generally 11 1 β 11 1 β β 10 ø 1
0 00 0 ø
yields simpler logic functions for the next state. 10 ø ø 10 ø ø 1 11 ø 0
α 01 1 ø
β 10 ø 1 However, since the functions in this example are already
1 11 ø 0 simple, the J-K flip-flop yields no further simplification. J1 K1 J0 K0
X X X X
Q 1Q 0 0 1 Q 1Q 0 0 1 Q 1Q 0 0 1 Q 1Q 0 0 1
We had determined the transitions of state variables from the state transition 00 0 0 00 ø ø 00 1 0 00 ø ø
table in step 3. 01 1 0 01 ø ø 01 ø ø 01 0 1
Q1 transitions (Q1→Q1+): Q0 transitions (Q0→Q0+):
11 ø ø 11 0 1 11 ø ø 11 0 1
Q1+Q0+,Z Q 1Q 1+ Q 0Q 0+
X X X 10 ø ø 10 ø ø 10 ø ø 10 ø ø
Q 1Q 0 0 1 Q 1Q 0 0 1 Q 1Q 0 0 1
00 01,0 00,0 00 0 0 00 α 0 J1 = X'Q0 K1 = X J0 = X' K0 = X
01 11,0 00,0 01 α 0 01 1 β {J1 , K1 , J0 , K0} = F(X, Q1, Q0)
11 11,1 00,0 11 1 β 11 1 β
We have thus obtained the function (F) that drives the inputs of the flip-flops
10 øø,ø øø,ø 10 ø ø 10 ø ø and determines the next state.
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.9 2011 - 2023 Feza BUZLUCA 10.10
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

5. We determine the output function (G) using the output table. Transition tables for flip-flops:
Z
X Transition tables for different types of flip-flops are given below.
Q 1Q 0 0 1
00 0 0
01 0 0 Z = X'Q1 Transition table for S-R flip-flop : Transition table for J-K flip-flop :
11 1 0
symbol QQ+ S R symbol QQ+ J K
10 ø ø
0 00 0 ø 0 00 0 ø
α 01 1 0 α 01 1 ø
6. We implement and draw the designed circuit using logic gates.
β 10 0 1 β 10 ø 1
X 1 11 ø 0 1 11 ø 0
J0
J Q0
K Q
K0 CLK
Transition table for D flip-flop: Transition table for T flip-flop :
Z symbol QQ+ D symbol QQ+ T
J1
J Q1 0 00 0 0 00 0
K1 Q
K CLK α 01 1 α 01 1
β 10 0 β 10 1
1 11 1 1 11 0
Clock
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.11 2011 - 2023 Feza BUZLUCA 10.12
http://www.buzluca.info http://www.buzluca.info
 Digital Circuits Digital Circuits

Synchronous Circuit Design Example 2: Moore Model State/output table:

State coding:
Designing a circuit using the Moore model has the same design stages that we have S+ S0: 00
XY
already seen. Meaning S 00 01 11 10 Z S1: 01
It is important to note that Modulo 0 S0 S0 S1 S2 S1 1 S2: 11
Modulo 1 S1 S1 S2 S3 S2 0 S3: 10
• outputs depend ONLY on the states, Modulo 2 S2 S2 S3 S0 S3 0 State variables:
• because of this, each state corresponds to a single output. Modulo 3 S3 S3 S0 S1 S0 0 Q1, Q0

Problem:
Coded state/output table: Q0 • X ′ • Y Q 1′ • X • Y Q1 ′ • X ′ • Y Q1 ′ • X • Y ′
We will design a synchronous sequential circuit with two inputs (X,Y) and a single
Q1+Q0+
output (Z). XY
D1 XY D0 XY
If the number of 1s received at the input is a multiple of 4, the output of the Q1Q0 00 01 11 10 Z Q1 Q0 00 01 11 10 Q1 Q0 00 01 11 10
circuit is 1. Otherwise, the output should be 0. If no 1s are received (the number 00 00 01 11 01 1 00 0 0 1 0 00 0 1 1 1
of 1s is zero), the output should be 1. 01 01 11 10 11 0
01 0 1 1 1 01 1 1 0 1
11 11 10 00 10 0
Solution: 10 10 00 01 00 0 11 1 1 0 1 11 1 0 0 0

The circuit should perform the modulo 4 operation, and if the result of the 10 1 0 0 0 10 0 0 1 0
operation is 0, the output should be 1. This FSM can be implemented with 4 states: Q1 • X ′ • Y ′ Q0 • X • Y ′
Q0 X ′ Y ′
• • Q0 ′ • X • Y
1. Modulo 0: S0 Output = 1 number of incoming 1s mod 4 = 0
2. Modulo 1: S1 Output = 0 number of incoming 1s mod 4 = 1 Since we are using the characteristic eq. of the D flip-flop (Q+=D), D1=Q1+ , D0=Q0+
3. Modulo 2: S2 Output = 0 number of incoming 1s mod 4 = 2 D1= Q0·X'·Y + Q1'·X·Y + Q1·X'·Y' + Q0·X·Y' Z= Q1' · Q0'
4. Modulo 3: S3 Output = 0 number of incoming 1s mod 4 = 3 D0= Q1'·X'·Y + Q1'·X·Y' + Q0·X'·Y' + Q0'·X·Y
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.13 2011 - 2023 Feza BUZLUCA 10.14
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

D input values of the flip-flop: (From the previous example)

Using Multiplexers for Synchronous Circuit Implementation
D1 XY D0 XY
If a synchronous sequential circuit is designed using D flip-flops, simpler Q1 Q0 00 01 11 10 to multiplexer:
00 01 11 10 to multiplexer :
Q1 Q0
implementations are possible if the inputs of the flip-flops are driven with 00 0 0 1 0 I = X⋅Y
0 00 0 1 1 1 I0 = X + Y
multiplexers. 01 0 1 1 1 I1 = X + Y
01 1 1 0 1 I1 = (X⋅Y)
In this method, 11 1 1 0 1 I3 = (X⋅Y)
11 1 0 0 0 I3 = (X + Y)
• The input of each D flip-flop is driven by a separate multiplexer. 10 1 0 0 0 I = (X + Y)
2 10 0 0 1 0 I2 = X⋅Y
• The state variables (flip-flop outputs) are connected to the selector
(control) inputs of the multiplexers. Therefore, each multiplexer selects one XY
of its data inputs according to the current state.
• The inputs of the multiplexer should have the necessary values that produce
the next state of the machine. I0 4:1
4:1
I1 MUX D0 Q0 Z = Q1·Q0
Z D Q
• We obtain the values that will be applied to the inputs of the multiplexers I2 VS Z
I3 s1 s0 CLK
from the rows of the state transition table. Q0'
Q1 Q0 Z
The same circuit designed in the previous example will be redesigned using I0 s1 s0
multiplexers. I1 D1 Q1
I2 4:1 Z
D Q
I3 MUX CLK
Q1'
Clock
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.15 2011 - 2023 Feza BUZLUCA 10.16
http://www.buzluca.info http://www.buzluca.info

Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

Counter Design State diagram: State table:

Counters that count at each active clock signal with a certain sequence can be X=0 Q1+ Q0+
designed as a synchronous sequential circuit. X 0
X=1 1 Q1Q0
The Moore model is appropriate for counter design. 00 01 00 01 11
Each output value of the counter can be treated as a different state. 01 10 00
X=1 X=1 X=0
X=0 11 00 10
We can obtain outputs directly from the state variables (Output = State, O=S).
This means that the design must use the Moore Model. X=1 10 11 01
11 10
Example: Rows are ordered according to the Gray
X=0 code so that state table can also be used as
Design the counter shown below that has a single control input (X).
State variables and outputs have the a Karnaugh map.
The counter should count at each rising edge of the clock signal in the natural same values (O = S).
order, 0-1-2-3. The counter should go back to 0 after 3.
Designing the counter using D flip-flops:
When X=0, it should count up; if X=1, it should count down.
Recall: D1 D0
X 0 1
Q+ = D Q1Q0 Q1Q0 X 0 1
X Counter clock
Therefore, 00 0 1 00 1 1 Output:
up/down D1 = Q1+ 01 1 0 01 0 0
Z0 = Q0
D0 = Q0+ 11 0 1 11 0 0
Z1 = Q1
z1 z0 Counter output 10 1 0 10 1 1
D1 = X'·(Q1⊕Q0) + X·(Q1⊕Q0)'
Most significant bit (MSB) Least significant bit (LSB) D0 = Q0'
D1 = X⊕Q1⊕Q0
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.17 2011 - 2023 Feza BUZLUCA 10.18
http://www.buzluca.info http://www.buzluca.info
 Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/ Digital Circuits

We can use logic gates (AND, OR, XOR etc.) or multiplexers to implement Example:
counters. Design a counter that counts in the sequence 0-1-2-3-4-5 and has a single
Below, since the D0 input has a very simple expression ( D0 = Q0' ) , we prefer a control input (X).
logic gate (single inverter) to a multiplexer. If X=0 count up by one; if X=1, count up by 2.
A multiplexer is used to drive input D1. D1 State table:
X 0 1 to multiplexer: X=0 Q2+Q1+Q0+
Q1Q0 000 001
Remember: State variables (Q1Q0) will be connected X
00 0 1 I0 = X X=0 X=0 Q2Q1Q0 0 1
to the selector inputs of the multiplexer. X=1 X=1
01 1 0 I1 = X' 000 001 010
11 0 1 I3 = X 001 010 011
101 X=1 X=1 010
10 1 0 I2 = X' 010 011 100
X X' X=1 X=1 011 100 101
D0 Q0 X=0 100 101 000
X=0 We move
D Q Z0 101 000 001
CLK 100 011 Q0 to the
X=0 110 ØØØ ØØØ columns.
Q1 Q0
111 ØØØ ØØØ
I0 s1 s0
I1 4:1 D1 Q1 Q2+Q1+Q0+
I2 z D Q Z1 QX
I MUX
3
CLK Q2Q1 0 00 01 11 10
We organize the state table 00 001 010 011 010
as a Karnaugh map: 01 011 100 101 100
Clock 11 ØØØ ØØØ ØØØ ØØØ
10 101 000 001 000
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.19 2011 - 2023 Feza BUZLUCA 10.20
http://www.buzluca.info http://www.buzluca.info

Digital Circuits Digital Circuits

In this example, we will use T flip-flops. T2 = (Q0+X)·(Q2+Q1) T1 = Q2'·X + Q2'·Q0 T0 = X'

Remember: X
Transition table for T flip-flop:
symbol QQ+ T Q2+Q1+Q0+
0 00 0 Q0X
Q2Q1 00 01 11 10
α 01 1 00 001 010 011 010
β 10 1 01 011 100 101 100 T2 Q2
1 11 0 11 ØØØ ØØØ ØØØ ØØØ T Q Z2
CLK
10 101 000 001 000 Q2'
By examining transitions (Q2→Q2+, Q1→Q1+, Q0→Q0+), we determine T2 , T1 , and T0 . Q1
T1 Z1
T2 T1 T0 T Q
CLK
Q0X Q0X Q0X Q1'
Q2Q1 00 01 11 10 Q2Q1 00 01 11 10 Q2Q1 00 01 11 10
00 0 0 0 0 00 0 1 1 1 00 1 0 0 1
01 0 1 1 1 01 0 1 1 1 01 1 0 0 1 T0 Q0
T Q Z0
11 Ø Ø Ø Ø 11 Ø Ø Ø Ø 11 Ø Ø Ø Ø CLK
Q2
10 0 1 1 1 10 0 0 0 0 10 1 0 0 1 Q0'
Q2'
Q1
T2' = Q0'·X' + Q2'·Q1' T1 = Q2'·X + Q2'·Q0 T0 = X' Clock
Q0
T2 = (Q0+X)·(Q2+Q1)
http://akademi.itu.edu.tr/en/buzluca/ http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.21 2011 - 2023 Feza BUZLUCA 10.22
http://www.buzluca.info http://www.buzluca.info

Digital Circuits

Implementation of synchronous
circuits using PLD

• Earlier, we looked at
implementing combinational
circuits using programmable logic
devices (PLDs).
• It is also possible to use PLDs to
implement synchronous circuits.
• For this purpose, we use PLD
units that include flip-flops.
• At the right, a 16R8 PAL circuit
is shown.
• Currently, synchronous circuits
are commonly implemented using
CPLDs and FPGAs.

http://akademi.itu.edu.tr/en/buzluca/
2011 - 2023 Feza BUZLUCA 10.23
http://www.buzluca.info