I'm given a state machine (6 states), 5 outputs, and 8 inputs. Now I have to answer "what is the minimum number of D flip flops needed to implement the machine and why?"
Is there a technique to this? Here's all I've come up with: I know the answer for counters, but do state machines function similarly? 1 flip flop for every 2 states? Or 1 flip flop per state? Or perhaps zero are required?
Thank you for any help!
Is there a technique to this? Here's all I've come up with: I know the answer for counters, but do state machines function similarly? 1 flip flop for every 2 states? Or 1 flip flop per state? Or perhaps zero are required?
Thank you for any help!
-
A Very Good question!. The answer may depend upon the exact State machine you are building, as there may well be shortcuts possible.
Generally speaking, you need one flip flop for every FACTOR OF 2 states, as each has two states of output, and can be multiplied. However, 3 flip flops admits of 2^3 = 8 states, which includes 2 Unwanted states. These could possibly be "blanked off" by causing them to decay into one of the 6 permitted states, at the switching speed of the logic family (glitch conditions exist, temporarily).
It is Always unwise to allow Unwanted states in electronic equipment, as it will darn sure enter them and get stuck or behave unpredictably, even if only at switch-on!. Hence it is Not Sufficient to design a circuit which "Apparently" cannot Enter into Illegal states, for all sequences of input changes. It is necessary to design-in Avoiding Actions for when they Do occur.
I haven't heard the term "state machine" in 30+ years and consider it an Academic Curiosity, nowadays, as extra gates and flip flops are so cheap and almost always available at nil extra cost (eg in a Gate Array or Programmable Logic Device).
So I reckon the answer is 3.
Generally speaking, you need one flip flop for every FACTOR OF 2 states, as each has two states of output, and can be multiplied. However, 3 flip flops admits of 2^3 = 8 states, which includes 2 Unwanted states. These could possibly be "blanked off" by causing them to decay into one of the 6 permitted states, at the switching speed of the logic family (glitch conditions exist, temporarily).
It is Always unwise to allow Unwanted states in electronic equipment, as it will darn sure enter them and get stuck or behave unpredictably, even if only at switch-on!. Hence it is Not Sufficient to design a circuit which "Apparently" cannot Enter into Illegal states, for all sequences of input changes. It is necessary to design-in Avoiding Actions for when they Do occur.
I haven't heard the term "state machine" in 30+ years and consider it an Academic Curiosity, nowadays, as extra gates and flip flops are so cheap and almost always available at nil extra cost (eg in a Gate Array or Programmable Logic Device).
So I reckon the answer is 3.
-
I would need 1 flip flop for every two states....
so the minimum would be 3 flip-flops...
Flip-flops will only determine the number of states, for input and output, additional combination logic would be required....
However, going strictly by the question,
1 Flip-Flop for every 2 states, that would be 3 Flip-Flops giving you 8 states to use....
so the minimum would be 3 flip-flops...
Flip-flops will only determine the number of states, for input and output, additional combination logic would be required....
However, going strictly by the question,
1 Flip-Flop for every 2 states, that would be 3 Flip-Flops giving you 8 states to use....