###
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.*
- 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.*
- 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?
- 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 X
_{0}.
- 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.*
- 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.
- 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.*
- What is the 16-bit, two's complement representation of -3?
Give
your
answer
in binary.
- 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?
- Given AND, OR, NOT gates and full adders, design a circuit for
doing 4-bit two's complement subtraction.
- 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.

- Write a sequence of MIPS instructions which put the absolute
value of $2 into $3.
- Write a MIPS instruction which will set $2 to 131,072 (= 2
^{17}
= 0000 0000 0000 0010 0000 0000 0000 0000_{2})

### The mid-term is Wednesday,
October 10th.