CSE370
Final Exam (
Please read through the entire examination first! This exam was designed
to be completed in 100 minutes (one hour and 40 minutes) and, hopefully, this
estimate will be reasonable. There are 4 problems for a total of 100
points. The point value of each problem is indicated in the table below.
Each problem and sub-problem is on a separate sheet of paper. Write your answer neatly in the space provided. If you need more space (you shouldn't), you can write on the back of the sheet where the question is posed, but please make sure that you indicate clearly the problem to which the comments apply. Do NOT use any other paper to hand in your answers.
The exam is CLOSED book and CLOSED notes. Please do not ask or provide anything to anyone else in the class during the exam. Make sure to ask clarification questions early so that both you and the others may benefit as much as possible from the answers.
Good luck and have a great winter break.
Name:
ID#:
|
Problem |
Max Score |
Score |
|
1 |
15 |
|
|
2 |
20 |
|
|
3 |
35 |
|
|
4 |
30 |
|
|
TOTAL |
100 |
|
1. Boolean Algebra (15 points)
(a – 5 pts) The following circuit implements
a Boolean function of 5 variables (A, B, C, S1, and S2). It uses five 4:1 multiplexers. Note that S1 and S2 are simply used to
select one of four functions of A, B, and C. Write the equations for these four functions. We’ll call them F0, F1, F2, and F3. Inputs to the multiplexer are numbered
from 0 to 3 top to bottom, control inputs are high-order on the left, low-order
on the right.
F0 =
F1 =
F2 =
F3 =
(b – 5 pts) We will now use a new kind of programmable
logic called a DAL (Decoder Array Logic) to re-implement our logic
function. The schematic of a very
useful DAL370V4 component is given below.
Show which connections need to be made to the OR gates to implement Z
(show the connections as an X at the intersection of the OR input line and the
decoder outputs). Decoder outputs
are numbered 0 to 7 from top to bottom, control inputs are high-order on the
left, low-order on the right.
(c – 5 pts) On the other hand, it might be
more efficient to implement this function in a
2. Sequential Logic (20 points)
(a – 5pts) You are given a basic edge-triggered D-type flip-flop. Your task is to turn it into a new kind of flip-flop that we’ll call a toggle (or T-type) flip-flop. It will have two inputs in addition to the clock signal: R, a synchronous reset signal; and T, the toggle input. When T is high at a positive clock edge, the value of Q will become the opposite of what it was previously. When T is low at a positive clock edge, the value of Q will not change. Using only simple gates (OR, AND, NOT, XOR – with as many inputs as you need) around the D-FF, create a T-FF. Fill in the equation for D as well as drawing a circuit around the D-FF below left. Your objective is to create a module like the T-FF symbol below right.
D = f(R,
T, Q) =
(b – 10 pts) By now, you have your T-FF ready to go. Design a reset-able 4-bit binary up-counter with enable using your new T-FF as the replicated component. Four of them are provided below. Draw your logic around them. Again, you should only need to use simple gates (with any number of inputs). Clearly label: the reset (RESET) signal for the entire counter; 4 output bits (labeled with LSB – least-significant bit – and MSB – most-significant bit – from left to right); and the counter’s enable (ENABLE) signal. When enable is low, the counter should not change value. When ENABLE is high, it should count to the next binary value.
(c – 5 pts) Do you foresee any issues with making
this type of counter into a longer counter (say, 32 bits long)? Write a couple of sentences at most.
3.
For this problem, you will implement a
finite-state machine using the parts provided below. However, you’ll have to figure out what the parts can do for
you by reading their Verilog models.
Read these Verilog descriptions carefully.
(a – 10 pts) What are the two components you’ve been provided? Describe the functions implemented by Thing_1 and Thing_2 with at most a couple of sentences for each. Be specific, complete, and relate them to parts you already know.
Thing_1 is a ….
Thing_2 is a ….
(b – 10pts) In one of the lab assignments this quarter, you
implemented a finite-state machine to play a simple “tug-of-war” game using two
push buttons and seven LEDs. The
state diagram for that FSM is given below. You can assume you have the two inputs, L and R, they are
high for exactly one cycle whenever the left and right push buttons are
pressed. 
For
this problem, you will re-implement the state machine using the parts provided
in part (a). Begin by completing
the symbolic state table below.
You will need to use Thing_1 to realize your state. First, choose an encoding for state S1
through S6 that will be compatible with using Thing_1, then complete the state
table below (using symbolic states).
Start by entering the next state for each possible state
transition. Then, fill in the
values for EN and DIR that you will need to make that state change occur in
Thing_1 (make sure to use don’t cares).
RESET will be connected to the CLR input of Thing_1.
(c – 5 pts) Derive equations for EN and DIR from the table in part (c). You do NOT need to use K-maps, in fact, it is NOT recommended you do so as they have high dimensionality. Instead, exploit the don’t cares to come up with the simplest functions you can of L, R, and the current state of Thing_1 (Q3, Q2, Q1, and Q0).
EN =
DIR =
(d – 10 pts) Now, it is time to wrap up our tug-of-war game. Show, how you would wire up the
components provided below: Thing_1, Thing_2, and the bank of seven LEDs. Use whatever simple gates you need to
realize the functions for EN and DIR you derived in part (c). Clearly label the L, R, RESET, and CLK
inputs to your completed circuit.
You should only need wires to connect to the inputs and outputs of
Thing_2 and the LEDs.
4.
The state diagram below is the one we used in lecture to describe a 3-value-key combinational lock.
However,
the program code we used did not correspond to this state diagram exactly. A more accurate rendition is the state
diagram shown below. Note that it
consists of two parallel finite state machines that communicate through two
signals (set_err and err). The
machine with two states is a
(a – 5 pts) Below are two symbolic state tables. The one for the 6-state FSM needs to be completed. The one for the 2-state FSM is already completed. Complete the first state table – use symbolic states.
Symbolic state table for the 6-state FSM:
Symbolic state table for the 2-state FSM:
(b – 10 pts) Select a state encoding for the two state machines:
ERR =
NO_ERR =
S1 =
S2 =
S3 =
S4 =
OPEN =
NO_OPEN =
Explain
in a few sentences why you chose the state encoding above.
(c – 5 pts) Complete the Verilog description for the 2-state FSM provided below:
module FSM_2 (clk, reset,
set_err, err);
input clk, reset, set_err;
output err;
reg [ ___ : ___ ] state;
parameter ERR = ______ ;
parameter NO_ERR = ______ ;
(d – 5 pts) Complete the Verilog description for the 6-state FSM provided below:
module FSM_6 (clk, reset,
equal, enter, err, set_err, mux, unlock);
input clk, reset, equal, enter, err;
output set_err, unlock;
output [2:0] mux;
reg [ ___ : ___ ] state;
parameter S1 = ______ ;
parameter S2 = ______ ;
parameter S3 = ______ ;
parameter S4 = ______ ;
parameter OPEN = ______ ;
parameter NO_OPEN = ______ ;
(e – 5 pts) Why was the set_err output of the 6-state FSM made to be an asynchronous Mealy output? Would our combinational lock still function properly if this FSM were realized as a synchronous Mealy machine?