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}.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s