Puzzle #10 – Mux Logic – Solution

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.

Low Power Methodology Manual

I recently got an email from Synopsys. It was telling me I can download a personalized copy of a “Low Power Methodology Manual”. Now, to tell you the truth, I sometimes get overly suspicious of those emails (not necessarily from Synopsys) and I didn’t really expect to find real value in the manual – boy, was I wrong, big time!

Here you get a very nice book (as pdf file), which has extremely practical advice. It does not just spend ink on vague concepts – you get excellent explanations with examples. And mind you, this is all for free.

Just rush to their site and download this excellent reference book that should be on the table of each digital designer.

The Synopsys link here.

The hard copy version can be bought here or here.

Replace Your Ripple Counters

I was recently talking to some friends, and they mentioned some problems they encountered after tape out. Turns out that, the suspicious part of the design was done full custom and the designers thought it would be best to save some power and area and use asynchronous ripple counters like the one pictured below. The problem was that those counters were later fed into a semi-custom block – the rest is history.

Asynchronous ripple counters are nice and great but you really have to be careful with them. They are asynchronous because not all bits change at the same time. For the MSB to change the signal has to ripple through all the bits to its right, changing them first. The nice thing about them is that they are cheap in area and power. This is why they are so attractive in fast designs, but this is also why they are very dangerous because the ripple time through the counter can approach the order of magnitude of the clock period. This means that a digital circuit that depends on the asynchronous ripple counter as an input might violate the setup-hold window of the capturing flop behind it. To sum up, just because it is coming from a flop doesn’t mean it has to be synchronous.

If you can, even if you are a full custom designer, I strongly recommend replacing your ripple counters with the following almost identical circuit.

It is based on T-flops (toggle flip flops are just normal flops with an XOR of the current state and the input, which is also called the toggle signal) and from the principle of operation is almost the same, although here instead of generating the clock edge for the next stage, we generate a toggle signal when all previous (LSB) are “1”. Notice that the counter is synchronous since the clock signal (marked red) arrives simultaneously to all flops.

Latch Based Design Robustness

Latch based design is usually not given enough attention by digital designers. There are many reasons for that, some are very well based, other reasons are just because latch based design is just unknown and looked at as a strange beast.

I intend to have a serious of posts concerning latch based design issues. I have to admit that most of my design experience was gained doing flip flop based designs, but the latch based designs I did were always interesting and challenging. If any of you readers have some interesting latch based design examples please send them over to my email and I will include them in later posts.

Just to start the ball rolling, here is a very interesting paper on the robustness of latch based design with comparison to flip flop based design. If you don’t have the time to go through the entire paper just look at figure 1 and its description.

I also added this paper to the list of recommended reading list.

Happy Birthday!

Wow, time goes by so fast. I just noticed that this blog celebrates its first birthday! Exactly one year ago it went “on the air”.
If you liked the posts, found them helpful or just have some nice things to say – just comment on this post.

Thanks,

Nir

Ring Buffers

On the last technical post I discussed the problem of transferring information serially between two different clock domains with similar frequency but with drifting phase.
This post will try to explain how this issue is being solved.

When approaching this problem, we have to remember that the phase might drift over time and we have to quantify this drift before the design starts. Modeling the channel beforehand is very helpful here.
Once we know the needed margin, we can approach the design of the ring buffer.

The ring buffer is a FIFO with both ends “tied together” as depicted below. Pointers designate the read and write position and are moved with each respected clock signal in the direction of the arrow (in the figure below – clockwise). Remember, the read and write pointers move at different times but the overall rate of change of both is similar. This means that in some moment one can move ahead of the other, and in another it can lag behind, but over time the the amount of clock edges is the same.

The tolerance of the ring buffer is represented below with the dashed arrows. The read and write clocks can drift in time up to a point just before they meet and cross each other.

The series of images below depicts how the read and write pointers move with time and how the buffer is filled with new information (green) and how it is read (red). Notice how the first two reads will generate garbage because it reads out information that was not written into the buffer.

One of the most complicated issues is the start-up of the ring buffer, because both clock domains are unrelated. A certain “start” signal has to be generated and “tell” both pointers to start to advance. If this is not done carefully enough, one pointer will start to advance ahead of time and thus “bite away” some of the margin we designed for. This problem is even more complicated, when a lot of channels with different ring buffers are operated in parallel.

In one of the next posts we will explore a simple technique that enables us to determine if the ring buffer failed and the information read is actually one which is not updated.

Long Break…

Due to a long and severe sickness I was unable to update the blog for such a long time.
I promise to catch up soon, with more interesting posts – hold on…