V22.0436  Prof. Grishman
Assignment 2: Combinational Circuit  Comparator
In this assignment, you are to design an 8bit comparator for unsigned
binary numbers and verify the design by simulating it using a popular procedural
language such as C, Pascal, or Java. You may use inverters and two and
threeinput AND, NAND, OR, NOR, exclusiveOR and exclusiveNOR ("equivalence")
gates. (A gate with an inverted input line should be treated as two separate
gates: the inverter and the gate.)
The input of an nbit binary comparator is two nbit numbers: A_{n1}
... A_{0} and B_{n1} ... B_{0}. There are
three outputs, labeled A<B, A=B, and A>B; for any input, exactly
one of these should =1.
Design suggestion: in analogy with the ripplecarry adder, you
can design a 1bit comparator and then hook these up to form a "ripple
comparator". The 1bit comparator would have five inputs; two
of these inputs would be the data bits, A_{i} and B_{i}.
The other three inputs, A<B_{in}, A=B_{in}, and A>B_{in},
would get information from the comparator to its left, indicating the relationship
between the bits to the left (between A_{n1} ... A_{i+1}
and B_{n1} ... B_{i+1}). The three outputs, A<B_{out},
A=B_{out}, and A>B_{out}, would represent the relation
between A_{n1} ... A_{i} and B_{n1} ... B_{i}.
Note that, in contrast to the ripple carry adder, here the information
ripples from left to right.
What to Submit:

A design for the circuit, starting from the basic logic gates listed above.
Don't draw one big circuit  if you use a ripple comparator, show the
structure of a 1bit comparator, and then (as a separate picture) show
how the 1bit comparators would be connected together. This emphasizes
the structure of the design and means you have much less to draw.

Determine the propagation delay of the circuit as a multiple of the propagation
delay of an individual gate.

Create a simulation of the circuit using a program. Use the same hierarchical
approach you used in designing the circuit. Submit a listing of this program.

Write a program to test this circuit. Submit a listing of this program,
and the test output. Can you exhaustively test this circuit?
All this should be bundled together and submitted by noon on February
17. Late assignments are penalized 5% after noon, and 10% for each
weekday late.
Extra Credit

How would you modify the circuit to compare two's complement signed numbers?

How would you modify the circuit to be faster, particularly for
large n?
Spring 1999