Puzzle #2

OK, here is another nice puzzle, which actually has applications in real life!
This one was given to me on the same IBM interview sometime around 10 years ago.

Here goes.

Again we are dealing with the poor engineers in the land of Logicia. For some sort of fancy circuitry, a 7-bit binary input is received. As a result it should give the amount of “1″s present in this vector. For example, for the inputs 1100110 and 1001110 the result should be the same and equal to 100 (4 in binary). This time however, the only components they have on their hands are Full Adders. Describe the circuit with minimum amount of parts.

This puzzle is fairly easy, and as I mentioned before has found some practical uses in some of my designs. More on this when I’ll give the answer.

Puzzle #1

Since I am a big fan of puzzles, I will try to post here from time to time a few digital design related puzzles.

This particular one was given to me in an interview at IBM over 10 years ago.

Due to the war in the land of Logicia there is a shortage of XOR gates. Unfortunately, the only logic gates available are two weird components called “X” and “Y”. The truth table of both components is presented below - Z represents a High-Z value on the output.
Could you help the poor engineers of Logicia to build an XOR gate?

Another Synchronization Pitfall…

Many are the headaches of a designer doing multi clock domain designs. The basics that everyone should know when doing multi clock domain designs are presented in this paper. I would like to discuss on this post a lesser known problem, which is overlooked by most designers. Just as a small anecdote, this problem was encountered by a design team led by a friend of mine. The team was offered a 2 day vacation reward for anyone tracking and solving the weird failures that they experienced. I guess this already is a good reason to continue reading…

OK, we all know that when sending a control signal (better be a single one! - see the paper referenced above) from one clock domain to another, we must synchronize it at the other end by using a two stage shift register (some libraries even have a “sync cell” especially for this purpose).

Take a look at the hypothetical example below

Apparently all is well, the control signal, which is an output of some combinational logic, is being synchronized at the other end.
So what is wrong?
In some cases the combinational logic might generate a hazard, depending on the inputs. Regardless whether it is a static one (as depicted in the timing diagram) or a dynamic one, it is possible that exactly that point is being sampled at the other end. Take a close look at the timing diagram, the glitch was recognized as a “0″ on clk_b’s side although it was not intended to be.

The solution to this problem is relatively easy and involves adding another sampling stage clocked with the sending clock as depicted below. Notice how this time the control signal at the other end was not recognized as a “0″. This is because the glitch had enough time to settle until the next rising edge of clk_a.

In general, the control signal sent between the two clock domains should present a strict behavior during switching- either 1–>0 or a 0–>1. Static hazards (1–>0–>1 or 0–>1–>0) or Dynamic hazards (1–>0–>1–>0 or 0–>1–>0–>1) are a cause for a problem.

Just a few more lines on synchronization faults. Quite often they might pop up in only some of the designs. You might have 2 identical chips, one will show a problem the other not. This can be due to slight process variations that make some logic faster or slower, and in turn generate a hazard exactly at the wrong moment.

Eliminating Unnecessary MUX structures

You will often hear engineers in our business saying something along these lines:
“I first code, and then let synthesis find the optimal implementation” or “synthesis tools are so good these days, there is no use in spending time on thinking in the circuit level…”. Well not me - sorry!! I am a true fan of “helping” or “directing” the synthesis.
The example I will discuss on this post, is a real life example that occurred while reviewing a fellow engineer’s work.

The block in discussion is quite a heavy one, with very tight timing requirements and complicated functionality (aren’t they all like that…). Somewhere in the code I encountered this if-else-if statement (Verilog):

if (s1)
   y = 1'b1;
else if (s2)
         y = 1'b0;
      else
         y = x;

Now, if this would have stood on its own, it would not have risen much suspicion. But this statement happened to be part of the critical path. On first look, the if-else-if ladder is translated into a set of cascaded muxes, but looking carefully at it, one can simplify it into two gates (or even one complex gate in most libraries) as shown below.

