h1

Ultimate Technical Interview Question – Take 2

January 31, 2008

Allow me to quote from Martin Gardner’s excellent, excellent book Mathematical Carnival (chapter 17):
When a mathematical puzzle is found to contain a major flaw - when the answer is wrong, when there is no answer, or when, contrary to claims, there is more than one answer or a better answer - the puzzle is said to be "cooked".

From the number of hits, it looks like the last post was quite popular. Therefore, I decided to give the problem some more thought and to try to find more minimal solutions – or as defined in the above quote “to cook this problem”.

My initial hunch was to try and utilize an SR latch somehow. After all it is a memory element for the price of only two gates. I just had a feeling there is someway to do it like that.
I decided to leave the count-to-3 circuitry, cause if we want to do a divide by 3, we somehow have to count…
Here is what I first came up with:

div_by_3_sr_1_cir.png

The basic idea is to use the LSB of the counter to set the SR flop and to reset the SR flop with a combination of some states and the low clock.
Here is the timing diagram that corresponds to the circuit above.

div_by_3_sr_1_wave.png

But! not everything is bright. The timing diagram is not marked red for nothing.
In an ideal world the propagation time through the bottom NOR gate would be zero. This would mean that exactly when the S pin of the SR latch goes high the R pin of the flop goes low – which means both pins are never high at the same time. Just as a reminder, if both inputs of an SR latch are high, we get a race condition and the outputs can toggle – not something you want on your clock signal. Back to the circuit… In our case, the propagation time through the bottom NOR gate is not zero, and the S pin of the latch will first go high, then – only after some time, the R pin will go low. In other words we will have on overlap time where both R and S pin of the latch will be high.

div_by_3_sr_1_prob.png

Looking back at the waveform, it would be nice if we could eliminate the second pulse in each set of two pulses on the R pin of the latch (marked as a * on the waveform). This means we just have to use the pulse which occurs during the “00” state of the counter.
This is easy enough, since we have to use the “00” from the counter and the “0” from the clock itself – this is just the logic for a 3 input NOR gate!

The complete and corrected circuit looks like this now:

div_by_3_sr_2_cir.png

And the corresponding waveform below. Notice how the S and R inputs of the SR latch are not overlapping.

div_by_3_sr_2_wave.png

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: