Reduced dependency – also graphically!

Ok, so let’s look at the RD-algorithm for graphs. Take the minimized graph we obtained in previous post. The first step is to make an assumption, i.e. that two states belong to the same block. We assume that $\overline{s_0,s_2}$ is one block:

We see that we leave the area (or block) marked by a dashed line on input 1 and stay inside the block on input 0. What does this tell us? Well, simply that this block is fine as it is – we have divided the graph into two blocks – areas if you will (the dashed area and the complement, i.e. everything outside it) and we change block one the same input – regardless of where in area we are.

Again, we could make the assumption that $\overline{s_1,s_3}$ , which gives an identical result:

Everything does not all the time fall into our hands that easily. We cannot distinguish between all states yet. Since the areas each contain two elements we need some more information. Assume that we wish to specify a certain state, say $s_0$ . Looking at the first graph, we could say: it’s in the area marked by a dashed line. What then? We need another block that does not contain $s_0$ and $s_2$ (in order to specify all states, $s_1$ and $s_3$ cannot be in the same block either).

Let’s try $\overline{s_0,s_1}$ :

Since we per definition must stay in or change the block for all elements in the dashed area, we must include $s_2$ . Why? If we are in $s_0$ and get input 1, we stay. If we are in $s_0$ and get input 1, we leave the block to $s_2$ . But if we include $s_2$ , we stay in the block.

Now looking at input 0: if we are in $s_2$ we leave the block, if we are in $s_0$ or $s_1$ , we stay. Since the assumption was $\overline{s_0,s_1}$ , we must stay. So we need to include $s_3$ in order to stay on input 0. We get the graph:

If we try all possible assumptions (excluding $\overline{s_0,s_1}$ and $\overline{s_2,s_3}$ , we will notice that they will end up with a block covering the whole graph. There is nothing to do about this. Crap… what to do now? Well, we can still use the case that works.

Lets define the states in binary as $s_0 \rightarrow 00$ and $s_2 \rightarrow 01$ AND $s_1 \rightarrow 10$ and $s_3 \rightarrow 11$ . Then the first bit of the next state $q_0^+$ will be a very simple function of the first bit of the current state $q_0$ :

$q_0^+ = q_o' \oplus i$

It does not change the fact that the second state bit equation remains complex – but still – we have at least reduced the complexity of first equation. One small step towards a simpler, less costly circuit!

NOTE: There is also a state assignment method called 1-hot. This method maps $s_0 \rightarrow 00001$ , $s_1 \rightarrow 00010$ , and so on… the obvious disadvantage is that the number of required state variables grows linearly with the number of states. The main advantage is that it is really easy to construct such a map and that it always is possible to construct a mapping such that exactly two state variables change each time we jump no another state, no matter what the graph looks like. What implication does it have on the state variable update equations? Hint: the equations have the form $q_j^+ = i \land q_{l_1} \lor \cdots \lor i \land q_{l_m} = i q_{l_1} \oplus \cdots \oplus iq_{l_m}$ .