I do not say that a good synthesis tool is not able to simplify this construction, and I have to admit I do not really know what is going on inside the optimization process - this seems to be some sort of black magic of our art - but fact is, that timing improved after describing the if-else-if statement explicitly as an or-and combination.
The reason can be, as depicted, that the muxes are being “dragged” somehow into the logic clouds just before and after them in hope of simplifying them there. I just don’t know!
A good sign to spot when such simplification is easily possible, is when you have an if-else-if ladder or a case statement with constants on the right hand side (RHS). It does make the code a bit less readable, but IMHO it is worth it.

Here is a short summery of some common mux constructs with fixed inputs and their simplified forms.

A Short Note on Drawings Conventions

Counting in Gray - Part III - Putting Everything Together

In the last post we built the basis for our Gray counter implementation. In this post we will combine all observations and create a “Gray bit cell” which could be instantiated as many times as one wishes to create Gray counters which count up or down and are of any desired length.

As mentioned before, the basic idea is to build a “Gray bit cell”. Naturally it has a single bit output, but the cell also has to get the information from all previous cells whether or not a pattern was identified and whether it has to toggle or not.

The latter point reminds us that we will have to use T-Flops for the implementation, since the patterns we observed in the previous post only concern when a certain Gray bit toggles and not its absolute value. The most basic implementation of a T-Flop is presented on the figure on the right.

The abstract view of the Gray cell is presented to the left. Both the clock and reset inputs have been omitted. The cell inputs and outputs are:

Q_o - Gray value of the specific bit (n)

Q_i - The previous - n-1 - Gray bit value

Z_i - All Gray bits n-2 down to 0 are “0″

Z_o - All Gray bits n-1 down to 0 are “0″

parity - Parity bit - or more correctly inverted parity

up_n_dn - If “1″ count up, if “0″ count down

enable - enable counting

Two implementations of the Gray cell are depicted below, the left one being more intuitive than the right, but the right one is more compact. Both implementations are logically identical.

All that is left now is to see how to connect the Gray cells in series to produce a Gray up/down counter.
In the final picture the Gray cells were connected to form a Gray counter. Notice that some cells are connected in a special way:

Cell 0 - Q_i and Z_i are both connected to “1″, The parity input is inverted and Z_o left unconnected

Cell 1 - Z_i connected to “1″

Cell n (MSB) - Q_i is connected to “1″, Z_o left unconnected

A few more words on the parity bit. In the given implementation it is generated by a normal D-Flop with its Qbar output connected to its D input. The same functionality can be achieved without this extra D-Flop, by using an Xor tree on the outputs of the Gray counter - remember our first observation from the previous post? the parity changes with each count.

That concludes this series of posts on Gray counters, but don’t worry I promise there will be more interesting stuff coming on Gray codes.

Counting in Gray - Part II - Observations

In the last post we discussed the different approaches, their advantages and disadvantages in terms of implementation, design requirements etc. We finished with the promise to have a solution for counting in Gray code, with registered outputs and which is could easily be described in HDL.

In this post we will observe some interesting facts concerning mirrored Gray codes, which in turn will lead us to our implementation.

Let’s start.

One of the most important and basic things we can see when observing Gray codes, is that with each increment or decrement the parity of the entire number changes. This is pretty obvious since each time only a single bit changes.

The Next observation is the “toggling period” of each of the bits in Gray representation. Bit 0, or the LSB has a “toggle period” of 2 - i.e. it flips each 2 counts. Bit 1 (one to the left of the LSB) has a “toggle period” of 4. In General with each move towards the MSB side, the toggle period doubles. An Exception is the MSB which has the same toggle period has the bit to its immediate right.
The top figure on the right demonstrates this property for a 5 bit Gray code.

The reason why this is true can be easily understood if we consider the way mirrored Gray codes are being constructed (which I assume is well known). Notice that this fact just tells us only the toggle period of each bit, not when it should toggle! To find this out, we will need our third observation.

Let us now look at when each bit flips with respect to its position. In order to help us, we will have to recall our first observation - parity changes with each count. The bottom figure on the right reveals the hidden patterns.

