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.

De Bruijn and Maximum Length LFSR Sequences

February 15, 2008

In the previous post I mentioned that a maximum length LFSR can be modified quite easily to generate the “all zero” state. The resulting sequence is then called a De Bruijn code. It has many uses in our business but also in remote areas like card tricks!!

The normal maximum length LFSR circuit cannot generate the “all zero” state or the trivial state, because it will get stuck in this state forever. The picture below shows as an example a 4-bit maximum length LFSR circuit.

The trick is to try to insert the “all zero” state in between the “00..01″ and the “10..00″ states. Normally after the “00..01″ state the next value to be pushed in from the left would be a “1″, so the state “10..00″ could be generated. If we would like to squeeze the “00..00″ state next, we need to flip this to “0″. Then we have to make sure that for the next cycle a “1″ will be pushed. This is done by detecting when the entire set of registers – less the rightmost one – are all zero, and using this as another input in the XOR feedback path. The result is a 2^n counting space sequence which is called a De Bruijn sequence. The figure of the completed De Bruijn counter is shown below.

Since it is a bit hard to follow the words, you can convince yourself by following the sequence – the table below will be of some help.

If you plot a single bit of the De Bruijn counter over time (doesn’t matter which bit) you will see something similar to the next figure. Notice how over time, observing 4 consecutive bits in the sequence not only gives a unique result (until it wraps around) but also gives all possible 4-bit combinations! A simple LFSR will only fulfill the first criteria.

If you like LFSRs and want to investigate a bit more, there is an excellent (albeit quite “heavy to digest”) book from Solomon Golomb called shift register sequences. The book is from the 1960s!! who said all good things in our industry are new…

Null Convention Logic

October 11, 2007

It is extremely rare in our industry that totally new approaches for Logic circuit design are taken. I don’t know the exact reasons and I really don’t want to get into the “fight” between tool vendors and engineers.

Null Convention Logic, is a totally different approach to circuit design. It is asynchronous in its heart (I guess half of the readers of this post just dropped now).
It is not new and being currently pushed by its developers in Theseus Research.

They published a book, which I really recommend reading. It is not very practical with the current mainstream tools and flows but it is a very interesting reading that will open your eyes to new approaches in logic design.
You can get a good introduction to the book’s content by reading this paper. It is fairly technical and would need a few good hours to digest and grasp the meaning behind, especially given the fact that it is so much different than what we are used to – forget about AND, OR and NOT gates…

Pre-scaled Counters

October 8, 2007

It is obvious that as a normal binary counter increases in width its maximum operation frequency drops. The critical path going through the carry chain up to the last half-adder element is purely combinational and increases with size. But what if our target frequency is fixed (as is usually the case) and we need to build a very wide counter? Here come to the rescue a variant of the normal binary counter – the pre-scaled counter.

Pre-scaled counters are based on the observation (or fact) that in the binary counting sequence, the LSB will toggle in the highest frequency (half that of the clock when working with the rising edge only). The next bit in line will toggle in half that frequency, the next with half of the previous and so on.
In general, the n-th bit will toggle with frequency 2^(n+1) lower than the clock (we assume that bit 0 is the LSB here). A short look at the figure below will convince you.

We can use this to our advantage by “partitioning” the counter we wish to build. In essence we make the target clock frequency of operation independent of the counter size! This means that given that our clock frequency enables us to have a single flop toggling plus minimal levels of logic, one could in theory build am extremely wide counter.

If you really insist, the above statement is not 100% correct (for reasons of clock distribution and skew, carry collect logic of a high number of partition stages, etc.) , but for all practical reasons it is true and useful. Just don’t try to build a counter with googolplex bits.

The basic technique for a 2-partition is shown below. We have an LSB counter which operates at clock frequency. Its width is set so it could still operate with the desired clock frequency. Once this counter rolls over an enable signal is generated for the MSB counter to make a single increment. Notice how we also keep the entire MSB counter clock gated since we know it cannot change its state.

The distance between the filtered clock edges (marked as “X”) of the MSB counter is determined by the width of the LSB counter. This should be constrained as a multi-cycle path with period X when doing synthesis.

The technique could be extended to a higher amount of “partitions” but then we must remember that the enable for each higher order counter is derived from all enable signals of all previous stages.

An interesting variant is trying to generate and up/down counter which is width independent. It is not so complicated and if you have an idea on how to implement it, just comment.