CSE370 Final Exam Solution
 

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.

    The circled connections represent don't cares and are optional.
     
(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. The two larger prime implicants of X, used in the PAL implementation, have to be split as the PLA only supports a total of 6 product terms. Fortunately, the two can be reconstructed from the prime implicants of the other two functions.
 
 
 
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. module special_counter (clk, reset, D, cnt3, cnt2, cnt1, cnt0)

  input clk, reset, D;
  output cnt3, cnt2, cnt1, cnt0;

  reg [3:0] cnt;

  always @(posedge clk) begin
    if (reset)
      cnt = 8; // reset to 8
    else if (D)
      if (cnt > 4) cnt = cnt - 1; // count down if > 4
      else cnt = 4; // not necessary
    else
      if (cnt < 12) cnt = cnt + 1; // count up if < 12
      else cnt = 12; // not necessary
  end

  assign cnt3 = cnt[3];
  assign cnt2 = cnt[2];
  assign cnt1 = cnt[1];
  assign cnt0 = cnt[0];

end
 

 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. A and E are equivalent states as are B and D. The reduced state diagram is shown below.

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

     
    current state
    input
    next state
    output
    A
    0
    A
    0
    A
    1
    B
    0
    B
    0
    C
    0
    B
    1
    B
    0
    C
    0
    E
    1
    C
    1
    D
    1
    D
    0
    C
    0
    D
    1
    D
    0
    E
    0
    A
    0
    E
    1
    B
    0
     
(b) 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.
    The state assignment (A = 100, B = 000, C = 001, D = 010, E = 110 shown below as CS1, CS2, and CS3 for current state and NS1, NS2, and NS3 for next state) was derived by setting one of the three state bits (CS3) to be able to be directly used as the output (this distinguishes state C as 001). Only two other bits are needed for the other four states. State B was set to 000 as it is the most frequently occuring next state. A and E were given similar codes as were B and D as they are equivalent states. E was assigned the code 110 as it is the least frequently occuring next state. Other state not shown in the table (011, 101, and 111) are don't cares.

     

    current state
    input
    next state
    output
    100
    0
    100
    0
    100
    1
    000
    0
    000
    0
    001
    0
    000
    1
    000
    0
    001
    0
    110
    1
    001
    1
    010
    1
    010
    0
    001
    0
    010
    1
    010
    0
    110
    0
    100
    0
    110
    1
    000
    0
     
(c) 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. NS1 = CS1 input' + CS3 input'
NS2 = CS3 + CS1' CS2 input
NS3 = CS1' CS3' input'
output = CS3 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.
     
    cycle
    operation
    AtoBus
    BtoBus
    ALU
    LoadA
    LoadB
    1
    C ¬ A
    1
    0
    Pass
    0
    0
    2
    B ¬ C and C ¬ B
    0
    1
    Pass
    0
    1
    3
    A ¬ C
    X
    X
    X
    1
    0
     
(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.

 

cycle
operation
AtoBus
BtoBus
ALU
LoadA
LoadB
1
C ¬ A
1
0
Pass
0
0
2
C ¬ C + Y
1
0
Add
0
0
3
A ¬ C
X
X
X
1
0