## 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:

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?

## Another Look at the Dual Edge Flip Flop

September 22, 2008

After writing the solution to one of the puzzles and after contemplating about our dear friend the dual edge flip flop, I noticed something very interesting.

If you look carefully at the implementation of the flip flop which is made out of MUXes, you will see that it is very easy to make a posedge or negedge flip flop by just exchanging the MUX feedback connection.
I wondered if it would be possible to construct a dual edge flip flop with MUXes.
Turns out it is quite possible and requires only one more MUX!

I find the above circuit to be pretty neat because of its symmetry.

Anyways, I wondered if I was the first one to think of this trick; Turns out that… well NO. A short search on the web showed me that someone already invented and wrote a paper about this circuit, check it out here.

I am not aware of any library utilizing this design for a standard cell (if you have different information please comment or send me an email). What is this good for? I guess you could use this neat trick in an ECO, since a lot of times MUX structures are readily available.

## Polymorphic Circuits

July 14, 2008

Here is a neat and not so new idea that I came across last year – “Polymorphic Circuits”. The basic concept is logic gates which under specific operating conditions behave in a certain way while under different operating conditions behave in another way. For example a circuit when operated with a 2 volt supply might act as an OR gate but when supplied with 1 volt will become an AND gate, or another example might be a circuit which in room temperature behaves as an XOR gate while at 120 degrees, the very same circuit operates as a NAND gate.

This concept just screams for new application (I guess mainly in security) but I was not able to think of something specific so far. Feel free to shoot ideas around in the comments section of this post.

In the meantime more details can be found on this paper (just skip to the images at the end of the paper to get the idea), or this paper.

## 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:

May 23, 2008

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.

## Cyclic Combinational Circuits

March 7, 2008

As one of my strange hobbies, I sometimes try to search the web for interesting PHD thesis works. I came across this one a while back and thought it would be interesting to share.

We always hear how bad combinational cyclic loops are. Design Compiler even generates a reports to help us detect them. In the normal ASIC flow combinational loops are very dangerous, hard to analyze and characterize for timing. But here comes this Dissertation work by Marc Riedel and highlights a special set of cyclic combinational circuits which offer several important advantages.

I will try to explain the basic principle by going through an example, but make sure to read his PHD thesis, it is well written and easily understood.

As an example we will look at the very simple case depicted below:

Notice that it has 5 inputs: X, Y0, Y1, Y2, Y3 and has 6 outputs f0..f5. Notice also the symmetry or duality between the AND/OR gates which have the X input connected into them. The basic principle being, that if X = “0” the cycle will be broken at the top AND gate and if X = “1”, the cycle would be broken in the middle OR gate. This in turn will “create” two “different” circuits depending on the value of X. In essence we have physically a combinational loop BUT we guarantee that whatever value X has, this loop will be logically broken!

Both cases are shown below.

If we factor in X into the equations we get the following dependencies for all the outputs on all the inputs.

The above example is one of the simplest of all and was just presented to show the principle. In this specific circuit you could also short Y0 and Y2, Y1 and Y3 and get a 3 input circuit where each of the inputs has the same behavior as X in the example (shown in page 12 in the PDF file of the thesis).

The thesis goes on to show how such circuits can be used with different advantages. The thesis is bears the date May 2004 – I hope that significant advances have been made in this area in the last 4 years. This idea is too beautiful to just let it accumulate dust or being discarded by the CAD industry…

## Johnson Counter Recovery Circuits

February 25, 2008

In a previous post I discussed the Johnson counter (diagram below). It was mentioned that if a bit accidentally flips in the wrong place in the counter (due to wrong reset behavior, noise, etc.) it will rotate through the counter indefinitely.

In a robust Johnson counter there is a mechanism for self-correction of these errors. This post discussed in detail how to resolve such single bit errors with minimum hardware overhead.

Let’s assume that for some odd reason within a run of “1”s or “0”s a single bit had flipped. If we now take a snapshot of 3 consecutive bits in the counter as the bits are rotating, we will eventually discover two forbidden states: “010” and “101”. All the other six possible states for 3 consecutive bits are legal – as seen in the table below:

The basic idea, is to try to identify those rogue states and fix them by flipping the middle, erroneous bit and pushing the result to the next state. Naturally, we have to make sure that we keep the normal behavior of the circuit as well.
We will examine two solutions (a) and (b). One more efficient (hardware wise) than the other.

Let’s start with approach (a). With this approach we try to correct both forbidden state. The table bellow shows a snapshot of 3 consecutive bits in the “state” column. One is marked in red the other in orange. The column “next(a)” contains the value to be shifted into the 3rd bit – e.g. if “011” is encountered then the middle “1” will be pushed unchanged to the bit to its right, however if the state “010” will be detected, the middle “1” will be flipped to a “0” and pushed into the right thus correcting a forbidden state.

The second approach (b) corrects only the single forbidden state “010”. Then how come this solves the problem? Approach (b) relies on the fact that state “010” is the inverse state of “101”. It is enough to correct state “010” since state “101” will reach the end of the counter, then will be flipped bit by bit and will eventually appear as “010” in the next cycle through the counter!

The next diagram shows the different hardware implementation for both solutions. While I can be blamed of being petty, solution (b) is definitely cheaper.

The final, self-correcting 4-bit Johnson counter is shown below.

It is important to note that this circuit recovers from a single bit error. If we had a 7-bit Johnson counter and 2 adjacent bits would flip in a middle of a run (unlikely but still possible), we would not detect it with the above circuit. For correcting 2 adjacent flips a wider “snapshot” of 4-bits is needed, and the circuit will naturally become more complex.

It is considered good design practice to have at least a single bit self-correcting circuit, as the one above, for each Johnson counter being used.