In General: Gray bit n will toggle in the next cycle, when the bit to its immediate right is “1″ and all the other bits to its right are 0 - or in other words a 100…00 pattern
The only exception is the MSB which toggles when all the bits to its right except the one to its immediate right are “0″ - or a X00…00 pattern

sounds complicated? look in the picture again, the pattern will just pop out to you.

You can take my word for it or check for yourself, anyways the rules for counting backwards (or down), in Gray, are:

The LSB toggles when the parity bit is “0″
For all the other bits: Gray bit n will toggle in the next cycle, when the bit to its immediate right is “1″, all the other bits to its right are 0 and the parity bit is “1″ - or in other words a 100…01 pattern

On the next post we will see how to use those observations to create a simple “gray bit cell”, which will be used as our building block for the final goal - the up/down Gray counter.

Counting in Gray - Part I - The Problem

I love Gray codes, there I said it. I love to try to find different and weird applications for them.
But Gray codes are one of those things where most designers heard of and know the principle they use - but when coming to implement a circuit based on Gray codes, especially when simple arithmetic is involved, things get complicated for them.

I don’t really blame them since that stuff can get relatively tricky. Maybe it is best to show with an example…
This paper is a must read for any digital designer trying to design an asynchronous FIFO. All the major issues, corner cases and pitfalls are mentioned there, and I just can’t recommend it enough.

But… what caught my attention was the implementation of the Gray counters in the design (page 2, section 2.0). Before we get into what was written, maybe a presentation of the problem is in place. Counting (i.e. only +1 or -1 operations on a vector is considered) in binary is relatively straight forward. We all learned to do this, and use it. The problem is how do you count in “Gray code” - i.e. given the 3-bit gray code number 111, what is the next number in line? (answer: 101)

The figure below shows the Gray code counting scheme for 3-bit “mirrored” Gray code (the most commonly used)

Look at any line, can you figure out what will be the next line based only on the line you look at??? If you think you know try figuring out what comes after 11011000010 ???

There are 2 very common approaches to solve this problem:

1. Convert to binary –> do a “+1″ –> convert back to Gray
2. Use a Look-up-Table to decode the next state

Both have severe disadvantages.

Let’s look through them one at a time.
Option 1, can be implemented in principle in two different ways (the plot thickens…)

The implementation on the left has the big advantage that the Gray output is registered, i.e. the values stored in the Flip-Flop are truly Gray. This is necessary when the output is used in an asynchronous interface (e.g. as a FIFO pointer).
The implementation on the right is faster though, with the disadvantage of the output being combinational.
The advantage of both implementations is that they are relatively compact to describe in HDL, even for wide counters and very flexible - e.g. one can add a “-1″ functionality quite easily.

Option 2, is basically a big LUT that describes the next Gray state of the counter.
The outputs will be truly registered, the implementation relatively fast, but very tedious to describe in HDL and prone to errors. just imagine a 7-bit Gray counter implemented as a big case statement with 128 lines. Now imagine that you would want to add a backward counting (or “-1″) operation.

The natural question asked is, isn’t there a better implementation that gives us the best of both worlds? Registered outputs, fast and easily described in HDL. The answer is a big “YES”, and I will show how to do it on my next post. That implementation will be even easy enough for entering it in schematic tools and using it in a full-custom environment!

hold on…

First Post…

Hi, I really suck in writing so I will get straight to the point.
This weblog will mainly be of interest to fellow Electrical Engineers with emphasis on the different aspects of Digital Design.
I will try to contribute from my experience and understanding and try to present some tips, tricks and just plain cool ideas from my field. Some things will be relatively basic, other more advanced.
In general, I intend to update the site once a week or so, since most stuff will be technical it would be quite hard to come up with something new each day - that, plus the fact that I am lazy…

Hopefully in time a small database of goodies will be accumulated.
I will certainly make mistakes and sometimes even post complete nonsense, so I hope you guys will correct me and be understanding.

Nir

p.s. I also admit the name “Adventures in ASIC Digital Design” is pretty lame but I just couldn’t come up with something better.