-1
$\begingroup$

I have an exam tonight and I'm reviewing my midterm exam. I got this question completely wrong, with no solution given.

b) [10 marks] Consider implementing the logic formula 'signal 1' below as a
hardware circuit without any optimization.  You have 2-input 'AND' gates
that settle in 125 ps, 2-input 'OR' gates that settle in 150 ps, and
infinitely fast wires.  After all (original) inputs have been asserted, how
long does it take the circuit to settle?  Show any numerical calculations.

signal 1 = (p \/ q \/ r) \/ (s /\ t)

                                                               ans: ____ ps

I had no idea what to do so I simply multiplied every AND gate I saw by 125ps and every OR gate I saw by 150ps. I know this is not how to do it because of the number of gates. Can someone please explain this problem to me?

$\endgroup$
  • $\begingroup$ Am I correct that the circuit should reflect the structure of the formula, without using associativity (which would allow to shorten the time)? I also consider \/ as left associative. So (p \/ q \/ r) takes two cascaded or gates, which requires 300ps. Then (s/\t) takes 125ps, but is done at the same time, so that you can ignore it. Then you OR the two results which takes 150ps to be added to the previous 300ps. And that makes 450ps. Just draw the picture and look at maximum time from entry to exit. considering each entry in turn. Best of my very old and unreliable knowledge of the topic. $\endgroup$ – babou Apr 17 '15 at 15:38
0
$\begingroup$

This is the circuit corresponding to the logic formula 'signal 1', withhout any optimization.

_p_
   \
    OR_ 
_q_/   \
        OR_
_r_____/   \
            OR__
_s_        /
   \      /
    AND__/
_t_/

The signal takes 150ps to stabilize after the first OR gate, thus providing correct input for the second which then takes another 150ps to provide a correct input to the last Or gate. Total time is 300ps.

In the same time, the signal from s and t entries is ANDed in 125ps, so that it already stabilized and ready for the last OR gate when the previous one is ready after 300ps.

Thus the last OR gate can stabilize on correct signal after 300ps, and takes an additional 150ps to do that, bringing the whole time to 450ps.

One (longish) way to get the result is to check every path from an entry to an exit, adding the duration of every gate encountered. The highest value obtained is the answer. The previous way of computing is better.

The optimized version

Using OR associativity, you could change the formula to:

signal 2 = (p \/ q )\/ (r \/ (s /\ t))

which corresponds to the circuit:

_p_
   \
    OR________ 
_q_/          \
               \
_r______        OR__
        \      /
_s_      \    /
   \      OR_/
    AND__/
_t_/

This circuit would take only 425ps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.