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

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:

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.

• Once you have worked this out manually you can verify your findings with Logic Friday which is free and very useful. – David Mar 27 '14 at 21:07
• @David Regarding "manually," are you saying that my approach would work? – Mlagma Mar 27 '14 at 21:17
• Sorry, I lack the knowledge to answer that. I just thought it would be helpful to have some way of verifying results at a later date. – David Mar 27 '14 at 21:19
• Ah, no problem. The tool you mentioned seems really useful. I'll check it out later. – Mlagma Mar 27 '14 at 21:20

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.