Back from vacation…
I really wanted to devote a set of posts on scan and its importance for us digital designers. I planned, wrote up a list of topics and problems I wanted to highlight, reworked everything and then searched the web…
Dang! Somebody already did it better and clearer than I could have ever done that!
All I can do is recommend on reading and re-reading those two articles – It will pay off. Links follow…
Here is another puzzle for you to ponder during the upcoming week. It would seem a bit far fetched from our usual digital design stuff, but the solution is somewhat related to the topics discussed in this blog. Moreover, it is simply a neat puzzle.
A group of 50 people are forming a column so person #1 is in front of all, followed by person #2 and so on up to person #50.
Person #50 can see all the people in front of him (#49..#1), person #49 can see only #48..#1 and so on.
The 50 people are now given hats in random. Each hat can be either black or white. The distribution of the hats is totally random (i.e. they might be all black or all white and not necessarily 25-25)
The people now take turn in guessing what color hat they are wearing – They are just allowed to say “white” or “black”, nothing more!. Person #50 starts and they continue in order down to person #1. If the person happens to guess the color of his own hat the group receives $1000.
What is the best strategy the 50 people should agree on before the experiments starts to maximize the amount of money they should expect? And what is the sum of money they should expect to earn from this experiment?
(you can do better than pure chance, or much better than $25,000…)
For the experts
What if the experiment is done with hats which are red, black or white? what about 4 colors? What would be the maximum color of hats that will still guarantee the amount from the original variant? and how?
Your company is pretty tight on budget this year and it happens to have only Muxes to design with.
You are required to design a circuit equivalent to the one below, using only Mux structures.
I will be on vacation for a week and half (up to september 25th) and will have relatively limited access to the web. Therefore, I will leave you with a series of puzzles just for fun. I will try to make at least one of them hard enough…
It’s been a while since I posted a nice puzzle and since I know they are so popular, here is a relatively simple one. It was used in job interviews btw (the last line will boost the amount of views for this post…)
A snail leaves his warm house and takes a crawl through the forest leaving behind him on the ground a trail of “0”s and “1”s. He takes a very complicated route crossing his path several times. At one point he becomes tired and disoriented and wishes to go back home. He sees his own path of “0”s and “1”s on the ground which he is about to cross (i.e. not the trail ending in his tail) and wonders whether to follow the trail towards the left or towards the right.
What is the shortest repeating code of “0”s and “1”s he should leave as he crawls in order to easily and deterministically track the way back home? What is the minimum amount of bits he needs to observe (or the sample length of the code)?
So, why do we really care about state machine partitioning? Why can’t I have my big fatty FSM with 147 states if I want to?
Well, smaller state machines are:
There is no rule of thumb stating the correct size of an FSM. Moreover, a lot of times it just doesn’t make sense to split the FSM – So when can we do it? or when should we do it? Part of the answer lies in a deeper analysis of the FSM itself, its transitions and most important, the probability of occupying specific states.
Look at the diagram below. After some (hypothetical) analysis we recognize that in certain modes of operation, we spend either a lot of time among the states marked in red or among the states marked in blue. Transitions between the red and blue areas are possible but are less frequent.
The trick now, is to look at the entire red zone as one state for a new “blue” FSM, and vice versa for the a new “red” FSM. We basically split the original FSM into two completely separate FSMs and add to each of the FSM a new state, which we will call a “wait state”. The diagram below depicts our new construction.
Notice how for the “red” FSM transitioning in and out of the new “wait state” is exactly equivalent (same conditions) to switching in and out of the red zone of the original FSM. Same goes for the blue FSM but the conditions for going in and out of the “wait state” are naturally reversed.
OK, so far so good, but what is this good for? For starters, it would probably be easier now to choose state encodings for each separate FSM that will reduce switching (check out this post on that subject). However, the sweetest thing is that when we are in the “red wait state” we could gate the clock for the rest of the red FSM and all its dependent logic! This is a significant bonus, since although previously such strategy would have been possible, it would just be by far more complicated to implement. The price we pay is additional states which will sometimes lead to more flip-flops needed to hold the current state.
As mentioned before, it is not wise to just blindly partition your FSMs arbitrarily. It is important to try to look for patterns and recognize “regions of operation”. Then, try to find transitions in and out of this regions which are relatively simple (ideally one condition to go in and one to go out). This means that sometimes it pays to include in a “region” one more state, just to make the transitioning in and out of the “region” simpler.
Use this technique. It will make your FSMs easy to debug, simple to code and hopefully will enable you to introduce low power concepts more easily in your design.
I promised before to write some words on reducing switching activity by cleverly assigning the states of an FSM, so here goes…
Look at the example below. The FSM has five states “A”-“E”. Most naturally, one would just sequentially enumerate them (or use some enumeration scheme given by VHDL or Veriog – which is easier for debugging purposes).
In the diagram the sequential enumeration is marked in red. Now, consider only the topology of the FSM – i.e. without any reference to the probability of state transitions. You will notice that the diagram states (pun intended) in red near each arc the amount of bits switching for this specific transition. For example, to go from state “E” (100) to state “B” (001), two bits will toggle.
But could we choose a better enumeration scheme that will reduce the amount of switching? Turns out that yes (don’t tell anybody but I forced this example to have a better enumeration 🙂 ). If you look at the green state enumeration you will clearly see that at most only one bit toggles for every transition.
If you sum up all transitions (assuming equal probability) you would see that the green implementation toggles exactly half the time as the red. An interesting point is that we need only to consider states “B” – “E”, because once state “A” is exited it can never be returned to (this is sometimes being referred to as “black hole” or “a pit”).
The fact that we chose the states enumeration more cleverly doesn’t only mean that we reduced switching in the actual flip-flops that hold the state itself, but we also reduce glitches/hazards in all the combinational logic that is dependent on the FSM! The latter point is extremely important since those combinational clouds can be huge in comparison to the n flops that hold the state of the FSM.
The procedure on choosing the right enumeration deserve more words but this will become a too lengthy post. In the usually small FSMs that the average designer handles on a daily basis, the most efficient enumeration can be easily reached by trial and error. I am sure there is somewhere some sort of clever algorithm that given an FSM topology can spit out the best enumeration. If you are aware of something like that, please send me an email.
Last week this blog crossed the 10,000 views mark in about 3+ months or so of being “on the air”. That number represents total views not counting my own visits to the blog (if it would include that, the number would for sure triple)
Just wanted to say thanks to everybody who is reading, sending emails, suggesting and even complaining (though there are not many of those).
Please don’t be ashamed and continue sending emails. First, it is fun to get them and second, it helps me improve and write about what is really interesting for you guys.
You are currently browsing the Adventures in ASIC Digital Design blog archives for September, 2007.
Adventures in ASIC Digital Design 