CSE370 Final Exam Solution

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).

Sm(2,3,5,7,11,13)

b) List the prime implicants for this function.

There are five: B2B1'B0, B3'B2B0, B3'B1B0, B3'B2'B1, B2'B1B0

c) List the essential prime implicants for this function.

There are three: B2B1'B0, B3'B2'B1, B2'B1B0

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

B2B1'B0 + B3'B2'B1 + B2'B1B0 + B3'B1B0

or

B2B1'B0 + B3'B2'B1 + B2'B1B0 + B3'B2B0

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.



Given the truth-table above, it is obvious that the circuit implements a rotate function. It is, in fact, a 4-bit barrel shifter (i.e., a cyclic shifter) where the amount by which to rotate is specified by the control 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.


Other solutions are possible for X1 and X2 depending on how the equations are minimized and the don't cares utilized.

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 Moore )? 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.

Note that: D1 = in, D2 = Q1', and out = Q1'Q2'.

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

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?

The state 11 and 10 are equivalent because they have the same output (0) and the same (or equivalent) next states, 10 and 10, respectively for an input of 1 and 00 and 00, respectively, for an input of 0.

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: (two pairs of equivalent states that could be combined into one are shown shaded)

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.

The easiest state assignment is to use the last three input values seen as the state code. This will be easy to implement because we can use a simple shift register for the computing the next state function.

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.

D1 = input; D2 = Q1; D3 = Q2; (3-bit shift register)

output = Q1Q2 + Q2Q3 + Q1Q3 (majority function)

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.

Two state diagrams are provided below showing synchronous Mealy and Moore machine implementations, respectively.