EDAboard.com | EDAboard.de | EDAboard.co.uk | WTWH Media

What is the name of the circuit structure that generates a s

Ask a question - edaboard.com

elektroda.net NewsGroups Forum Index - FPGA - What is the name of the circuit structure that generates a s

Goto page 1, 2, 3, 4  Next

Weng Tianxiang
Guest

Thu Dec 13, 2018 3:45 pm   



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

Andy Bennet
Guest

Thu Dec 13, 2018 4:45 pm   



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

HT-Lab
Guest

Thu Dec 13, 2018 5:45 pm   



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


Guest

Thu Dec 13, 2018 9:45 pm   



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

Weng Tianxiang
Guest

Thu Dec 13, 2018 9:45 pm   



On Thursday, December 13, 2018 at 8:06:46 AM UTC-8, HT-Lab wrote:
Quote:
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

gtwrek
Guest

Thu Dec 13, 2018 10:45 pm   



In article <d9feef36-d31d-4870-9170-700041248e94_at_googlegroups.com>,
Weng Tianxiang <wtxwtx_at_gmail.com> wrote:
Quote:

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

gtwrek
Guest

Thu Dec 13, 2018 11:45 pm   



In article <ab41052b-483a-45ff-9000-ca442466d54b_at_googlegroups.com>,
Weng Tianxiang <wtxwtx_at_gmail.com> wrote:
Quote:

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

Weng Tianxiang
Guest

Thu Dec 13, 2018 11:45 pm   



On Thursday, December 13, 2018 at 1:27:52 PM UTC-8, gtwrek wrote:
Quote:
In article <d9feef36-d31d-4870-9170-700041248e94_at_googlegroups.com>,
Weng Tianxiang <wtxwtx_at_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

Weng Tianxiang
Guest

Fri Dec 14, 2018 12:45 am   



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

KJ
Guest

Fri Dec 14, 2018 1:45 am   



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

KJ
Guest

Fri Dec 14, 2018 2:45 am   



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 it 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


Guest

Fri Dec 14, 2018 3:45 am   



On Thursday, December 13, 2018 at 9:02:26 PM UTC-5, gnuarm.del...@gmail.com wrote:
Quote:
On Thursday, December 13, 2018 at 3:14:03 PM UTC-5, Weng Tianxiang wrote:
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?

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 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.

There are likely to be shared logic in the individual bits of the state variable, but how likely is it that the software will optimize out the exact signals you hypothesize?

Does this make sense?

Rick C.

Tesla referral code + https://ts.la/richard11209


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

Rick C.


Guest

Fri Dec 14, 2018 3:45 am   



On Thursday, December 13, 2018 at 5:19:51 PM UTC-5, gtwrek wrote:
Quote:
In article <ab41052b-483a-45ff-9000-ca442466d54b_at_googlegroups.com>,
Weng Tianxiang <wtxwtx_at_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


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.


Guest

Fri Dec 14, 2018 3:45 am   



On Thursday, December 13, 2018 at 3:14:03 PM UTC-5, Weng Tianxiang wrote:
Quote:
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?


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 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.

There are likely to be shared logic in the individual bits of the state variable, but how likely is it that the software will optimize out the exact signals you hypothesize?

Does this make sense?

Rick C.

Tesla referral code + https://ts.la/richard11209

Weng Tianxiang
Guest

Fri Dec 14, 2018 4:45 am   



On Thursday, December 13, 2018 at 6:09:09 PM UTC-8, gnuarm.del...@gmail.com wrote:
Quote:
On Thursday, December 13, 2018 at 9:02:26 PM UTC-5, gnuarm.del...@gmail.com wrote:
On Thursday, December 13, 2018 at 3:14:03 PM UTC-5, Weng Tianxiang wrote:
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?

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 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.

There are likely to be shared logic in the individual bits of the state variable, but how likely is it that the software will optimize out the exact signals you hypothesize?

Does this make sense?

Rick C.

Tesla referral code + https://ts.la/richard11209

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

Rick C.


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 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.

S0_C1 logic is A BIT SIGNAL.

Weng

Goto page 1, 2, 3, 4  Next

elektroda.net NewsGroups Forum Index - FPGA - What is the name of the circuit structure that generates a s

Ask a question - edaboard.com

Arabic version Bulgarian version Catalan version Czech version Danish version German version Greek version English version Spanish version Finnish version French version Hindi version Croatian version Indonesian version Italian version Hebrew version Japanese version Korean version Lithuanian version Latvian version Dutch version Norwegian version Polish version Portuguese version Romanian version Russian version Slovak version Slovenian version Serbian version Swedish version Tagalog version Ukrainian version Vietnamese version Chinese version Turkish version
EDAboard.com map