State Reduction

A state diagram show the sequence of current and next states through which the state machine sequences. Figure 32.4. The transition from a current state to the next state is determined by current state and the inputs. The outputs of the state machine may also change during the transition from the current state to the next state. The outputs may depend only on the current state (Moore Machine) or a combination of current state and the inputs (Mealy Machine). It is possible that two or more states are equivalent. Two states are considered equivalent if for the same set of inputs the states change to the same next state or equivalent next states and give identical outputs. If equivalent states exist then one of the equivalent state is removed. Reduction in the number of state results in fewer flip-flops and a simpler circuit.

digital logic design  State Reduction

digital logic design  State Reduction

Reduction in the number of states is possible if one is interested only in the input and output relationship, that is, input and outputs remain unchanged. When external outputs are taken directly from flip-flops, the output must be independent of the number of states before state reduction algorithms are applied. Consider the sequence a, b, c, f, d, d, e, g, e, g, d, e, a, f, d, e, a starting from the initial state a. The inputs and the corresponding outputs are shown in the table. Table 32.8

state a b c f d d e g d e a f d e a
Input 1 1 1 0 1 0 1 0 0 0 0 0 0 0
Output 0 1 1 0 0 1 1 0 1 0 0 0 1 0

Table 32.8 The input and output sequence

In the next state table the state ‘f’ is equivalent to state ‘g’ as for each set of inputs states ‘f’ and ‘g’ change to states ‘d’ and ‘e’ respectively. Table 32.9a. Similarly, the outputs also remain identical. Therefore state ‘g’ can be eliminated and in the state table all instances of state ‘g’ are replaced by state ‘f’.

Present State Next State Output
X=0 X=1 X=0 X=1
a f b 0 0
b b c 1 1
c a f 0 1
d e d 1 0
e a g 0 1
f d e 0 0
g d e 0 0

Table 32.9a Next-State table

Present State Next State Output
X=0 X=1 X=0 X=1
a f b 0 0
b b c 1 1
c a f 0 1
d e d 1 0
e a f 0 1
f d e 0 0

Table 32.9b Next State table, with state ‘g’ eliminated and instances of state ‘g’ replaced by state ‘f’

In the next state table state ‘c’ is equivalent to state ‘e’ as for each input, the current state changes to the same next states. Table 32.9b. The outputs are also identical when changing from the present state to the next state. The state table is simplified by eliminating state e and replacing all instances of state ‘e’ with state ‘c’. table 32.9c. The State diagram represented by the simplified state table is shown. Figure 31.7.

Present State Next State Output
X=0 X=1 X=0 X=1
a f b 0 0
b b c 1 1
c a f 0 1
d c d 1 0
f d c 0 0

Table 32.9c Next State table, with state ‘e’ eliminated and instances of state ‘e’ replaced by state ‘c’

digital logic design  State Reduction

Reconsider the initial sequence a, b, c, f, d, d, e, g, e, g, d, e, a, f, d, e, a starting from the initial state a. The inputs and outputs for the state sequence derived from the simplified State diagram are shown in table 32.10.

state a b c f d d c f d c a f d c a
Input 1 1 1 0 1 0 1 0 0 0 0 0 0 0
Output 0 1 1 0 0 1 1 0 1 0 0 0 1 0

Table 32.10 The input and output sequence obtained from the simplified state diagram

Elimination of equivalent states results in the reduction in the number of flip-flops. In the example described, the elimination of two states reduces the total number of unique states from seven to five, however the number of flip-flops remain the same which is three. If the number of states had been reduced to four then only two flip-flops would be required.

VN:F [1.9.14_1148]
Rating: 10.0/10 (1 vote cast)
VN:F [1.9.14_1148]
Rating: +1 (from 1 vote)
State Reduction , 10.0 out of 10 based on 1 rating