The National Higher School of Artificial Intelligence 2023/2024

Digital systems First Year

Solution

Assignment 05
Exercise 01
Consider the state diagram shown below. Implement the corresponding synchronous sequential circuit
by using JK flip-flop then D flip-flops.

Solution :

In this states diagram, we have two states = 2n  n = 1 (one Flip-Flop).

Transitions table of JK and D

Excitation table (Inputs + States (present and next) + Outputs + inputs of FFs)

Input Present state Next state Excitation inputs of FF

X Y Q Q+ J K D
0 0 0 0 0 x 0
0 0 1 0 x 1 0
0 1 0 0 0 x 0
0 1 1 1 x 0 1
1 0 0 0 0 x 0
1 0 1 1 x 0 1
1 1 0 1 1 x 1
1 1 1 1 x 0 1

Excitation equations of JK

Q 0 1
XY Q 0 1
XY
00 0 x 00 x 1
01 0 x 01 x 0
11 1 x 11 x 0
10 0 x 10 x 0
J = X.Y K = X’.Y’
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

Logic diagram of circuit based on JK Flip-Flop

X Y

J Q

CLK

Excitation equations of D :

Q 0 1
XY
00 0 0
01 0 1
11 1 1
10 0 1
D = XY + Q (X+Y)

Logic diagram of circuit based on D Flip-Flop

X Y

D Q

CLK

Exercise 02
Design the sequential circuit (by using D Flip-Flops) that detects the following sequence: 01101 (This
sequence is read bit/bit from the left to the right). The detector must assert an output 𝑧 = 1 when the
sequence is detected.

Solution :

What is a sequence detector? …10110

A sequence detector is a synchronous sequential circuit that detects X Sequence
Z
the specific bit sequence in the incoming bits. So if the circuit detects detector
CLK
the sequence then outputs 1 otherwise 0.

Steps for designing a FSM (sequential circuit)

 Draw a states-transitions diagram (also called : states diagram),
 Draw a states table,
 Select the type of Flip-Flops (D,T, JK) and draw the excitation table,
 Find the inputs boolean function for each FF (excitation equation) in term of present states and
Inputs,
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

 And similarly, find the outputs Boolean function,

 Draw the logic diagram circuit,

1. States diagram : sequence: 01101

Start
0-
Recovery (overlapping)
-
01101-
01-
Correct transition 1/1
(restart) but not
the best

011-
0110- 1/1
The best transition
(with covering)

2. States table (Excitation) :

We have 5 states < 2n  n = 3 Flip-Flops.
Each state (node) has 3 bits :
S1 = 000
S2 = 001
S3 = 010
S4 = 011
S5 = 100
S6, S7 and S9 are unused states

Input Present states Next states Output Excitation inputs of FFs

X Q2 Q1 Q0 Q2+ Q1+ Q0+ Z D2 D1 D0
S1 0 0 0 0 0 0 1 0 0 0 1
S2 0 0 0 1 0 0 1 0 0 0 1
S3 0 0 1 0 0 0 1 0 0 0 1
S4 0 0 1 1 1 0 0 0 1 0 0
U
S5 0 1 0 0 0 0 1 0 0 0 1
N S6 0 1 0 1 x x x x x x x
U
S S7 0 1 1 0 x x x x x x x
E
D S8 0 1 1 1 x x x x x x x
S1 1 0 0 0 0 0 0 0 0 0 0
S2 1 0 0 1 0 1 0 0 0 1 0
S3 1 0 1 0 0 1 1 0 0 1 1
S4 1 0 1 1 0 0 0 0 0 0 0
U
S5 1 1 0 0 0 1 0 1 0 1 0
N
U
S6 1 1 0 1 x x x x x x x
S S7 1 1 1 0 x x x x x x x
E
D S8 1 1 1 1 x x x x x x x
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

3. Equations of excitation inputs :

Q1Q0
Q1Q0
XQ2 00 01 11 10 XQ2 00 01 11 10 XQ2
Q1Q 0 00 01 11 10
00 0 0 1 0 00 0 0 0 0 00 1 1 0 1
01 0 x x x 01 0 x x x 01 1 x x x
11 0 x x x 11 1 x x x 11 0 x x x
10 0 0 0 0 10 0 1 0 1 10 0 0 0 1
D2 = X’ Q1Q0 D1 = XQ2 + X Q1’Q0 + X Q1Q0’
D0 = X’ Q1’ + Q1Q0’
= X (Q2 + (Q1 xor Q0))

