CSE370 Final Exam (8 June)
 

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 5 problems for a total of 100 points. The point value of each problem is indicated in the table below.

Each problem is on a separate sheet of paper. Write your answer neatly in the space provided. If you need more space (you shouldn’t), there are a couple of extra sheets at the end of the exam, 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 note. Please do not ask or provide anything to anyone else in the class during the exam.

Good luck.

Name:
ID #:

 
 
Problem
Max Score
Score
1
10
  
2
20
  
3
15
  
4
30
  
5
25
  
TOTAL
100
  
 

 

1. Combinational Logic (10 points)

You are to design a circuit that takes a 4-bit number as input (F8, F4, F2, F1) and generates an output which is 1 if the input number is one of the Fibonacci numbers between 2 and 15 and 0 otherwise. Recall that the program for assignment #9 computed the nth Fibonacci number. You may assume that the input is never 0 or 1. The most significant bit of the input is F8. Please use the Karnaugh map below for this problem.

(a) Write this function as a list of minterms (S m(...) notation).
 

(b) List the prime implicants for this function.
 

(c) List the essential prime implicants for this function.
 

(d) Find the minimal sum of products expression for this function.
 

(e) Draw a circuit diagram for the mimized function using only AND, OR, and NOT gates.
 

2. PAL/PLA/ROM Implementations of Combinational Logic (20 points)

The following three Karnaugh maps show three functions X, Y, and Z of the inputs A, B, C, and D.

(a) Implement the three functions above using the read-only memory (ROM) shown below. Place Xs where connections need to be made in the OR plane.

     
(b) Implement the three functions above using the programmable array logic (PAL) shown below. Place Xs where connections need to be made in the AND plane. Note that all outputs must be a sum of no more than three product terms. NOTE: please write the product term at the output of each AND gate.
     
     
(c) Implement the three functions above using the programmable logic array (PLA) shown below. Place Xs where connections need to be made in the AND and OR planes. Note that there can be no more than six total product terms for all three functions. NOTE: please write the product term at the output of each AND gate.
 
 
 

3. Sequential Logic (15 points)

(a) Develop the state diagram for a special 4-bit up/down counter. The counter never counts below 4 and never above 12. It has a reset input (R) that sets it to 8 and a direction input (D) that determines whether it counts up or down (up if D = 0 and down if D = 1). If the counter is reset to 8 and D is true then its successive states will be 8, 7, 6, 5, 4, 4, 4, . . . and it will stay at 4 until it is reset of D changes to 0.
 

(b) Write a Verilog module for the special up/down counter of part (a). Don't worry about precise syntax.
 

4. Implementation of Sequential Logic (30 points)

Below is the state diagram for a finite state machine that has one input and one output. You are to minimize the number of states (if possible), compose a symbolic state table, encode the states (state assignment), and derive the logic to implement the finite state machine.

The finite state machine performs a simple function. It takes an input bit stream and filters all strings of consecutive 1s into a single 1. Use a Moore design. Assume that you start in the initial state A where only 0s have been seen on the input (do not include a reset input for your machine, just assume it starts in the right state).

For example, if the input stream is 00010001111000111000 (the leftmost being the first input bit) and you are starting in state A, then the output will be 00001000000100000100. Note that a leading 1 will appear with a delay at the output.

Input:  00010001111000111000
Output: 00001000000100000100

 

(a) Minimize the number of states in the state diagram above, if possible. List any states that may be equivalent.
 

(b) Draw a symbolic state table for the original finite state machine.
 

(c) Determine an encoding for the states of the original state machine. How many bits of state are used in your machine? Explain why you chose the particular encoding you decided upon. Do not be concerned with the optimality of your choice.
 

(d) Derive the logic for the state machine. Do not draw a logic schematic, write Boolean functions for the input to each flip-flop and for the output.
 

5. Control Logic Design (25 points)

You are given the data-path below. Note that there are three registers. Two of these have a load control input, while the other loads a new value on every clock cycle. There are two tri-state drivers that connect the outputs of registers A and B to a common bus. Finally, there is an ALU that can perform two operations: pass Y, add X and Y. X is always the output of register C, while Y is the value on the bus.

(a) Show the register-transfer operations needed to implement an instruction that swaps the contents of the A and B registers (SWAP A, B). Make sure to clearly indicate how many states will be needed to implement the instruction and the value of each control signal in each state. Assume the instruction is already in the instruction register so there is no need to worry about fetching the instruction or incrementing a program counter.
 

(b) Show the register-transfer operations needed to implement an instruction that doubles the contents of the A register (TWOX A). Make sure to clearly indicate how many states will be needed to implement the instruction and the value of each control signal in each state. Assume the instruction is already in the instruction register so there is no need to worry about fetching the instruction or incrementing a program counter.