CSE370 Final Exam (16 December)

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 6 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 open book and notes as long as they are your own. 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
5
2
10
3
15
4
20
5
25
6
25
TOTAL
100

1. Combinational Logic Design (5 points)

You are to design a circuit that takes a 4-bit number as input (B3, B2, B1, B0) and generates an output which is 1 if the input number is prime and 0 otherwise. Recall that the first few prime numbers are: 2 (for which B3=0, B2=0, B1=1, B0=0), 3, 5, 7, 11, and 13. Please use the Karnaugh map below for this problem.


a) Write this function as a list of minterms (Sm(...) 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.



2. Mux-based Implementation of Combinational Logic (10 points)

Describe what the following circuit does in one or two sentences. Begin by filling in the truth-table below. The four components are all 4:1 multiplexers (S1=1 and S0=0 connect input 2 to the single output) with identical select inputs.



3. PAL/PLA/ROM Implementations of Combinational Logic (15 points)

a) Implement the following functions of three variables (A, B, and C) using a read-only memory (ROM). Note that A=0, B=1, C=1 corresponds to minterm 3.

X1 = m(0,2,5,6,7) + d(1)

X2= m(5,6) + d(7)

X3= m(0,1,3,5)


b) Implement the same functions using a PAL.


c) Implement the same functions using a PLA.



4. Sequential Logic Analysis (20 points)

Is the finite state machine implementation below Moore or Mealy (fill in here ) ? Complete the timing diagram for the circuit. Derive and sketch a state diagram for the state machine by first completing the state table provided below. Does this machine have any equivalent states and if so what are they?

a) Complete the timing diagram below.


Complete the state table below.

in
Q1
Q2
D1
D2
out
0
0
0
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1

b) Draw the state diagram:











c) Are any of the states equivalent? In other words, do they have the same output and lead to the same (or equivalent) next states for the same value of the input?



5. Finite State Machine Design (25 points)

Design a state machine for the following problem. You should show:

(a) the state diagram,

(b) the state assignment (and a justification for why you think it will lead to less logic),

(c) the next state equations (in sum-of-products form - its not necessary to minimize).

This state machine has one input and one output. The input is a serial bit stream and the output on each cycle is a 1 if there were at least two 1s in the previous three input bits and is a 0 otherwise. You must use a Moore design. Assume that you start in an initial state 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). Try to reuse states as much as possible.

Example: 

          Input:  00010100110101100
                       |   | 
          Output: 00000100011101110

a) Draw the state diagram:











b) Provide a state assignment by listing each state in your state diagram and the code you will use to identify it. Give a reason why you picked the particular state assignment and why it may lead to less logic than another state assignment.








c) Derive the next state equations for each of the state bits and for the output in sum-of-products form (don't bother minimizing). Show all your work on this sheet and/or the next.






6. Control Logic Design (25 points)

Given below is a data path comprising two registers, an ALU and a data bus. The ALU has one control signal, Op, which indicates the operation the ALU performs:

Op = 0 : output = A+B

Op = 1 : output = A-1

The ALU also generates an output signal Zero which is 1 if the output of the ALU is 0.


Design a control circuit which waits for a start signal and then computes .

This is the same computation performed by our test program for the processor of assignment #9. This time, however, we will implement that entire program in a state machine. The state machine waits for a Start signal to be asserted. When this occurs, you may assume that the value of N is stored in register A. There are load control signals for each of the two registers and a clear input for the B register. The result should be stored in the B register when the instruction completes. At this point, the control should wait for another Start signal so that it can perform the operation again.

a) Draw a block diagram for the control circuit clearly showing all inputs and outputs.












b) Draw a state diagram for the control circuit. Clearly show all outputs.











Comments to: cse370-webmaster@cs.washington.edu (Last Update: )