Why Not Just Over-Constrain My Design?

June 25, 2008

This is a question often raised by beginners when trying to squeeze performance from their designs.
So, why over-constraining a design does not necessarily improve performance. The truth is that I don’t really know. I assume it is connected to some internal variables and measuring algorithms inside the synthesis tool and the fact that they give up trying to improve the performance because they reached a certain local minimum in some n-variable space (really!).

But empirically, I (and many others) have found out that you can not get the best performance by just over-constraining your design in an unrealistic manner. It has to be somehow closely related to the actual maximum speed that can be reached. The graph below sums up this problem pretty neatly.

As seen above, there is a certain min-max range for the performance frequency that can be reached and its peak is not the result of the highest frequency constrained!
The flat region on the left of the figure is the speed reached without any optimization, that is, right after mapping your HDL into gates. As we move towards the right, we see actual speed improvement as we constrain for higher speeds. Then a peak is reached and constraining for higher speeds results in poorer performance.

I worked relatively less with FPGAs in my carrier but I have seen this phenomenon there as well. Take it to your attention.

Edge Triggered SR Latch

June 18, 2008

I never really used an edge triggered SR latch in any of my circuits before, but I dug this from my bag of circuit goodies and it is just too nice not to share (does it show that I am designing circuits for too long?)

The basic idea is to use two regular run-of-the-mill flip flops and combine them to a single “SR latch like” construction which is edge triggered.
The circuit is displayed below, and I just can’t help it – admiring a circuit with some sort of cross coupling…

And a corresponding timing diagram:

Non-Power-of-2 Gray Counter Design

June 9, 2008

So… you want to design a counter with a cycle which is different than a power of 2. You would like to use a Gray counter because of its advantages and just because it is simply beautiful, but alas, your cycle length is not a power of two – what to do?
This post will try to give you a sort of recipe of how to design such a non-power-of-2 Gray counter and the reasoning behind.

First, if your cycle length is an odd number, you are in trouble since this is just not possible to construct a counter with the Gray properties and with an odd cycle length. A simple way to see why it is so, is to notice that a Gray counter changes its parity with each count because only one bit changes at a time.
This naturally means that the parity toggles, but since we have an odd number of states and if we started with even parity – the last state will also have odd parity, and when we wrap around the parity won’t change! Assuming that the first and last states are different, this means that 2 bits must change at a time, thus contradicting the Gray hypothesis.

OK, so we limited ourselves to an even amount of states, is it possible now? It is! We could ask our friend Google and come up with some info and even some patents, but the best discussion on the subject that I found was written by Clive Maxfield here.

When approaching this problem, what (hopefully) should immediately struck us, is that we have to somehow use the reflection property of the Gray code (This method among others is discussed by Clive as well). Let’s take a deeper look at the 4-bit Gray code below.

The pairs of states which have identical distance from the axis of reflection are only different by their MSB. This in turn, means that we could eliminate pairs-at-a-time around the axis of reflection, and arrive to our desired number of states for the counter. Moreover, we notice that the (n-1) LSBs count up to a certain value then change direction and count down again. This property remains true even if we remove any amount of pairs around the axis of reflection.

What we have to do now, is to find this “switching value”, when we reach it on the up-count, toggle the direction bit – which is also our MSB, and block the (n-1) LSBs Gray counter for this direction switch cycle (otherwise 2 bits would change). We now count down to the initial state (all zeros). When we reach it, we again have to switch direction and block the counter and so on ad infinitum.

We can use the modular up/down Gray counter I described here, here and here. for our (n-1) LSBs. We have to find a priori the “switching value”, which is the (n-1) bit Gray value of our number of counter states divided by 2. For Example, if you want a 10 state Gray counter then: 10/2 = 5, therefore we need the 5th Gray value of a normal 3 bit Gray code, which turns out to be 110
The rest of the circuit is depicted in the figure below:

It is important to see that we use the minimal possible memory elements required for the Gray counter (i.e. no extra states to remember or pipeline) and that during “direction switching” we gate the clock for the (n-1) LSBs up/down Gray counter using an ordinary clock gate construct.
If we look carefully we see that the “direction switching” logic is basically a mux structure with the select being the direction bit.

A timing diagram of the above circuit for a 10 state Gray counter is also depicted below for clarity.

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!