Continue to Site

# combination of 2 FSMs

Status
Not open for further replies.

#### vijay82

##### Member level 2
from this link, the following question:

An FSM, M, is constructed by connecting the output of a 3-state FSM to the inputs of an 9-state FSM. M is then reimplemented using a state register with the minimum number of bits. What is the maximum number of bits that may be needed to reimplement M?

It would seem the number of states in the new reimplemented FSM would be 12 but is 27, as given in the answer at the same place.

Isn't it logical to think the same 3+9 states would be coded in the new FSM, with transitions in the last 9 states depending on the output from the first 3 states (looking at it from an RTL coding perspective). Can anyone give an explanation for states being multiplicative (3*9) than additive(3+9)?

It's a matter of how many states in total you can have as a whole system. YOu have 3 states in the 1st FSM, and 9 states in the 2nd FSM. Combining them together, you can potentially have 3*9 states.
Just like throwing 2 dices. You can have 6*6 different states at most, not 6+6.

Thanks lostinxlation.

I knew what the multiplication means logically as you described in the dice example. However, since you've not described the next steps, I assume you're saying the next-state transitions would have to be re-written from scratch for the new FSM? I don't see any merit in that, given that the 2 FSMs are already coded and tested. And how would you deduce the new logic from what is existing? I tried taking a smaller example (2-state and 4-state FSM respectively) to get some better insight but it seems like too much work.

As far as I read the question, it sounds a new FSM is a rewritten from scratch with the same functionality as the original 2 FSM logic. It's asking about the maximum number of bits required for a state register which needs to represent 27 different states based on the original 2 FSM construction. There may be less than 27 states, but such an detail was not given and it asked about max number of bits.

Or I might read the question wrong. In fact, I don't know why it refers to the minimum number of bits.

Yeah, I had the same confusion of the solution being required with respect to maximum or minimum bits (both are mentioned in the question). I think the maximum number can be theoretically any number of bits (with the extra states being wasteful). As is common with such questions, I think it is the minimum number that is being asked to guarantee efficient state encoding and minimal gates.

I'm still not convinced though as to what will be the basis for re-coding the new FSM without some help from the older FSMs.

it isn't hard to do. for the 2,3 case:
old: X0 X1, and Y0, Y1, Y2
new: S00 S01 S02 S10 S11 S12
this is done for the 3,7 case as well.

If HDL were to be written:
(csm == X0) is the same as (csm == S00) || (csm == S01) || (csm == S02)

In the above example, the 2b+4b combined state machines can combine to form a 5b state machine. The logic may be more complex to determine next state.

Yeah, I had the same confusion of the solution being required with respect to maximum or minimum bits (both are mentioned in the question). I think the maximum number can be theoretically any number of bits (with the extra states being wasteful). As is common with such questions, I think it is the minimum number that is being asked to guarantee efficient state encoding and minimal gates.

I'm still not convinced though as to what will be the basis for re-coding the new FSM without some help from the older FSMs.
I think the original question is very logical, and correct.
It clearly says that the new, combined, state machine is implemented with the minimum number of bits.
We don't know this number, but we know the upper bound, the worst case.
This is the maximum they ask for, and it is 5, since no more than 5 bits are needed to encode the states,
which are 27 or less.

Since we don't know much about the original state machines, we can only calculate the worst case.

Status
Not open for further replies.