What is the name of the circuit structure that generates a state machine's jumping signals?

Hi,
What is the name of the circuit structure that generates a state machine's jumping signals?
I remember I looked at the circuit structure and wrongly remembered the structure name as "decision tree". By looking at Wikipedia, I realize that it is a wrong name.
What is the correct name?
Thank you.
Weng

Reply to
Weng Tianxiang
Loading thread data ...
If then else or Case select
Reply to
Andy Bennet
Transition or next state logic?
Hans
formatting link

Reply to
HT-Lab
s jumping signals?
tructure name as "decision tree". By looking at Wikipedia, I realize that i t is a wrong name.
I'm not sure there really is any universal term for this other than "logic" . A state machine has two main elements, the memory or flip flops used to store the state and the logic that generates the next state. Then there is additional logic if outputs are required other than the state signals them selves. I don't recall any formalism that names these logic blocks separat ely other than perhaps "next state" and "output" logic.
What is the context of your question exactly? Maybe that will help.
Rick C.
Tesla referral code -
formatting link
Reply to
gnuarm.deletethisbit
Hi,
Sorry, maybe I did not specify my question clearly.
Here is a code example I would ask for answer:
type State_Type is ( S0, S1, ...);
signal WState, WState_NS : State_Type; ...;
a : process(CLK) begin if rising_edge(CLK) then if SINI = '1' then WState
Reply to
Weng Tianxiang
Are you looking for the terms "Mealy" and "Moore"? A "Mealy" output is a combinational function of the current state, and the current inputs. A "Moore" output is a function of just the current state. One could label the "next state" signals as "Mealy" outputs of the state machine.
Xilinx and Altera generates the circuit for a state machine the same way as any other synthesized logic. It infers states as memory or registers, with combinataional logic between them. There's some specialized tools that's sometimes triggered to specific optimize recognized "state machines" - however this is an optimization only (perhaps fault tolerant too). I note that recently most of my state machines are NOT recognized as a state machine by Vivado. I don't really care, as long as it meets timing...
Regards,
Mark
Reply to
gtwrek
Hi Mark,
It is not about "Mealy" and "Moore" that is about how to design a state machine.
My question is how to generate a state machine in a systematic circuit, including all signals, state outputs and non-state outputs, whether or not how complex a state machine structure is.
If there is no systematic circuit structure to fully generate any type of state machines, I would like to invent such circuits and apply for a patent.
But in my deep mind I think there should be such systematic circuits and it is
not my turn, not my turn, not my turn, not my turn, not my turn, not my turn,
to file such a patent.
I once read a patent from Altera describing how to generate a circuit for a state machine. At the time when I was reading I found the method was absurd. Now I couldn't find the patent any more.
Thank you.
Weng
Reply to
Weng Tianxiang
Still not clear on what you're thinking about with regard to a "systematic" circuit structure.
A tool to generate a "circuit, including all signals, state outputs and non-state outputs" pretty much describes a Synthesis tool. And I'd rhink most of the patents on those things have been filed and granted for a LONG time.
I've never really understood the exceptional focus on "state machines" - it's just logic and registers like any other part of the design. Some clever folks decided that under very special circumstances, one could better optimized certain datapaths - and the first "state machine" optimizer was created. But it's just that an optimization tool - one that can be used in a limitted set of circumstances. In today's large designs where random logic is pretty much free, these minor optimizations don't usually interest me.
Good luck,
Mark
Reply to
gtwrek
Hi,
Now I believe the term "decision tree" is used for generating a state machine. Because at every node in a state machine a decision must be made to determine where to go and what signals's values should be.
Thank you.
Weng
Reply to
Weng Tianxiang
Has it occurred to you that no tool gives a hoot about the term 'state mach ine'? State machine is nothing more than a human label given to a chunk of code so that a human can have a classification term to use when discussing it? A tool simply takes a logic description and transforms it into logic ga tes or lookup tables or whatever the underlying physical implementation. No concept of a 'state machine'is required for that task. Similarly, there i s no advantage when performing that transformation as to whether the input describes a 'state machine' or a 'shift register'. 'Memory array' is a usef ul classification because recognizing something describing a memory array c an change how the description gets implemented. 'State machine'... don't th ink so.
Kevin
Reply to
KJ
Forgot to add that your statement "Because at every node in a state machine a decision must be made to determine where to go and what signals's values should be" is not at all what is going on... unless you want to say that i t applies to ALL synthesis operations that transform a human readable logic description into an implementation. I wouldn't call that a 'decision tree' , but you may feel differently.
Kevin
Reply to
KJ
ine's jumping signals?
he structure name as "decision tree". By looking at Wikipedia, I realize th at it is a wrong name.
n generate signal S0_C1 and others. I think it is an oldest circuit.
ne?
First of all, I don't agree with your hypothesis that signals S0_C1, et. al . exist at any point in this design. They may, but might not depending on the details of the state encoding and the optimizations performed.
I think what you are failing to consider is that the states, S0, S1, et. al . are encoded in some manner. The actual logic generated would then depend on all the input combinations that assert a given bit in the encoded state values. So if the state variable WState_NS is three bits and uses 00, 01 and 10 for the state values, the variable WState_NS(0) would have its own e quation (I'll skip solving that for you) and the variable WState_NS(1) woul d have another equation which is not likely to be the same.
There are likely to be shared logic in the individual bits of the state var iable, but how likely is it that the software will optimize out the exact s ignals you hypothesize?
Does this make sense?
Rick C.
Tesla referral code +
formatting link
Reply to
gnuarm.deletethisbit
I think Weng is looking for something very abstract and algorithmic. I believe he is expecting state machine design to be more complex than it is. This is well furrowed ground. Weng, you would do better to look elsewhere.
Rick C.
Tesla referral code --
formatting link

PS I am posting my referral link because if anyone wants to buy a Tesla and they use my link you will get free supercharging for six months (as of now for sure) and I will get a brownie point toward a wall connector that I'd like.
Reply to
gnuarm.deletethisbit
chine's jumping signals?
the structure name as "decision tree". By looking at Wikipedia, I realize that it is a wrong name.
can generate signal S0_C1 and others. I think it is an oldest circuit.
hine?
al. exist at any point in this design. They may, but might not depending o n the details of the state encoding and the optimizations performed.
al. are encoded in some manner. The actual logic generated would then depe nd on all the input combinations that assert a given bit in the encoded sta te values. So if the state variable WState_NS is three bits and uses 00, 0 1 and 10 for the state values, the variable WState_NS(0) would have its own equation (I'll skip solving that for you) and the variable WState_NS(1) wo uld have another equation which is not likely to be the same.
ariable, but how likely is it that the software will optimize out the exact signals you hypothesize?
Opps, I should have said if "the state variable WState_NS is two bits"
Rick C.
Reply to
gnuarm.deletethisbit
e:
machine's jumping signals?
ed the structure name as "decision tree". By looking at Wikipedia, I realiz e that it is a wrong name.
t can generate signal S0_C1 and others. I think it is an oldest circuit.
achine?
. al. exist at any point in this design. They may, but might not depending on the details of the state encoding and the optimizations performed.
. al. are encoded in some manner. The actual logic generated would then de pend on all the input combinations that assert a given bit in the encoded s tate values. So if the state variable WState_NS is three bits and uses 00, 01 and 10 for the state values, the variable WState_NS(0) would have its o wn equation (I'll skip solving that for you) and the variable WState_NS(1) would have another equation which is not likely to be the same.
variable, but how likely is it that the software will optimize out the exa ct signals you hypothesize?
Rick, How a state machine is constructed is not important, the important thing is : there is A BIT SIGNAL that will make the state machine going from state S 0 to state S1 on the next cycle when it is asserted on the current cycle ba sed on the S0_C1 logic which I have given before.
S0_C1 logic is A BIT SIGNAL.
Weng
Reply to
Weng Tianxiang
is: there is A BIT SIGNAL that will make the state machine going from state S0 to state S1 on the next cycle when it is asserted on the current cycle based on the S0_C1 logic which I have given before.
That signal only 'exists' for a one-hot encoded state machine, but not for any other encoding. Given that logic in an FPGA is implemented inside look up tables even that signal won't actually exist either when implemented in such a fashion. Given that you state without basis "the important thing is : there is A BIT SIGNAL that will make the state machine going from state S 0 to state S1" and I've shown how that is not the case, then I guess it's n ot so important after all. You can (and will) choose to dismiss what I've said because you're not interested in actual logic synthesis but you were t he one who stated the importance of the existence of this signal, yet I've shown your statement to be false.
Now, it is possible for you to choose to write your source code in a way th at you do have such a discrete signal. But doing so is your personal style choice and has no bearing on any more general concepts such as 'state mach ine' or any bearing on how anyone else would write their own source code fo r a 'state machine'. As I previously mentioned, the term 'state machine' i s really only a classification term to allow for human discussion, the term has no real importance in logic synthesis or design.
Kevin
Reply to
KJ
:
g is: there is A BIT SIGNAL that will make the state machine going from sta te S0 to state S1 on the next cycle when it is asserted on the current cycl e based on the S0_C1 logic which I have given before.
r any other encoding. Given that logic in an FPGA is implemented inside lo okup tables even that signal won't actually exist either when implemented i n such a fashion. Given that you state without basis "the important thing is: there is A BIT SIGNAL that will make the state machine going from state S0 to state S1" and I've shown how that is not the case, then I guess it's not so important after all. You can (and will) choose to dismiss what I'v e said because you're not interested in actual logic synthesis but you were the one who stated the importance of the existence of this signal, yet I'v e shown your statement to be false.
that you do have such a discrete signal. But doing so is your personal sty le choice and has no bearing on any more general concepts such as 'state ma chine' or any bearing on how anyone else would write their own source code for a 'state machine'. As I previously mentioned, the term 'state machine' is really only a classification term to allow for human discussion, the te rm has no real importance in logic synthesis or design.
I don't want to start an argument about what I am doing, right or wrong. In a month or so I will publish something that will shows your following 2 cl aims are wrong:
1. "That signal only 'exists' for a one-hot encoded state machine, but not for any other encoding. "
2. "As I previously mentioned, the term 'state machine' is really only a cl assification term to allow for human discussion, the term has no real impor tance in logic synthesis or design."
I will give no reason why it is.
Weng
Reply to
Weng Tianxiang
ote:
e machine's jumping signals?
ered the structure name as "decision tree". By looking at Wikipedia, I real ize that it is a wrong name.
hat can generate signal S0_C1 and others. I think it is an oldest circuit.
machine?
et. al. exist at any point in this design. They may, but might not dependi ng on the details of the state encoding and the optimizations performed.
et. al. are encoded in some manner. The actual logic generated would then depend on all the input combinations that assert a given bit in the encoded state values. So if the state variable WState_NS is three bits and uses 0 0, 01 and 10 for the state values, the variable WState_NS(0) would have its own equation (I'll skip solving that for you) and the variable WState_NS(1 ) would have another equation which is not likely to be the same.
te variable, but how likely is it that the software will optimize out the e xact signals you hypothesize?
is: there is A BIT SIGNAL that will make the state machine going from state S0 to state S1 on the next cycle when it is asserted on the current cycle based on the S0_C1 logic which I have given before.
That is where you fail to understand. Your code does not include the signa l S0_C1. The structure of the state machine does not dictate such a signal . You can conceive of this signal in your mind and perform any design task s using this signal, but that does not mean it is in any way real. Even in the case of a 1-hot encoded machine this signal will only exist if there a re no other ways to enter the state S1.
So if you only wish to suppose that the signal S0_C1 exists in your theoret ical analysis, fine. I have found in certain cases decomposition to simila r basic signals to be useful in specifying state machines in a simple way. But don't for a minute believe that it exists in any real world implementa tion or is in any way fundamental to the operation of the state machine.
Of your questions:
n > generate signal S0_C1 and others. I think it is an oldest circuit.
Yes, it is called a state/next-state table and is very simple.
We just call it "logic".
ne?
Yes, they take the logic you define in your HDL and apply the many types of decomposition, optimization and synthesis on it that are also used on all the other logic code you use in the rest of your design.
Rick C.
Tesla referral code --
formatting link
Reply to
gnuarm.deletethisbit
On Friday, December 14, 2018 at 7:30:22 PM UTC-8, snipped-for-privacy@gmail.com w rote:
:
ate machine's jumping signals?
mbered the structure name as "decision tree". By looking at Wikipedia, I re alize that it is a wrong name.
that can generate signal S0_C1 and others. I think it is an oldest circuit .
te machine?
, et. al. exist at any point in this design. They may, but might not depen ding on the details of the state encoding and the optimizations performed.
, et. al. are encoded in some manner. The actual logic generated would the n depend on all the input combinations that assert a given bit in the encod ed state values. So if the state variable WState_NS is three bits and uses 00, 01 and 10 for the state values, the variable WState_NS(0) would have i ts own equation (I'll skip solving that for you) and the variable WState_NS (1) would have another equation which is not likely to be the same.
tate variable, but how likely is it that the software will optimize out the exact signals you hypothesize?
"
g is: there is A BIT SIGNAL that will make the state machine going from sta te S0 to state S1 on the next cycle when it is asserted on the current cycl e based on the S0_C1 logic which I have given before.
nal S0_C1. The structure of the state machine does not dictate such a sign al. You can conceive of this signal in your mind and perform any design ta sks using this signal, but that does not mean it is in any way real. Even in the case of a 1-hot encoded machine this signal will only exist if there are no other ways to enter the state S1.
etical analysis, fine. I have found in certain cases decomposition to simi lar basic signals to be useful in specifying state machines in a simple way . But don't for a minute believe that it exists in any real world implemen tation or is in any way fundamental to the operation of the state machine.
can > generate signal S0_C1 and others. I think it is an oldest circuit.
hine?
of decomposition, optimization and synthesis on it that are also used on al l the other logic code you use in the rest of your design.
Hi Rick, I don't want to start an argument about what I am doing, right or wrong. In a month or so I will publish something that will show your following 2 cla ims are wrong:
1. Even in the case of a 1-hot encoded machine this signal will only exist if there are no other ways to enter the state S1.
2. But don't for a minute believe that it exists in any real world implemen tation or is in any way fundamental to the operation of the state machine.
Thank you.
Weng
Reply to
Weng Tianxiang
te:
e:
state machine's jumping signals?
membered the structure name as "decision tree". By looking at Wikipedia, I realize that it is a wrong name.
od that can generate signal S0_C1 and others. I think it is an oldest circu it.
?
tate machine?
C1, et. al. exist at any point in this design. They may, but might not dep ending on the details of the state encoding and the optimizations performed .
S1, et. al. are encoded in some manner. The actual logic generated would t hen depend on all the input combinations that assert a given bit in the enc oded state values. So if the state variable WState_NS is three bits and us es 00, 01 and 10 for the state values, the variable WState_NS(0) would have its own equation (I'll skip solving that for you) and the variable WState_ NS(1) would have another equation which is not likely to be the same.
state variable, but how likely is it that the software will optimize out t he exact signals you hypothesize?
ts"
ing is: there is A BIT SIGNAL that will make the state machine going from s tate S0 to state S1 on the next cycle when it is asserted on the current cy cle based on the S0_C1 logic which I have given before.
ignal S0_C1. The structure of the state machine does not dictate such a si gnal. You can conceive of this signal in your mind and perform any design tasks using this signal, but that does not mean it is in any way real. Eve n in the case of a 1-hot encoded machine this signal will only exist if the re are no other ways to enter the state S1.
oretical analysis, fine. I have found in certain cases decomposition to si milar basic signals to be useful in specifying state machines in a simple w ay. But don't for a minute believe that it exists in any real world implem entation or is in any way fundamental to the operation of the state machine .
t can > generate signal S0_C1 and others. I think it is an oldest circuit.
achine?
s of decomposition, optimization and synthesis on it that are also used on all the other logic code you use in the rest of your design.
In a month or so I will publish something that will show your following 2 c laims are wrong:
t if there are no other ways to enter the state S1.
entation or is in any way fundamental to the operation of the state machine .
No need to argue. Just explain. "The best argument is that which seems me rely an explanation." - Dale Carnegie
I have studied the 1-hot state machine. The only signal required for each "hot" (state element) is it's next value. That value depends on *all* the possible transitions into a given state, not just a transition from any one state into that state which is what your S0_C1 bit signal is. The actual signal at the input to the state FF is the logical OR of the equivalent sig nal for transitions from *all* the states that have transitions into this s tate, including a transition from this state itself... unless the clock ena ble is also used, sometimes inefficiently. So the input to the FF might be an OR of S0_C1, S1_C1N, S2_something...
Of course, you can write your code that way if you wish (write code, draw d iagrams, etc). My only point is this has nothing to do with the actual res ulting signals produced to construct the state machine in an FPGA or other logic device. The actual input to the state FF is what we call next_state and is not always equivalent to what you seem to be picturing. What you se em to be picturing can be used in design, but it may not be a real signal i n the implementation.
Rick C.
Tesla referral code -+
formatting link
Reply to
gnuarm.deletethisbit

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.