Archive for March, 2008

h1

Puzzle #9 – The Snail – Solution

March 27, 2008

I will keep this post short. First make sure you take a look at the original puzzle – link here.

The shortest sequence is 6 bits long and is “100110” (or its inverse “011001”). The smallest amount of bits needed to determine a direction is 5, i.e. any 5 consecutive bits seen by the snail could help him determine the direction home.

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.

h1

Cyclic Combinational Circuits

March 7, 2008

As one of my strange hobbies, I sometimes try to search the web for interesting PHD thesis works. I came across this one a while back and thought it would be interesting to share.

We always hear how bad combinational cyclic loops are. Design Compiler even generates a reports to help us detect them. In the normal ASIC flow combinational loops are very dangerous, hard to analyze and characterize for timing. But here comes this Dissertation work by Marc Riedel and highlights a special set of cyclic combinational circuits which offer several important advantages.

I will try to explain the basic principle by going through an example, but make sure to read his PHD thesis, it is well written and easily understood.

As an example we will look at the very simple case depicted below:

cyclic_combinational1.png

Notice that it has 5 inputs: X, Y0, Y1, Y2, Y3 and has 6 outputs f0..f5. Notice also the symmetry or duality between the AND/OR gates which have the X input connected into them. The basic principle being, that if X = “0” the cycle will be broken at the top AND gate and if X = “1”, the cycle would be broken in the middle OR gate. This in turn will “create” two “different” circuits depending on the value of X. In essence we have physically a combinational loop BUT we guarantee that whatever value X has, this loop will be logically broken!

Both cases are shown below.

cyclic_combinational2.png

cyclic_combinational3.png

If we factor in X into the equations we get the following dependencies for all the outputs on all the inputs.

cyclic_combinational4.png

The above example is one of the simplest of all and was just presented to show the principle. In this specific circuit you could also short Y0 and Y2, Y1 and Y3 and get a 3 input circuit where each of the inputs has the same behavior as X in the example (shown in page 12 in the PDF file of the thesis).

The thesis goes on to show how such circuits can be used with different advantages. The thesis is bears the date May 2004 – I hope that significant advances have been made in this area in the last 4 years. This idea is too beautiful to just let it accumulate dust or being discarded by the CAD industry…