EEE 21 AY 2017-2018 Problem Set
DUE: Tuesday 21 November 2017 / 5:30 pm EEEI Admin Office (EEE 21 Submission Box)
Instructions:
1. Write your name, student number, large class section (TLM or HLM) and DC section on the top
right hand side of all pages of you answer sheet. Staple the sheets together.
2. Label the start of each part prominently. Show all your solutions. Answers without supporting
solutions (when applicable) will not be given credit.
3. Number the pages of your answer sheet.
4. Use one side of your answer sheet only. Do not write at the back.
5. There are ~200 of you in all so please help us make the task of checking as easy as possible.
Write neatly and BOX ALL FINAL ANSWERS.
=========================================
PROBLEM GROUP 1: Sequential Circuit Analysis
Figure 1.1 Sequential Circuit for Problem Group 1
1A. Given the sequential circuit above, draw the state diagram. Show your solution including the:
i. equations for the flipflop inputs (use DA, DB, and DC to differentiate between the inputs of the
flipflops) and system outputs in terms of system inputs and flipflop outputs, and the
ii. state transition table which includes the excitation inputs, system input and output.
Use the table headers indicated in Table 1.1.
Current System Excitation Next States System
States Input Inputs Output
A B C X DA DB DC A B C Z
Table 1.1. State Transition Table Headers for Problem Group 1
1B. Is the given circuit a Mealy or a Moore machine? Explain.
1C. Bonus: What is the function of the circuit? What is the corresponding output sequence Z for the input
sequence X = 0001011011101001010?
EEE 21 AY 2017-2018 Problem Set
DUE: Tuesday 21 November 2017 / 5:30 pm EEEI Admin Office (EEE 21 Submission Box)
PROBLEM GROUP 1: Sequential Circuit Analysis
A.
FlipFlop Inputs System Output
DA = AC+B Z = BCX
DB = C
DC = X(A+B+C)
Current System Excitation Next States System
States Input Inputs Output
A B C X DA DB DC A B C Z
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0 1 1 0
0 1 0 0 1 0 0 1 0 0 0
0 1 0 1 1 0 1 1 0 1 0
0 1 1 0 1 1 0 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0
1 0 0 0 1 0 0 1 0 0 0
1 0 0 1 1 0 0 1 0 0 0
1 0 1 0 0 1 0 0 1 0 1
1 0 1 1 0 1 1 0 1 1 0
1 1 0 0 1 0 0 1 0 0 0
1 1 0 1 1 0 1 1 0 1 0
1 1 1 0 1 1 0 1 1 0 0
1 1 1 1 1 1 1 1 1 1 0
The blue arrows correspond to X=0, black arrows to X=1. Z=1 only for arrows from 001 to
010, and from 101 to 010, other arrows result to Z=0. In your answers, transition arrows
must be labelled input/output.
100
Z=1
000 001 010 Z=1
101
011
110
111
B. The circuit is a Mealy machine because the output Z depends on the system input X seen
from the equation of Z which is Z = BCX.
C. Bonus: The circuit outputs 1 when it detects 010 sequence until 100 is detected. After 100
is detected, the output is always 0 regardless of what the input is.
X = 0001011011101001010
Z = 0000100000000100000
EEE 21 AY 2017-2018 Problem Set
DUE: Tuesday 21 November 2017 / 5:30 pm EEEI Admin Office (EEE 21 Submission Box)
PROBLEM GROUP 2: State Minimization
2A. Given the state diagram of a sequential
circuit in Figure 2.1:
i. Create the state transition table.
ii. Reduce the state table by using:
a. Inspection Method
b. Implication Method
iii. Which states are equivalent?
iv. Draw the reduced state diagram.
2B. Given the State transition table in Table 2.1:
i. Without minimization, how many
flipflops should be used to implement
the circuit for the state table above?
Looking at the table only, is this a
mealy or moore circuit? Figure 2.1: State Diagram
ii. How many classes are formed initially
Present Next State / Output
using reduction by partitioning?
Enumerate all and identify the states State X = 00 X = 01 X = 10 X = 11
belonging to each class. A E/1 C/0 B/1 F/1
iii. Perform reduction by partitioning and B C/0 F/1 E/1 B/0
create the reduced state transition C B/1 A/0 D/1 F/1
table.
D G/0 F/1 E/1 B/0
iv. Which states are equivalent? How
many flipflops are needed to E C/0 F/1 B/1 E/0
implement the minimized state table. F C/1 F/1 D/0 H/0
G D/1 A/0 B/1 F/1
H B/1 C/0 E/1 E/1
Table 2.1: State Transition Table
2Ai.
Present Next State / Output
State Input = 0 Input = 1
a a/0 b/0
b c/0 d/0
c a/0 d/0
d e/0 f/1
e a/0 f/1
f g/0 f/1
g a/0 f/1
2Aii.a. Inspection Method
Present Next State / Output Present Next State / Output
State Input = 0 Input = 1 State Input = 0 Input = 1
a a/0 b/0 a a/0 b/0
b c/0 d/0 b c/0 d/0
c a/0 d/0 c a/0 d/0
d e/0 f/1 d e/0 d/1
e a/0 f/1 e a/0 d/1
f e/0 f/1 Step 2: d = f
Step 1: e = g Final answer
EEE 21 AY 2017-2018 Problem Set
DUE: Tuesday 21 November 2017 / 5:30 pm EEEI Admin Office (EEE 21 Submission Box)
2Aii.b. Implication Method
Step 1: cancel out states Step 2: write out necessary equivalent
states
b
ac
b
bd
c
c bd ac
d X X X
d X X X
e X X X
e X X X ae
f X X X
f X X X eg ag
g X X X
g X X X af ag
a b c d e f
a b c d e f
Step 3: check for state equivalency Final answer:
correctness e=g
ac d=f
b
bd
Present Next State / Output
c bd ac State Input = 0 Input = 1
a a/0 b/0
d X X X
b c/0 d/0
c a/0 d/0
e X X X ae
d e/0 d/1
eg e a/0 d/1
f X X X ag
()
g X X X af ag
a b c d e f
2Aiii. Equivalent states:
e & g. d & f.
EEE 21 AY 2017-2018 Problem Set
DUE: Tuesday 21 November 2017 / 5:30 pm EEEI Admin Office (EEE 21 Submission Box)
2Aiv.
2B.i. the number of flipflops needed are correlated to the number of states, following the
equation:
2number of flipflops >= number of states
since we have 8 states, there must be 3 flipflops.
Mealy circuit, because there are different outputs possible for each current state
[Link]. There will be 3 classes.
Class 1: 1011 (A,C,G,H)
Class 2: 0110 (B,D,E)
Class 3: 1100 (F)
[Link].
Step 1:
Class 1 2 3
State A C G H B D E F
Next Class 2123 2123 2123 2122 1322 1322 1322 1321
Step 2:
Class 1: 1011 (A,C,G)
Class 4: 1011 (H)
Class 1 2 3 4
State A C G B D E F H
Next Class 2123 2123 2123 1322 1322 1322 1324 2122
Final Answer
Present Next State / Output
State X = 00 X = 01 X =10 X = 11
S1 S2/1 S1/0 S2/1 S3/1
S2 S1/0 S3/1 S2/1 S2/0
S3 S1/1 S3/1 S2/0 S4/0
S4 S2/1 S1/0 S2/1 S2/1
[Link].
A&C&G
B&D&E
There are 4 states, therefore, we need 2 flipflops.