2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Once you have worked this out manually you can verify your findings with Logic Friday which is free and very useful. \$\endgroup\$ – David Mar 27 '14 at 21:07
  • \$\begingroup\$ @David Regarding "manually," are you saying that my approach would work? \$\endgroup\$ – Mlagma Mar 27 '14 at 21:17
  • \$\begingroup\$ 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. \$\endgroup\$ – David Mar 27 '14 at 21:19
  • \$\begingroup\$ Ah, no problem. The tool you mentioned seems really useful. I'll check it out later. \$\endgroup\$ – Mlagma Mar 27 '14 at 21:20
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.