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

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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

  

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On 13/12/2018 13:45, Weng Tianxiang wrote:
Quoted text here. Click to load it

If then else or Case select

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On 13/12/2018 13:45, Weng Tianxiang wrote:
Quoted text here. Click to load it
Transition or next state logic?

Hans
www.ht-lab.com


Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 8:06:46 AM UTC-8, HT-Lab wrote:
Quoted text here. Click to load it

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 <= S0;

     else
    WState <= WState_NS;
     end if;
  end if;
end process;

b : process(all)
begin
  case WState is
    when S0 =>
      if C1 then
        WState_NS <= S1;

      elsif C2 then
    WState_NS <= S2;
        
      else        
        WState_NS <= S0;
      end if;
    ...;
  end case;
end process;

Now a synthesizer must generate a signal S0_C1 as follows

S0_C1 <= not SINI and WState = S0 and C1;

When S0_C1 is asserted, WState will go from S0 to S1.

I call signal S0_C1 a jumping signal for the state machine.

I want to know:
1. Is there a systematic circuit structure or a systematic method that can generate signal S0_C1 and others. I think it is an oldest circuit.

2. If there is a systematic circuit structure, what its name is?

3. Do you know how Xilinx or Altera generates a circuit for a state machine?

Thank you.

Weng

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
Quoted text here. Click to load it

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
  






Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 1:27:52 PM UTC-8, gtwrek wrote:
Quoted text here. Click to load it

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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
Quoted text here. Click to load it

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



Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 2:19:51 PM UTC-8, gtwrek wrote:
Quoted text here. Click to load it

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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 5:19:51 PM UTC-5, gtwrek wrote:
Quoted text here. Click to load it

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 -- https://ts.la/richard11209

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.  

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 3:14:03 PM UTC-5, Weng Tianxiang wrote:
Quoted text here. Click to load it
ine's jumping signals?
Quoted text here. Click to load it
he structure name as "decision tree". By looking at Wikipedia, I realize th
at it is a wrong name.
Quoted text here. Click to load it
n generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
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 + https://ts.la/richard11209

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 9:02:26 PM UTC-5, snipped-for-privacy@gmail.com
 wrote:
Quoted text here. Click to load it
chine's jumping signals?
Quoted text here. Click to load it
 the structure name as "decision tree". By looking at Wikipedia, I realize  
that it is a wrong name.
Quoted text here. Click to load it
can generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
hine?
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
ariable, but how likely is it that the software will optimize out the exact
 signals you hypothesize?  
Quoted text here. Click to load it

Opps, I should have said if "the state variable WState_NS is two bits"

  Rick C.

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 6:09:09 PM UTC-8, snipped-for-privacy@gmail.com
 wrote:
Quoted text here. Click to load it
om wrote:
Quoted text here. Click to load it
e:
Quoted text here. Click to load it
machine's jumping signals?
Quoted text here. Click to load it
ed the structure name as "decision tree". By looking at Wikipedia, I realiz
e that it is a wrong name.
Quoted text here. Click to load it
t can generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
achine?
Quoted text here. Click to load it
. 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.  
Quoted text here. Click to load it
. 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.  
Quoted text here. Click to load it
 variable, but how likely is it that the software will optimize out the exa
ct signals you hypothesize?  
Quoted text here. Click to load it

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


Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 10:06:58 PM UTC-5, Weng Tianxiang wrote:
Quoted text here. Click to load it
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.
Quoted text here. Click to load it

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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Friday, December 14, 2018 at 4:43:57 AM UTC-8, KJ wrote:
Quoted text here. Click to load it
:
Quoted text here. Click to load it
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.
Quoted text here. Click to load it
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.
Quoted text here. Click to load it
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.
Quoted text here. Click to load it

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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Thursday, December 13, 2018 at 10:06:58 PM UTC-5, Weng Tianxiang wrote:
Quoted text here. Click to load it
om wrote:
Quoted text here. Click to load it
.com wrote:
Quoted text here. Click to load it
ote:
Quoted text here. Click to load it
e machine's jumping signals?
Quoted text here. Click to load it
ered the structure name as "decision tree". By looking at Wikipedia, I real
ize that it is a wrong name.
Quoted text here. Click to load it
hat can generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
 machine?
Quoted text here. Click to load it
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.  
  
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
te variable, but how likely is it that the software will optimize out the e
xact signals you hypothesize?  
Quoted text here. Click to load it
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.
Quoted text here. Click to load it

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:  
Quoted text here. Click to load it
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.  

Quoted text here. Click to load it

We just call it "logic".  

Quoted text here. Click to load it
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 -- https://ts.la/richard11209

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Friday, December 14, 2018 at 7:30:22 PM UTC-8, snipped-for-privacy@gmail.com w
rote:
Quoted text here. Click to load it
:
Quoted text here. Click to load it
.com wrote:
Quoted text here. Click to load it
il.com wrote:
Quoted text here. Click to load it
wrote:
Quoted text here. Click to load it
ate machine's jumping signals?
Quoted text here. Click to load it
mbered the structure name as "decision tree". By looking at Wikipedia, I re
alize that it is a wrong name.
Quoted text here. Click to load it
 that can generate signal S0_C1 and others. I think it is an oldest circuit
.
Quoted text here. Click to load it
te machine?
Quoted text here. Click to load it
, 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.  
  
Quoted text here. Click to load it
, 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.  
Quoted text here. Click to load it
tate variable, but how likely is it that the software will optimize out the
 exact signals you hypothesize?  
Quoted text here. Click to load it
"
Quoted text here. Click to load it
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.
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
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.  
  
Quoted text here. Click to load it
can > generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
hine?
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it

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

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On Friday, December 14, 2018 at 11:59:13 PM UTC-5, Weng Tianxiang wrote:
Quoted text here. Click to load it
 wrote:
Quoted text here. Click to load it
te:
Quoted text here. Click to load it
il.com wrote:
Quoted text here. Click to load it
mail.com wrote:
Quoted text here. Click to load it
g wrote:
Quoted text here. Click to load it
e:
Quoted text here. Click to load it
state machine's jumping signals?
Quoted text here. Click to load it
membered the structure name as "decision tree". By looking at Wikipedia, I  
realize that it is a wrong name.
Quoted text here. Click to load it
od that can generate signal S0_C1 and others. I think it is an oldest circu
it.
Quoted text here. Click to load it
?
Quoted text here. Click to load it
tate machine?
Quoted text here. Click to load it
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
.  
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
 state variable, but how likely is it that the software will optimize out t
he exact signals you hypothesize?  
Quoted text here. Click to load it
ts"
Quoted text here. Click to load it
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.
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
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
.  
Quoted text here. Click to load it
t can > generate signal S0_C1 and others. I think it is an oldest circuit.
Quoted text here. Click to load it
achine?
Quoted text here. Click to load it
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.  
Quoted text here. Click to load it
In a month or so I will publish something that will show your following 2 c
laims are wrong:  
Quoted text here. Click to load it
t if there are no other ways to enter the state S1.  
Quoted text here. Click to load it
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 -+ https://ts.la/richard11209

Re: What is the name of the circuit structure that generates a state machine's jumping signals?
On 15/12/2018 07:50, snipped-for-privacy@gmail.com wrote:
Quoted text here. Click to load it

In Xilinx can't you looks at the RTL logic generated and see what  
signals are being produced?

Dave

Site Timeline