Posts Tagged ‘challenge’


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!


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…