Electronic – Finding the logic expressions of a finite state machine that has three possible inputs

state-machines

I'm familiar with finite state machines when there are two possible states for input, which I will call w. That is, w = 1 or w = 0. However, what about the situation in which w can equal A, B, or C? In this situation, I believe that I would have to represent the input with two bits, such that A = 00, B = 01, and C = 11.

For example, say I have to detect the sequence ABCB (using a Moore Machine). Below is a picture of the state diagram, state-table, and state-assignment table:

enter image description here

Here, I represent the present state with three bits, and the next state with three bits. Normally, I have no issue finding the required logic expressions using Karnaugh Maps given that w = 1 or 0. However, here w = A, B, or C. Assuming that I let A = 00, B = 01, and C = 11, how would I derive the appropriate logic expressions?

My inclination is to solve a 5-variable Karnaugh Map for each Next State flip-flop (i.e. Y2, Y1, Y0). For instance, Y2 is some function of y1, y2, y3, and w that can be found using a Karnaugh Map.

Am I heading in the right direction with my reasoning here? Any constructive input is appreciated.

Note: This is related to an assignment of mine, but this is not the pattern I'm trying to detect.

Edit: Now that I thought about it some more, it seems like I really have 5 bits to work with in regard to the Karnaugh Map – which it technically four variables because yn represents 1 bit and w represents two bits.

Best Answer

You are almost done, all what's left is to get the logic equations from the table. Remember that w is an input so it is part of the present state and we will use it to compute values of the next state.

Let w be a 2 bit number, $$w = w_1w_0$$

so if we let A = 00, B = 01, and C = 11 then:

$$ w = \left.\begin{cases} \bar{w_1} \bar{w_0} & w = A\\ \\ w_1 \bar{w_0} & w = B\\ \\ w_1 w_0 & w = C \end{cases} \right\} \\ \\ $$

and the 5 states are $$ S_i = \left. \begin{cases} \bar{y_2 }\bar{y_1 }\bar{y_0 }& i = 1 \\ \\ \bar{y_2 }\bar{y_1 } y_0 & i = 2 \\ \\ \bar{y_2 } y_1 \bar{y_0 } & i = 3 \\ \\ \bar{y_2 } y_1 y_0 & i = 4 \\ \\ y_2 \bar{y_1} \bar{y_0 } & i = 5 \end{cases} \right\} $$

To get the logic for computing the next state you get the boolean equation for each bit of the next state separately.E.g to get the logic for computing y0 :

$$ y_{0 , next} = S_1 A + S_2 A + S_3A + S_3 C + S_4 A + S_5 A $$

$$ y_{0, next} = \bar{y_2 }\bar{y_1 }\bar{y_0 } \bar{w_1} \bar{w_0} + \bar{y_2 }\bar{y_1 } y_0 \bar{w_1} \bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } \bar{w_1} \bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } w_1 w_0 + \bar{y_2 } y_1 y_0 \bar{w_1} \bar{w_0} + y_2 \bar{y_1} \bar{y_0 } \bar{w_1} \bar{w_0} $$

which reduces to

$$ y_{0, next} = \bar{w_1}\bar{w_0} + \bar{y_2 } y_1 \bar{y_0 } w_1 w_0 $$

Repeat this for y2 and y1, to get the rest of the combinational logic required.

The output(z) is high when this state machine is in state 5 so Z will be given by:

$$ z = S_5 = y_2 \bar{y_1} \bar{y_0 } $$

This is a moore machine as Z is only dependent on the current state.

Related Topic