h1

Ultimate Technical Interview Question – The Standard Solution

January 24, 2008

OK, so I am getting tons of email with requests to post a solution for this question which was initially posted here.
I am going to post now what I consider the “standard minimal solution”, but some of you have come up with some neat and tricky ways, which I will save for future a post.
The basic insight was to notice that if you are doing a divide by 3 and wanna keep the duty cycle at 50% you have to use the falling edge of the clock as well.
The trick is how to come up with a minimal design, implementing as little as possible flip-flops, logic and guaranteeing glitch free divided clock.

Most solutions that came in, utilized 4 or 5 flip flops plus a lot more logic than I believe is necessary. The solution, which I believe is minimal requires 3 flops – two working on the rising edge of the clock and generating a count-to-3 counter and an additional flop working on the falling edge of the clock.

A count-to-3 counter can be achieved with 2 flops and a NOR or a NAND gate only, as depicted below. These counters are also very robust and do not have a “stuck state”.

count_to_3.png

The idea now is to use the falling edge of the clock to sample one of the counter bits and generate simply a delayed version of it.
We will then use some more logic (preferably as little as possible) to combine the rising edge bits and falling edge bit in a way that will generate a divide by 3 output (with respect to out incoming clock).

The easiest way (IMHO) to actually solve this, is by drawing the wave forms and simply playing around. Here is what I came up with, which I believe to be the optimal solution for this approach – but you are more than welcome to question me!

clk_div_by_3.png

and here is also the wave form diagram that describes the operation of the circuit, I guess it is self-explanatory.

clk_div_by_3_wave.png

One more interesting point about this implementation is that it does not require reset! The circuit will wake up in some state and will arrive a steady state operation that will generate a divide by 3 clock on its own. We discussed some of those techniques in the past when talking about ring counters – link to that post here.

Advertisements

5 comments

  1. very well explained. Good Job !


  2. cool man I was trying to find answer for a long time


  3. If you need more interview questions.
    Go throgh these links
    Php Interview Qeustions

    C Interview Qeustions

    Java Interview Qeustions


  4. hi,

    The solution is not seems to be optimal,

    u don’t need 3rd flop at all, Take clk, cntr_msb and cntr_lsb as input and design a logic. 🙂


  5. what FFs aare those..? r the first two T-ffs n 3rd one D-ff?



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: