h1

Puzzle #8 – Clock Frequency Driver – Solution

March 26, 2008

It’s been a while since I posted some puzzles or solutions to puzzles. I noticed that I concentrated lately more on tricky circuits and fancy ideas but neglected the puzzle section. Some readers asked me to post some more puzzles. Before I can do that, I have to first clear the list of all unsolved puzzles.

The clock frequency driver puzzle drew little attention compared to the others and I got only one complete and correct solution for it.
What follows is my own solution which I hope will be easily understood.

The requirement was to have a NAND gate as the last output stage with one input driven by a rising edge triggered memory element and the other by a falling edge triggered memory element.
A look at the NAND gate truth table reveals that somehow the inputs have to toggle between “11” (to generate a logical “0”) and “10”, “00” or “01” (to generate the logical “1”) on each and every clock edge!

I will now describe the solution for a certain case while the value in brackets will represent the analogous opposite case.
This in tern means (and without loss of generality) that with each rising[falling] clock edge the output state of both flops should be “11”. On the falling[rising] edge we should have the states “00”, “01” or “10”.

The state “00” can be immediately eliminated because the transition “00” –> “11” means we have to have both bits change on the rising[falling] edge together.
we are left with the following possible cases for the transitions (“r” marks a rising edge transition, “f” a falling edge transition):

  1. “10” r–> “11” f–> “10”
  2. “10” r–> “11” f–> “01”

Looking at the first option reveals that the rightmost bit needs to change on the rising edge from “0” to “1” and on the falling edge from “1” to “0” – this is not possible or in contradiction to the rules.
The second option looks promising – the rightmost bit changes from “0” to “1” on the rising edge, the left most from “1” to “0” on the falling edge – so far so good… but, let us continue the pattern:

“10” r–> “11” f–> “01” r–> “11”

Each second state has to be “11”. After continuing the sequence for one more step we see that now the rightmost bit changes from “0” to “1” on the rising edge, but the immediate previous transition had it change on the falling edge, therefore we get again a contradiction!

We conclude that having a NAND on the output is impossible.

As mentioned before Mark Wachsler sent his own solution long time ago. Here it is in is own words:

I’m assuming the question is, is it possible to do something like this:

always @ (posedge clock) p <= something;
always @ (negedge clock) n <= something else;
assign out = ~ (p & n);

and have out toggle on every transition of the clock?

If so, the answer is no.

Proof by contradiction:
1. Assume it can be done: out toggles on every transition of the clock.
2. We know p and n never change simultaneously, so for out to toggle,
either p or n must be 1.
3. So it may never be the case that p == 0 and n == 0.
3. Since they can’t both be zero, and they never change
simultaneously, at least one of them must always be 1.
4. But if n is always one, out can’t have a transition on negedge.
And if p is always one, out can’t have a transition on posedge.
5. Therefore there are some clock edges on which out doesn’t toggle.

So it can’t be done.

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: