CSCI-UA.0436 - Prof. Grishman

Assignment 1: Using Logisim

0.  Download Logisim and go through the tutorial.

1 . Construct the truth table for a 3-input odd-parity circuit: a circuit with three inputs and one output, where the output is 1 if and only if an odd number of the inputs are 1. 

2.  Using Logisim, design and draw a schematic of a 3-input odd-parity circuit. You may use AND, NAND, OR, NOR, and inverter gates in your circuit.

3.  If each gate in the circuit (from question 2) has a delay of 2 ns, what is the delay of your circuit?

4.  Design a circuit which takes as input a 4-bit unsigned integer X3X2X1X0 and outputs a 1 if and only if X > 11.  You may draw the circuit using Logisim or by hand.  (Hint:  what do all the input patterns which produce a 1 output have in common?)

5.  Prove that the NOR gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NOR gate.

Hint: first build an inverter from a NOR gate. Then use inverters and NOR gates to construct an OR gate and to construct an AND gate. You will need DeMorgan's theorem to build the AND gate.

Extra credit

Prove that a two-input multiplexer is also universal by showing how to build the AND, OR, and NOT functions using a multiplexer.

Due in one week: September 19st (until midnight)

How to hand this in:  For part 2, email the Logisim circuit as an attachment. Mail your homework to  grishman@cs.nyu.edu and smj340@cs.nyu.edu;  mark the mail CompArch -- Asgn 1 .  The remaining parts may be sent electronically or may be handed in, in hard copy, in class, next Wednesday (late homeworks in hard copy must be brought to 715 B'way, 7th Floor).