Johnson Counter Recovery Circuits

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

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…

Real World Examples #2 – Fast Counters

This is something which will be obvious to the “old school” people, because it was used a lot in the past.

A few weeks ago a designer who was working on a very, very small block asked for my advice on the implementation of counters. The problem was that he was using a 7-bit counter, defined in RTL as cntr <= cntr +1;
The synthesis tool generated a normal binary counter, but unfortunately it could not fulfill the timing requirements – a few GHz.
(Don’t ask me why this was not done in full-custom to begin with…)

Now, the key to solving this problem was to notice that in this specific design only the terminal count was necessary. This meant that all intermediate counter states were not used anywhere else, but the circuits purpose was to determine if certain amount of clock cycles have occured.

This brings us to the question: “Under these conditions, is there a cheaper/faster counter than the usual binary counter?”
Well I wouldn’t write this post if the answer was negative… so obviously the answer is “Yes” – this is our old friend the LFSR!
LFSRs can be also used as counters, and they are being used in two very common, specific ways:

1. As a terminal counter – counter needs to measure a certain amount of clock edges. It counts to a specific value and then cycles over or resets
2. As a FIFO pointer – where the actual value itself is not of great importance but the order of increment needs to be deterministic and/or the relationship to another pointer of the same nature

Back in the age of prehistorical chip design (the 1970s), when designers really had to think hard for every gate, LFSRs were a very common building block and were often used as counters.

A slight disadvantage, is that the counting space of a full length n-bit LFSR is not 2^n but rather (2^n)-1. This sounds a bit petty on my side but believe me it can be annoying. Fear not! There is a very easy way to transform the state space to a full 2^n states. (can you find how???)

So next time you need a very fast counter, or when you need pointers for your FIFO structure – consider your good old friend the LFSR. Normally with just a single XOR gate as glue logic to your registers, you achieve (almost) the same counting capabilities given to you by the common binary counter.