CSCI-UA.0436 - Prof. Grishman

Practice Mid-Term

Note: the italicized comments indicate the main topics to be covered on the exam, but are not exhaustive. Any topic covered in the notes about combinational and sequential circuits is fair game on the exam.

The mid-term is closed book.   However, students may bring a single sheet of notes (letter, legal, or A4, written on both sides, with your name on the sheet) to the exam. 

Time and Frequency

You should know the units of time and frequency, and be able to convert between them.
  1. What is the clock period for a 200 Hz clock?  For a 200 MHz clock?

Combinational Circuits

You should be able to design a circuit (and compute its propagation delay), given a verbal or truth-table description of the circuit. You should be familiar with the basic circuit types: and, or, nand, nor, exclusive-or, and not gates; multiplexer, full adder, and decoder.
  1. Design an exclusive-or circuit using only AND, OR, and NOT gates.  What is the delay of this circuit if the delay of each individual gate is 200 ps?
  2. Given a 3-bit input X representing a 3-bit binary number, design a circuit to test whether X is greater than or equal to 5. If this condition is true, the output of your circuit should be a 1, otherwise 0. In your design, refer to the low order bit of X as X0.
  3. Suppose you are given a large box of 2-input multiplexers. Show how to connect them up to create an 8-input multiplexer. If the delay from input to output on the 2-input multiplexer is 10 ns, what is the delay of the circuit you have designed? Suppose you had to create an N input multiplexer; what would the delay be? How many 2-input multiplexers would you need?

Sequential Circuits

You should understand the function of the basic types of flip-flops (set-reset, D type, master-slave), and the reason for using master-slave FFs. You should be able to assemble a register file. From a description of a sequential procedure, you should be able to create a state diagram, a state transition table, and finally a circuit.
  1. Go through the process of designing a two-bit down counter. First, draw the state diagram. Second, write down the state transition table. Third, convert the transition table to a formula in Boolean algebra. Finally, convert the formula to a circuit and show how it would connect to FFs to create a complete counter circuit.
  2. Consider a two-bit up counter with a select input S. If S=0, the circuit acts as an up counter; if S=1, the counter goes to 0 on the next clock cycle (reset). Give the state transition diagram and table for this counter.  Design the counter circuit from this table.

Arithmetic

You should understand two's complement arithmetic and the design of adders and subtractors, including the carry-look-ahead adder, and be able to give the delay time of these circuits.
  1. What is the 16-bit, two's complement representation of -3? Give your answer in binary.
  2. Suppose you are given an adder for unsigned 16-bit binary numbers. What changes must you make to the circuit to use it as an adder for 16-bit, two's complement numbers?
  3. Given AND, OR, NOT gates and full adders, design a circuit for doing 4-bit two's complement subtraction.
  4. A sum-of-products circuit has a propagation delay = 3 gate delays.  Why can't we build a 16-bit adder using sum-of-products with this propagation delay?

MIPS

You should be able  to translate simple code segments given in C or Java into MIPS assembler, and answer questions about the MIPS instruction set.
  1. Write a sequence of MIPS instructions which put the absolute value of $2 into $3.
  2. Write a MIPS instruction which will set $2 to 131,072 (= 217 = 0000 0000 0000 0010 0000 0000 0000 00002)

The mid-term is Wednesday, October 10th.