4. Equations of output :

XQ2
Q1Q0 00 01 11 10
00 0 0 0 0
Z = X Q2
01 0 x x x
11 1 x x x
10 0 0 0 0

5. Logic diagram of the circuit :

X Z
D2 Q2

Q2

D1 Q1

Q1

D0 Q0
Q0

CLK
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

Exercise 03
Draw the State Transition Diagram for a Finite State Machine that, given a sequence of binary digits,
outputs 1 if the second most recently seen digit is 1 and outputs 0 otherwise.

For example, an input of 01100111 has the output 00110011.

Label all states and transition inputs/outputs you draw. You may or may not need all 6 states.

Solution :

0 1

For this question, we need states to track the value of the most recent input bit.

 If the most recent input bit was a 0, we know that the output for the next transition will be a 0 (as
an input of either a 0 or a 1 will cause the 2nd most recent bit to be a 0).
 If the most recent bit is a 1, we know that after another bit comes in, the 2nd most recent bit will
have been a 1, so we should output a 1.

We see that any transition leaving state 0 outputs a 0, and any transition leaving state 1 outputs a 1.
While there are possible implementations that could use more states, we only need 2 to represent this
problem as the state from which we are leaving will represent the value of the 2nd most recent bit.

Exercise 04
A four-state counter has states labeled as S0, S1, S2 and S3. It has two single-bit inputs : CL (clear)
and CO (count).

 When CL = 1, the next state becomes S0 irrespective of the present state and the value of CO.
 When CL = 0 and CO = 0, the next state remains the same as the present state.
 When CL = 0, on each successive application of CO = 1, states transitions as . . .
S0→S1→S2→S3→S0 . . ..

The circuit has one output, which becomes 1 only when the circuit is in state S3, otherwise the output
remains 0.

Draw the state diagram for this counter circuit.

 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

Solution :

The state diagram of the counter is shown below:

CL, CO = 1X/0 1X/0

01/0
S0 S1 00/0

1X/0 1X/0
01/0 01/0

00/1 01/1 00/0

S3 S2

Exercise 05
A recognizer has a single input X and two outputs (Z1 and Z2).
 The output Z1 becomes 1 each time the input sequence 101 is observed. Otherwise Z1=0.
 The output Z2=1 each time input sequence 011 is observed, otherwise Z2=0.
For example, for the input X={10101101}, the outputs are: Z1={00101001}, and Z2={00000100}.
1) Draw the Mealy style state diagram of this machine.
2) Deduce the FSM using a shift register and a minimum number of gates.

Solution :
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

Exercise 06
The logic implementation of a state machine (FSM – Sequential circuit) is shown in the figure below.
How many states does this state machine have? (Assume that it always starts from A=0, B=0)

D1 Q1 D0 Q0

A B
clk
Solution :

The excitation equations of Flip-Flops :

A = A’ xor B

B=A

A B
0 0 S0 Start
1 0 S2 Next state
0 1 S1 .
0 0 S0 .
etc etc etc
.
S3 (A=1, B=1) is never accessed (Unused state).

Number of states = 3

.
 The National Higher School of Artificial Intelligence 2023/2024
Digital systems First Year
Solution

Exercise 07
Analyze the sequential circuit in the figure below.

The excitation equations of Flip-Flops and output:

J = E xor Q0’

K = E Q0 ’

T = E nand Q1 = (E Q1)’

S = E Q0

States-Transitions Table

Input Present states Excitation inputs of FF Next states Output

E Q1 Q0 J K T Q1+ Q0+ S
0 0 0 1 0 1 1 1 0
0 0 1 0 0 1 0 0 0
0 1 0 1 0 1 1 1 0
0 1 1 0 0 1 1 0 0
1 0 0 0 1 1 0 1 0
1 0 1 1 0 1 1 0 1
1 1 0 0 1 0 0 0 0
1 1 1 1 0 0 1 1 1

States-Transitions Diagram :

0/0
00 01
1/0

0/0 1/0 1/1

0/0
11 10
0/0 0
1/1