## Dual Edge Binary Counters + Puzzle

June 24, 2009

I lately came across the need to use a dual edge counter, by this I mean a counter which is counting both on the rising and on the falling edge of the clock.
The limitation is that one has to use only normal single edge sensitive flops, the kind you find in each library.

There are several ways to do this, some easier than others. I would like to show you a specific design which is based on the dual edge flop I described in a previous post. This design is just used here to illustrate a point, I do not recommend you use it – there are far better ways. Please refer to the end of the post for more on that.

The figure below depicts the counter:

The counter is made of 2 n-bit arrays of flops. The one operates on the rising edge, the other on the falling edge. The “+1″ logic is calculated from the final XOR output, which is the real output of the counter! The value in each of the n-bit arrays does not represent the true counting value, but is used to calculate the final counter value. Do not make the mistake and use the value directly from either set of flops.

This leads to a small puzzle – given the conditions above, can this counter be done with less flops?

## Challenge #3 – Counting the Number of “1″s

November 13, 2008

Time for a new challenge! The last two had some great responses and solutions. If you read through the comments you’d see there were some disagreements on what is the best approach. Some claimed a hand crafted approach is the best, while others said it was more of a theoretical problem and we should use a synthesis tool to solve it.
Both have pros and cons, although for those specific challenges I personally tend to go with the hand crafted approach – you, of course, don’t have to agree with me.

For this time we got a very practical problem that pops up again and again: counting the number of “1″s in a vector.
Use the metrics given in challenge #1 and find the minimal delay circuit for a combo cloud that counts the number of “1″s in an 8-bit vector. You get 8 bits in and supply 4 output bits which give a binary representation of the amount of “1″s in the 8-bit vector.

Oh and don’t forget to mention how your method scales when counting 16-bit and 32-bit vectors.

## Challenge #2 – One Hot Detection

October 20, 2008

The last challenge was a big success with many people sending their solutions via email or just posting them as a comments.
Many of you said they were waiting for the next challenge. So, before returning to the usual set of posts about different aspects of digital design, let’s look at another one.

Imagine you have a vector of 8 bits, The vector is supposed to be one hot coded (only a single logic “1″ is allowed in the set). Your task if you choose to accept it , is to design a combo block to detect if the vector is indeed one-hot encoded.

We are again looking for the block with the shortest delay. As for the solution metrics for this challenge please refer to the previous challenge.

Also try to think how your design scales when the input vector is 16 bits wide, 32 bits wide and the general case of n bits wide.

Good luck!

## Challenge #1 – DBI Detect

October 8, 2008

It has been a while since we had a challenge question on the site (last one was the divide by 3 question), and I would like to have more of those in the future. I will basically pose a problem and ask you to solve it under certain conditions – e.g. least hardware or latency, lowest power etc.

This time the challenge is related to a real problem I encountered recently. I reached a certain solution, which I do not claim to be optimal, actually I have the feeling it can be done better – I am therefore very interested in your own way of solving the problem.

Your challenge is to design a combo-block with 8 inputs and 1 output. You receive an 8-bit vector, If the vector contains 4 ’1′s or more, the output should be high, otherwise low (This kind of calculation is commonly used for data bus inversion detection).

What is the best way to design it with respect to minimizing latency (in term of delay units), meaning the lowest logic depth possible.

Just so we could compare solutions, let’s agree on some metrics. I am aware that your own library might have different delay ratios between the different elements, but we gotta have something to work with.

• Inverter – 1 delay unit
• NOR, NAND – 2 delay units
• AND, OR – 3 delay units
• 3 or 4 input NOR, NAND – 4 delay units (2 for first stage + 2 for second stage)
• 3 or 4 input OR, AND – 6 delay units (2 for first stage + 2 for second stage)
• XOR, MUX – 7 delay units (2 AND/OR + 1 Inverter)
• Please either post a comment with a detailed solution, or send me an email.

Take it from here guys…

## Puzzle #13 – A Google Interview Question

July 25, 2008

The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment – until then I am sure the headline will generate some traffic .

The original question as it was given to me was:
Given an array with 2n+1 integer elements, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.

Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness – the rest of the 2^N – (2n+1) are all zeroes). n elements appear twice – in different places in the SRAM, while a single value appears only once.

Design a circuit with the minimum amount of hardware to find the value which appears only once.

## Puzzle #12 – Count and Add in Base -2

June 3, 2008

It has really been a long time since a new puzzle appeared on the blog.
This one is a neat little puzzle that was pretty popular as an interview question. I tried to expand on it a bit, so let’s see where this goes.

The basic idea is: can you count in base -2? There is no typo here – it is minus 2. So far the original puzzle, now my small contribution…
Once you realize how to do this, try to build a logical circuit that performs addition directly (i.e. no conversions) in base -2.

Good luck!

## Puzzle #10 – Mux Logic – Solution

May 29, 2008

Puzzle #10 – Mux Logic, still didn’t get an official solution so here goes.
If you are not familiar with the puzzle itself, as usual I ask you to follow the link and reread its description.

To solve this puzzle let’s first take a look at the combinational parts of the circuits. If we could build an OR gate and a NOT gate from MUXes it would be enough to make any combinational circuit we wish (this is because OR and NOT are a complete logic system, same as AND and NOT, or just NOR or NAND).
The figure below shows how to build NOT, OR and AND gates from a single MUX.

Next in line we have to somehow build the flipflop in the circuit. We could build a latch from a single MUX quite easily if we feedback the output to one of the MUX inputs. The figure below will make everything clearer. Notice that we could easily construct a latch which is transparent while its clock input is high or low by just changing the input the feedback wire is connected to.
We then use two latches, one transparent low the other transparent high to construct a flipflop.

As a final note, some use the versatility of the MUX structure to their advantage by spreading MUX structures as spare cells. Later if an ECO is needed one can build combinational as well as sequential elements just from those single MUX structures.

## 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.

## 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.

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.

## Puzzle #11 – Not Just Another Hats Problem

September 16, 2007

Here is another puzzle for you to ponder during the upcoming week. It would seem a bit far fetched from our usual digital design stuff, but the solution is somewhat related to the topics discussed in this blog. Moreover, it is simply a neat puzzle.

A group of 50 people are forming a column so person #1 is in front of all, followed by person #2 and so on up to person #50.
Person #50 can see all the people in front of him (#49..#1), person #49 can see only #48..#1 and so on.
The 50 people are now given hats in random. Each hat can be either black or white. The distribution of the hats is totally random (i.e. they might be all black or all white and not necessarily 25-25)

The people now take turn in guessing what color hat they are wearing – They are just allowed to say “white” or “black”, nothing more!. Person #50 starts and they continue in order down to person #1. If the person happens to guess the color of his own hat the group receives \$1000.
What is the best strategy the 50 people should agree on before the experiments starts to maximize the amount of money they should expect? And what is the sum of money they should expect to earn from this experiment?
(you can do better than pure chance, or much better than \$25,000…)

For the experts

What if the experiment is done with hats which are red, black or white? what about 4 colors? What would be the maximum color of hats that will still guarantee the amount from the original variant? and how?