CSE 140 Components and Design Techniques for Digital Systems - HW6: Finite State Machine (FSM)
Due: Thu 5/18/2023, 11:00 AM PDT
NAME ___________________ PID ___________________
COLLABORATORS _____________________________________
Assignments must be completed individually. To get started, navigate to the response template GDoc and click on “Make a copy” from the “File” menu. Concisely respond to all prompts, save the file as a PDF, then upload to GradeScope, and mark all pages. While we accept physically written/annotated submissions, type out or insert digital images (ex. “Drawing” from the “Insert” menu) as far as possible. Contain your responses to the answer boxes, which you may resize. Please highlight or circle your final answer(s) for questions where you must show work. Review course material like lecture slides, recordings, and Piazza to best use our office hours, for guidance.
Question 1: Professor Rick decides to continue his journey by visiting Grinnell Glacier at Glacier National Park. He will be going on a journey around the park for a couple of weeks to explore the beauty of the great outdoors. On his way there, he has been tinkering with his trusty computer, trying to build finite state machines that can recognize different patterns. Help Professor Rick build two FSM in parts a and b that accepts the following string as its input:
X = 10010
You can draw your diagrams by hand or using https://www.cs.unc.edu/~otternes/comp455/fsm_designer/
a) Build a Moore FSM with the least number of states that accepts X.
b) Build a Mealy FSM with the least number of states that accepts X.
Question 2: Professor Rick has a knack for designing finite state machines that are very efficient. As soon as he set foot on the trail, he was struck by inspiration and now wants to design a state machine using one-hot encoding. Help Professor Rick by decoding the state machine and answering the question below.
The diagram above is drawn with: https://www.cs.unc.edu/~otternes/comp455/fsm_designer/ .
Use the following one-hot encoding for the states:
S0: 0001
S1: 0010
S2: 0100
S3: 1000
a. Given the finite state machine above, write down the excitation table (without don’t care). The bits of one-hot encoding for the states is represented as p3, p2, p1, and p0, where p0 is the right-most bit of the encoding. The input is represented as b. The rows in the table below are enough to record all possibilities.
Inputs | Outputs | |||||||
p3(t) | p2(t) | p1(t) | p0(t) | b | p3(t+1) | p2(t+1) | p1(t+1) | p0(t+1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b. Minimize the states in the FSM above. Draw it below. Extra states can be left empty.
Question 3: As Professor Rick continues his walk along the trail, he surprisingly stumbles across a piece of paper with a complex state diagram that encodes a string of 1s and 0s into a different string of 1s and 0s. He wants to find a way to convert the given Mealy machine into a Moore machine. Help Professor Rick by completing the questions below.
a) Write a state table for the Mealy Machine.
Current State | b = 0 | b = 1 | ||
Next State | Output (y) | Next State | Output (y) | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b) Write the state table for an equivalent Moore Machine and how it relates to the Mealy states (with no more than eight states including the new states. )
Current State | Output | b = 0 Next State | b = 1 Next State | How it relates to Mealy States |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c) Draw the new Moore Machine, using no more than eight states (Assume that we don’t care about the output when we reset)
Question 4: Once the circuit was completed, Professor Rick found a second complex state diagram when he flipped over the paper. He wants to take a step further and draw out the FSM circuit for the following diagram. Help Professor Rick complete the steps below.
Given the state diagram below, design a finite state machine step by step; each state is represented by two bits in the form of Q1Q0 and transitions are represented as input/output.
a) Based on the state diagram above, first fill in the state table below;
Present State | Input | Next State | Output | ||
Q1 | Q0 | X | D1 | D0 | Y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b) After filling the state table above, using K-map to come up with minimal expressions of next state and output Y. You need to use Q1, Q0 and input x to write these expressions (You can use XOR gate to minimize the SOP);
c) Finally, draw the circuit for the FSM.
