Review Questions for Exam 2

As you're sitting and reviewing for the second exam, think about your general preparation up to this point. The goal is for you to keep up with class material each week. If you've done so, the exam should be, for the most part, straight-forward, and the preparation should also be this way.

If you've decided "there's still next week" or "there's no HW, so why should I have to do 311" this week, there may be a lot to study. The course is partly about getting you to do the work that's necessary, even if there's no homework or quizzes. Ultimately, you're responsible for getting something out of the course, regardless of who's teaching the class. You can always find excuses why you didn't learn something, but it doesn't help you learn anything.

Anyway, onward and forward!

Format

The exam should have the following structure. The exam should be divided into four parts.

Combinational Logic
Sequential Logic
MIPS programming (functions, arrays, linkers)
Challenge Section

The first three parts usually make up about 100-110 points out of a 140 point exam. The last part is about 30-40 points.

Some students will only manage to complete the first 3 parts, and not be able to complete the rest of the exam. The exam is usually on the long side. Partial credit will be given. So, you might favor some incomplete answers if you get a sketch of the basic idea correct.

If you're concerned about time, then you may want to skip the programming questions and come back to them later. They will be worth more points this time.

Note: there are also circuit problems, so they can take some time to draw too.

The "Challenge" section has challenging questions. They can be much tougher than the average question. However, points are points, whether they come from the easier section or the challenge section. Occasionally, a challenge question will be easy, so it's worth reading them over quickly to see if any of them look easy to you.

The test is usually curved. I tend to rank you relative to the entire class. Historically, a C is about 70/140. That's only 50%. However, since it's curved, it may not always work out to be 70. Clearly, I prefer students to be in the 80-90 range minimum.

Usually, you need to average over 100 for an A. That leaves a very large A range (from 100-140).

We'll return exams after Spring Break.

Review Questions

On to the review questions. Some solutions to be posted throughout the weekend. Some comments are added in italics.

Sequential Logic

Note: you should have been able to come up with many of these questions on your own, based on class notes and on lectures. It's good practice to predict exam questions as some professors may not provide any practice questions at all, and expect you to figure out questions on your own. It's a useful skill to come up with such questions.

Draw a 3-bit parallel load register. Use D flip flops.
Draw a 3-bit asynchronous counter. Use T flip flops.
Draw a Moore machine for a counter which counts 00, 01, 10, and has a hold operation. Implement using T flip flops and a ROM.
What's the difference between a Mealy and Moore machine?
Come up with a Mealy machine, implement it using D flip flops.
Write the characteristic table for D and T flip flops.
Write the excitation table for D and T flip flops.
Explain the difference between characteristic tables and excitation tables.
How are excitation tables used to implement circuits?
Implement a T flip flop using D flip flops and logic gates.
Explain state.
Suppose a FSM has N distinct states. How many flip flops are required (at a minimum)?
One flip flop can store how much information?
What is a timing diagram?
Given a FSM, and a timing for some input, draw a timing diagram. (Would only show up on challenge section---it's not hard, but you would have to try it out once).
Draw an FSM that takes two bits of input at a time. These two bits are bits i from two arbitrarily long strings. Assume the two strings are being fed in from the most significant bits first to the least significant bits. At time unit 1, A_{n - 1} and B_n-1 are fed to the machine. At time unit 2, A_{n -
2} and B_n-2 are fed to the machine.
The FSM should output 00 if the two values are equal so far, 10 if string A has a larger value (assume UB), and 01 if string B has a larger value.
Draw the FSM.

Combinational Logic

Some questions are more for background, some are more realistic on an exam.

Combinational Logic is an implementation of what?
The behavior of a combinational logic circuit can be described in two ways. Which two?
Name the gates used in combinational logic.
Which logical operations are associative? Commutative?
What is a minterm?
Come up with an arbitary truth table using 3 variables, and write a sum of products expression.
Write a truth table for a full adder.
Design a 3-bit ripple carry adder. What assumptions did you make?
Now modify the adder so that it has an additional output V which is 1, if there is overflow, and 0 if not. What assumptions did you make?
Design a 4-1 MUX from 2-1 MUXes.
Design a 5-1 MUX from any "smaller" MUXes (2-1, 4-1).
Write a Boolean expression for all outputs of a 2-4 decoder with active-low enable, e.
Define functional completeness.
What gates are functionally complete?
Design a circuit that converts numbers from 3-bit 1C to 3-bit 2C.
Assume the gate delay is T. Write a formula/expression for the gate delay of an N-input AND gate implemented from 2-input AND gates.
Why is OR₂ different from OR₃?
Implement OR₂ using NAND gates.
Let S be the set of Boolean functions have n bits as input and 1 bit as output. What is the size of set S? Write a formula.

MIPS functions

What are the three types of MIPS instructions?
Each of the three types has different parts. Indicate which bits are used for what. (e.g., which bits are used for the opcode, etc).
What are the alternate names of the registers (e.g., $v0, etc.)?

Implement the following function in MIPS using the conventions given in class and the book:

int sum( int n )
{
  if ( n <= 0 )
     return 0 ;
  else
     return n + sum( n - 1 ) ;
}

jal puts the return address in a register. Is this helpful? What are potential problems?
Suppose you want to push $s0 and $s1 onto the stack. Write the MIPS instructions to do this.
Suppose you have an array with label arr. The size of the array is in register $a0. Furthermore, you have a system call to print integers. To make the system call, you do:
```
  li $v0, 1      # 1 means to print_int, li means load immediate
  li $a0, 10     # Puts the value to be printed in $a0
  syscall        # Prints the value
```
You may assume you have a la $rs, label instruction which loads the address given by label into register $rs
Implement as a loop.
Implement as a recursive function (write it in C first, then translate)
Explain caller-saved and callee-saved registers.
How is an address computed for a jump instruction?
How is an address computed for a branch instruction?
How is an address computed for a load instruction?
Give the names of the various kinds of addressing modes?

Miscellaneous

Draw the CPU given in the handout on Thursday.

Web Accessibility