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

 

On 13/12/2018 13:45, Weng Tianxiang wrote:
> 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
> 
>   
> 

If then else or Case select

On 13/12/2018 13:45, Weng Tianxiang wrote:
> 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
> 
>   
> 
Transition or next state logic?

Hans
www.ht-lab.com

On Thursday, December 13, 2018 at 8:45:47 AM UTC-5, Weng Tianxiang wrote:
> 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?

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 themselves.  I don't recall any formalism that names these logic blocks separately 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 - https://ts.la/richard11209

On Thursday, December 13, 2018 at 8:06:46 AM UTC-8, HT-Lab wrote:
> On 13/12/2018 13:45, Weng Tianxiang wrote:
> > 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
> > 
> >   
> > 
> Transition or next state logic?
> 
> Hans
> www.ht-lab.com

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

In article <d9feef36-d31d-4870-9170-700041248e94@googlegroups.com>,
Weng Tianxiang  <wtxwtx@gmail.com> wrote:
>
>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?
>

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
 

On Thursday, December 13, 2018 at 1:27:52 PM UTC-8, gtwrek wrote:
> In article <d9feef36-d31d-4870-9170-700041248e94@googlegroups.com>,
> Weng Tianxiang  <wtxwtx@gmail.com> wrote:
> >
> >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?
> >
> 
> 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

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

In article <ab41052b-483a-45ff-9000-ca442466d54b@googlegroups.com>,
Weng Tianxiang  <wtxwtx@gmail.com> wrote:
>
>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.

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

On Thursday, December 13, 2018 at 2:19:51 PM UTC-8, gtwrek wrote:
> In article <ab41052b-483a-45ff-9000-ca442466d54b@googlegroups.com>,
> Weng Tianxiang  <wtxwtx@gmail.com> wrote:
> >
> >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.
> 
> 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

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

Has it occurred to you that no tool gives a hoot about the term 'state machine'? 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 gates or lookup tables or whatever the underlying physical implementation. No concept of a 'state machine'is required for that task.  Similarly, there is no advantage when performing that transformation as to whether the input describes a 'state machine' or a 'shift register'. 'Memory array' is a useful classification because recognizing something describing a memory array can change how the description gets implemented. 'State machine'... don't think so.

Kevin