Digital System Design using FSMs. Peter D. Minns
target="_blank" rel="nofollow" href="#ulink_ea35a674-96f9-5676-855f-86674e9570c7">Figure 1.12 State diagram for single pulse with memory FSM.
In this state diagram the sling (loop /s going to and from s0) indicates that while input s is logic 0 (/s) the FSM will remain in state s0 regardless of how many clock pulses are applied to the FSM. Only when input s goes to logic 1 will the FSM move from state s0 to s1, and then only when a clock pulse arrives. Once in state s1, the FSM will set its output P to logic 1, and on the next clock pulse the FSM will move from state s1 to s2.
The reason why the FSM will stay in state s1 for only one clock pulse is because in state s1 the transition from this state‐to‐state s2 occurs on a clock pulse only. Once the FSM arrives in state s2, it will remain there whilst input s = 1. As soon as input s goes to logic 0 (/s) the FSM will move back to state s0 on the next clock pulse.
Since the FSM remains in state s1 for only a single clock pulse, and since P = 1 only in state s1, the FSM will produce a single output pulse.
Note in the FSM state diagram that each state has a unique state identity: s0, s1, and s2.
Also note that each state has been allocated a unique combination of flip‐flop states, for example:
State s0 uses the flip‐flop combination A = 0 B = 0, e.g. both flip‐flops reset.
State s1 uses the flip‐flop combination A = 1 B = 0, e.g. flip‐flop A is set.
State s2 uses the flip‐flop combination A = 0 B = 1, e.g. flip‐flop A is reset, flip‐flop B is set.
Now move on to Frame 1.12.
Let’s continue with the one‐pulse design.
The flip‐flop outputs are seen to define each state. If we could see nothing more than the A and B outputs of the two flip‐flops, we could tell what state the FSM was in by the output logic levels on each flip‐flop.
We could also tell in which state the output P was to be logic 1, i.e. in state s1 where the flip‐ flop output logic levels are A = 1 and B = 0.
Therefore, the output P = A/B. (Remember, AB is used to indicate the logical AND operation used in Boolean algebra.)
So we now see that the flip‐flops are used to provide a unique identity for each state.
We also see that, since each state can be defined in terms of the flip‐flop output states, the outside world outputs can also be defined in terms of the flip‐flop output states since the outside worlds output states themselves are a function of these states.
L is logic 1 in states s1 and s2 and is defined in terms of the flip‐flop outputs A/B + /AB.
Therefore, L = A/B + /AB = A/B + /AB. No Boolean reduction is possible in this case.
The allocation of unique values of flip‐flop outputs to each state is rather an arbitrary process. In theory, we can use any values so long as each state has a unique combination. This means that we cannot have more than one state with the flip‐flop values of, say, A/B (i.e. both states cannot have the same value).
In practice it is common to assign flip‐flop values so that the transition between each state involves only one flip‐flop changing state. This is known as ‘following a unit distance pattern’: only one flip‐flop changes state.
The above example does not use a unit distance pattern since there are two flip‐flop changes between states s1 and s2. However, the reader will be going on to make use of the unit distance code idea.
The reader could also make the single‐pulse state diagram (Figure 1.12) follow a unit distance pattern by adding an extra state. This extra state could be inserted between states s2 and s0, having the same output for P as state s0. In the state diagram the new state would also have the value of L, the same as that in state s2, since the reader does not want L to change until s goes to 0.
Try re‐drawing the state diagram with this additional state and assign a unit distance pattern to the flip‐flops.
When you have done this, go to Frame 1.13.
A completed state diagram with unit distance patterns for flip‐flops is shown in Figure 1.13.
Figure 1.13 State diagram for single‐pulse generator with memory and dummy state.
Note that the added state has the unique name of s3 and the unique flip‐flop assignment of A = 0 and B = 1.
Also note that s2 uses the A and B values of A = 1 and B = 1. This provides the required unit distance coding. It also has the output P = 0, as it would in state s0 (the state it is going to go to when s = 0).
In this design the addition of the extra state has not added any more flip‐flops to the design since two flip‐flops can have a maximum of 22 = 4 states (remember Frames 1.2 and 1.3).
The addition of this extra state is usually called a dummy state.
Look carefully at the state diagram in Frame 1.13 and satisfy yourself that the state diagram is doing the same thing as the one in Frame 1.11. If you cannot see this, consider reading Frames 1.11–1.13 again.
Now let us add an additional input called r to our state diagram.
Input r is to be added so that if r = 1 the FSM will continue to pulse output P (on and off) until r is made 0. At this point the FSM will return to state s0 but only if input s = 0.
Draw the block diagram for the FSM.
Draw the state diagram for this modified FSM.
Take your time and think about what you are doing.
Turn to Frame