Archive for the ‘Puzzles’ Category

h1

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:
dual edge 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?

h1

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.

Ready, set, go!

h1

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!

h1

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…

    h1

    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.

    h1

    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!

    h1

    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.