Can I use Verilog or SystemVerilog to write a state machine

[Weng Tianxiang]

Hi,
Thank you for more people involved in this discussion.

1. Here is my prior art description of FIG. 1 on how a clock gating device is used. Clock gating device is used in my invention as a prior art device.

[0009] FIG. 1 is an interface diagram for any type of clock gating device currently known in the art. These types of clock gating devices have their clock input ‘>’ coupled to a state machine’s clock source, with its clock pulse output C driving a clock pulse on the next cycle if the clock enable input E is asserted on the current cycle.

2. Because of the strict requirement of IEEE Transaction requirement on paper's originality, I cannot disclose any details of my invention until about 3 months later. The paper contains 11 double column pages, excluding the author's biography, and 10 related schematic diagrams of related state machine's circuits.

From the schematic diagrams you can immediately know that the full circuit of a state machine is much simpler than any counterpart of a conventional state machine circuit with clock enable logic naturally generated without any extra logic.

Thank you.

Weng

 

[KJ]

On Wednesday, January 9, 2019 at 11:44:56 AM UTC-5, Weng Tianxiang wrote:

From the schematic diagrams you can immediately know that the full circuit of a state machine is much simpler than any counterpart of a conventional state machine circuit with clock enable logic naturally generated without any extra logic.

The schematic of a ripple counter implemented with T flip flops is also quite simple when compared to that of a conventional synchronous counter. As I previously posted, use of T flip flops rather than D flip flops (and the consequential generation of gated clocks to support synthesis using T flip flops) is existing prior art that is covered in old textbooks. Your chosen subset of use cases such as state machines is a restriction over what is already out as prior art which covered all synchronous machines.

Kevin Jennings

 

[Weng Tianxiang]

“Your chosen subset of use cases such as state machines is a restriction over what is already out as prior art which covered all synchronous machines. ”

My method only applies to a state machine circuit and defines many brand new concepts for a state machine.

The method is useless for FPGA as nobody cares about a low power state machine circuit. The saver of my invention is the case of CPU' 100,000 state machines for 6M L2 cache.

Weng

 

[gtwrek]

In article <3913d54c-b09e-4a4d-8890-3359a13ba7ea@googlegroups.com>,
Weng Tianxiang <wtxwtx@gmail.com> wrote:

“Your chosen subset of use cases such as state machines is a restriction over what is already out as prior art which covered all synchronous machines. ”

My method only applies to a state machine circuit and defines many brand new concepts for a state machine.

The method is useless for FPGA as nobody cares about a low power state machine circuit. The saver of my invention is the case of CPU' 100,000 state machines
for 6M L2 cache.

Sigh, can't believe I keep letting myself get dragged into these
discussions...

Weng - what you're completely missing what many have been telling you -
your definition of a "state machine" is so broad that it's essentially
meaningless. Since you think that YOUR definition of a "state machine"
includes this 6M L2 cache, then as Ken and I have tried to tell you,
your "state machine" definition includes the subset of ALL synchronous
machines.

This isn't a terrible definition of a state machine, (but one that
doesn't offer much utility). But this just goes to show you that any
Super Snazzy Ideas you've got have already been shown in prior art, in
the general set of all synchronous machines, as Ken's trying to
communicate to you.

I fear you'll ignore this information as you've ignored most of what
information others have tried to communicate to your in the past (in
this thread and others). But I'm saying it anyway.

I'll await your reply with more sets of patent result hits from
google... <- Sarcasm

Regards,

Mark

 

[gtwrek]

In article <q15k3l$g4j$1@dont-email.me>, gtwrek <gtwrek@sonic.net> wrote:
> Many attributions to "Ken" that should have attributed "Kevin"

Sorry Kevin for the misattribution...

Regards,

Mark

 

[Weng Tianxiang]

Hi Mark,

Here is the definition of a state machine introduced in my prior art part:

[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

Weng

 

[gtwrek]

In article <5a65def4-8b0c-49f6-9642-15f52606832a@googlegroups.com>,
Weng Tianxiang <wtxwtx@gmail.com> wrote:

Hi Mark,

Here is the definition of a state machine introduced in my prior art part:

[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite
set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q
is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

This definition matches all synchronous digital circuits.

Regards,

Mark

 

On Tuesday, January 8, 2019 at 4:47:13 PM UTC-5, Weng Tianxiang wrote:

On Tuesday, January 8, 2019 at 12:26:39 PM UTC-8, gtwrek wrote:
In article <dd5eaff5-f99d-48f3-99bc-10dfda031747@googlegroups.com>,
Weng Tianxiang <wtxwtx@gmail.com> wrote:
If 2 state machines as you suggested may be active on the same clock, how do you handle it using your scheme?

Weng - I find your obsession with "state machines" a bit puzzling. I
seem to recall an poster a few years ago asking about the "largest"
state machine in current designs - was this you? It seems likely, in
the event that you consider a CPU cache as a large number (~100,000)
of state machines running in parallel.

I've not designed a CPU cache. But I can pretty much guarantee that
whomever designed that CPU cache you're thinking about did NOT model
the design as such (a lot of state machines running in parallel). To
be frank, I can see the entire design being done without implementing
a "state machine" at all.

A state machine is simply a model to make it easier for humans to
understand and design a circuit. It's not neccesary at all to apply
this model to any or all digital circuits.

One of my co-workers (for whatever reason) abhors "State machine"
design, and won't use them - at all. That's fine, he models things
differently. And he's a very productive engineer - not hindered one bit
by his lack of use of "state machines".

Conversely, one can model an entire ASIC (or FPGA) design as simply
one large state machine. Or many smaller state machines running in
parallel. (Assume a single clock for this analogy). It's just that a
model to aid our (the designers) view of a design.

Take a full schematic of any full ASIC. Draw a random blob around ANY
set of 4-5 FFs. Include some parts of the fanin and fanout logic
of those flip flops. Bam - there's a state machine. Repeat 20,000
times for all FF's in the design. Is this useful - not really - but it
will meet any definition of "State Machine" that you can define.

Regard,

Mark

Hi Mark,

You really has good memory!!!

I posted a post with title: "What is largest number of state machines in a chip" at this FPGA group several years ago.

Here are tons of state machine patents about how to design a L2 cache. I list only the search word "L2 cache inassignee:intel" and you can find through Google there are 4,830 patents filed and issued by Intel, the search word "L2 cache state machine inassignee:intel" and it leads to 4,360, each of them is related to a type of state machines.

I believe that anyone cannot be accounted as a professional digital circuit designer if he does not seriously consider or design a state machine.

One of my hobbies is to look at patents filed by Intel, IBM, AMD, Xilinx and Altera. Reading Xilinx and Altera' patents gives me the knowledge on how they design their FPGA chips. Reading Intel, IBM and AMD' patents gives me the knowledge on how they design something very complex and new technology trend. And through the reading I find many topics for me to further develop.

I disagree with your following opinion:
"I've not designed a CPU cache. But I can pretty much guarantee that
whomever designed that CPU cache you're thinking about did NOT model
the design as such (a lot of state machines running in parallel). To
be frank, I can see the entire design being done without implementing
a "state machine" at all. "

Here is an Intel patent: US8493397B1: "Circuit for placing a cache memory into low power mode in response to special bus cycles executed on the bus"

https://patents.google.com/patent/US8493397?oq=L2+cache+state+machine

https://patents.google.com/patent/US20140156931?oq=L2+cache+state+machine

I agree with your following opinion:
"a lot of state machines running in parallel".

After my invention all state machine design will be benefited to be in lower power status, no matter what type of state machines is, and the logic resource usage is less than a conventional synthesizer would generate.

Rick,
I disagree with your opinion:
"elsif WState /= WState_NS then

This is not so trivial compared to the FSM itself, especially in an ASIC. I would estimate it is approximately the same amount of logic in general. "

In my invention there is no one single logic gate generated for comparison "WState /= WState_NS". Is it obvious to you?

That is the best point of my invention.

If you can perform an equality comparison without using gates, that will be of tremendous value in logic design. Instead of using conventional gates all logic can be decomposed to an expression using equality comparisons (the equivalent of the XOR applied to bits followed by an OR gate). So if you can perform the not equal comparison on a multi-bit word without gates, then every digital logic design can be implemented with no logic gates at all!

By all means patent that and the world will beat a path to your door!!!

But obviously what you said is not true. So I must be misunderstanding you..

Perhaps you can explain what you really mean.

Rick C.

-+ Get 6 months of free supercharging
-+ Tesla referral code - https://ts.la/richard11209

 

[Weng Tianxiang]

Hi Mark,

"This definition matches all synchronous digital circuits."

Do you plan to retrieve the following claiming?

"Weng - what you're completely missing what many have been telling you -
your definition of a "state machine" is so broad that it's essentially
meaningless."

I really don't understand what you are saying.

Weng

 

[Weng Tianxiang]

Hi Rick,

First of all, I have to appreciate your following guessing:
"If you can perform an equality comparison without using gates, that will be of tremendous value in logic design. Instead of using conventional gates all logic can be decomposed to an expression using equality comparisons (the equivalent of the XOR applied to bits followed by an OR gate). So if you can perform the not equal comparison on a multi-bit word without gates, then every digital logic design can be implemented with no logic gates at all! "

But You are wrong in guessing my invention without any logic bases.

1. There is no comparison at all.

2. I use another trick to avoid any comparison for a state machine circuit and reach a conclusion that you need comparison to achieve.

3. The trick seems to be non-obvious to you now.

But don't worry, your conclusion is wrong too:
"obviously what you said is not true. So I must be misunderstanding you."

Weng

 

[gtwrek]

In article <767950fd-cde7-4840-97d1-72013316e77a@googlegroups.com>,
Weng Tianxiang <wtxwtx@gmail.com> wrote:

Hi Mark,

"This definition matches all synchronous digital circuits."

Do you plan to retrieve the following claiming?

"Weng - what you're completely missing what many have been telling you -
your definition of a "state machine" is so broad that it's essentially
meaningless."

Do you mean will I retract my statement? No I won't because it's
consistent. The definition you listed in the grandparent post of a "state
machine" has such a broad scope that EVERY synchronous digital circuit
in existance fits the definition.

You can prove me wrong by counter-example. I assert that your
definition of "state machine" is so broad that any synchronous digital
circuit will match your definition. If you can show/explain ANY
synchronous digital circuit that does NOT match your definition of a
"state machine" you'll have falsified my assertion.

I can come at it from the opposite end and suggest a few example of
synchronous digital circuits that one normally wouldn't think of as
"state machines" but fit your definition none-the-less.

But I think the excercise (of trying to come up with a counter-example)
would help you understand what we've been trying to communicate to you.

Regards,

Mark

 

[KJ]

On Wednesday, January 9, 2019 at 6:23:44 PM UTC-5, Weng Tianxiang wrote:

But You are wrong in guessing my invention without any logic bases.

Perhaps Rick is wrong as you state (or maybe not), but I am not. You have disclosed enough to discern what you think is the important idea to patent (although I don't pretend to know all that you may claim from that idea). Since you cannot disclose until you hear about publication, I won't disclose either.

1. There is no comparison at all.

2. I use another trick to avoid any comparison for a state machine circuit and reach a conclusion that you need comparison to achieve.

3. The trick seems to be non-obvious to you now.

But in fact the 'trick' as you call it is obvious and also, unfortunately for you, the idea is in fact old prior art that you are simply not recognizing. But maybe the PTO won't pick up on it, or maybe you'll find someone to part with $$ for what you will be marketing as a 'new' idea or maybe, if the patent is granted, you'll get challenged in court and lose. Time, as they say, will tell.

Kevin Jennings

 

[Weng Tianxiang]

Kevin, Can you give me a link to the prior art idea?

 

[Thomas Stanka]

Am Mittwoch, 9. Januar 2019 23:07:47 UTC+1 schrieb gtwrek:

Weng Tianxiang <wtxwtx@gmail.com> wrote:
[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite
set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q
is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

This definition matches all synchronous digital circuits.

Yes, that's true. A FSM could be a dedicated statemachine written in one HDL module, but each counter is a simple FSM and each complete logic design can be seen as a statemachine.

Every part of a statemachine containing at least 2 states and 1 input and output is itself a statemachine and every combination of 2 statemachines is one statemachine. FSM is just a model to describe a digital circuit with at least one sequential element.

best regards Thomas

 

[Richard Damon]

On 1/10/19 5:25 AM, Thomas Stanka wrote:

Am Mittwoch, 9. Januar 2019 23:07:47 UTC+1 schrieb gtwrek:
Weng Tianxiang <wtxwtx@gmail.com> wrote:
[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite
set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q
is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

This definition matches all synchronous digital circuits.

Yes, that's true. A FSM could be a dedicated statemachine written in one HDL module, but each counter is a simple FSM and each complete logic design can be seen as a statemachine.

Every part of a statemachine containing at least 2 states and 1 input and output is itself a statemachine and every combination of 2 statemachines is one statemachine. FSM is just a model to describe a digital circuit with at least one sequential element.

best regards Thomas

Perhaps some would call ANY synchronous digital circuit a state-machine,
but the more classical definition would imply that it be a system with a
single clock domain as it is the transformation from one 'State' to
another 'State' on *The* clock edge, with the definition of the Next
State being a function of the Previous State and the Inputs. The concept
of previous and next imply a singular concept of time steps, thus a
single clock domain (though clock gating/enables of that domain would be
allowed).

A system using multiple, not tightly related clocks, would fail that
definition, and in the FSM view of the world would be multiple
intertwined State Machines. Most digital system can be viewed as a set
of coupled FSMs based on the number of clock domains in the system.
Poly-Phase systems and system using wave phasing (multiple clocks
between registers) stretch the concept of a State Machine a bit, but can
probably be reasonably described as such. Some systems with Asynchronous
bits can get harder to describe as a FSM.

 

[gtwrek]

In article <ugHZD.8990$nO2.5464@fx08.iad>,
Richard Damon <Richard@Damon-Family.org> wrote:

On 1/10/19 5:25 AM, Thomas Stanka wrote:
Am Mittwoch, 9. Januar 2019 23:07:47 UTC+1 schrieb gtwrek:
Weng Tianxiang <wtxwtx@gmail.com> wrote:
[0003] Traditionally a deterministic finite state machine is mathematically defined as a set of 6-tuple M = (Σ, Δ, Q, q0, δ, λ), where Σ is a finite
set of input symbols, Δ /= 0 is a finite set of output symbols, Q /= 0 is a finite set of states, q0 є Q is the “reset” state, δ(q, a) : Q x Σ → Q
is the transfer function, and λ(q, a) : Q x Σ → Δ is the output function.
[0004] Conventional state machine theory has following State Machine Axiom:
[0005] State Machine Axiom A state machine has one and only one state being active on any cycle after the state machine is properly initialized.

This definition matches all synchronous digital circuits.

Yes, that's true. A FSM could be a dedicated statemachine written in one HDL module, but each counter is a simple FSM and each complete logic design can
be seen as a statemachine.

Every part of a statemachine containing at least 2 states and 1 input and output is itself a statemachine and every combination of 2 statemachines is one
statemachine. FSM is just a model to describe a digital circuit with at least one sequential element.

best regards Thomas


Perhaps some would call ANY synchronous digital circuit a state-machine,
but the more classical definition would imply that it be a system with a
single clock domain as it is the transformation from one 'State' to
another 'State' on *The* clock edge, with the definition of the Next
State being a function of the Previous State and the Inputs. The concept
of previous and next imply a singular concept of time steps, thus a
single clock domain (though clock gating/enables of that domain would be
allowed).

Yes, exactly. The qualification of a single clock - or as you note -
related clocks is what I was trying to cover with the term SYNCHNRONOUS
digitial circuits. In one of my post up the thread I mentioned a
single clock - Kevin more correctly labeled the requirements as
SYNCHRONOUS which I think summarizes the requirements better so I took
that label.

I'll say again, any SYNCHRONOUS digital circuit meets Weng's definition
of a state machine.

Regards,

Mark

 

[KJ]

On Wednesday, January 9, 2019 at 10:26:39 PM UTC-5, Weng Tianxiang wrote:

Kevin, Can you give me a link to the prior art idea?
Sorry, I'm not going to prior art research for your patent application for you.

However, I will suggest that you tend to take a very narrow view of some topic, such as a state machine, and appear to ignore applicable work that is more general, of which your 'state machine' is simply a subset.

Kevin Jennings

 

So much wrong.

Any marginally competent cache designer understands that only one cache line is accessed at a time. So the cache is designed as a RAM with data, tags, and state. Each cycle the data, tags and state are read, and a single state machine is used to generate the next state, which is written back into the RAM.

There are plenty of papers on flip flop design that detects whether the new data is different from the present state, and uses that to generate a clock pulse only if necessary.

On Tuesday, January 8, 2019 at 6:12:43 PM UTC-5, Weng Tianxiang wrote:

Hi Mark,

"I assert (without eny evidence whatsoever) that whomever designed that CPU
cache memory at Intel did NOT model it (in his head or otherwise) as
100,000 or more state machines running in parallel. That's just crazy. "

Here are the facts, you are welcome and no matter whether you agree or not:
1. 6M L2 cache, the largest L2 cache I can search for with a commercial CPU;

2. Every 64 bytes in L2 cache constitute a cache line;

3. Each L2 cache line works independently;

4. Each L2 cache line has at least one state machine to control its data or instructions in coherence. I will not be surprised that each L2 cache line may have up to 8 state machines to control its working.

4. Each L2 cache line has at least one state machine to control its data or instructions in coherence. I will not be surprised that each L2 cache line may have up to 8 state machines to control its working.

4. Each L2 cache line has at least one state machine to control its data or instructions in coherence. I will not be surprised that each L2 cache line may have up to 8 state machines to control its working.

4. Each L2 cache line has at least one state machine to control its data or instructions in coherence. I will not be surprised that each L2 cache line may have up to 8 state machines to control its working.

4. Each L2 cache line has at least one state machine to control its data or instructions in coherence. I will not be surprised that each L2 cache line may have up to 8 state machines to control its working.


1. IBM: Cache-coherency protocol with upstream undefined state
https://patents.google.com/patent/US6374330

2. IBM: Cache-coherency protocol with recently read state for data and instructions
https://patents.google.com/patent/US5996049

3. NVidia: State machine control for a pipelined L2 cache to implement memory transfers for a video processor. https://patents.google.com/patent/US8493397

Thank you.

Weng

 

On Wednesday, January 9, 2019 at 6:23:44 PM UTC-5, Weng Tianxiang wrote:

Hi Rick,

First of all, I have to appreciate your following guessing:
"If you can perform an equality comparison without using gates, that will be of tremendous value in logic design. Instead of using conventional gates all logic can be decomposed to an expression using equality comparisons (the equivalent of the XOR applied to bits followed by an OR gate). So if you can perform the not equal comparison on a multi-bit word without gates, then every digital logic design can be implemented with no logic gates at all! "

But You are wrong in guessing my invention without any logic bases.

1. There is no comparison at all.

2. I use another trick to avoid any comparison for a state machine circuit and reach a conclusion that you need comparison to achieve.

3. The trick seems to be non-obvious to you now.

But don't worry, your conclusion is wrong too:
"obviously what you said is not true. So I must be misunderstanding you."

Ok, I am reading your code. So you are saying your code is not what you mean. Got it.


Rick C.

++ Get 6 months of free supercharging
++ Tesla referral code - https://ts.la/richard11209

 

[Weng Tianxiang]

On Thursday, January 10, 2019 at 2:02:22 PM UTC-8, dlhe...@gmail.com wrote:

So much wrong.

Any marginally competent cache designer understands that only one cache line is accessed at a time. So the cache is designed as a RAM with data, tags, and state. Each cycle the data, tags and state are read, and a single state machine is used to generate the next state, which is written back into the RAM.

There are plenty of papers on flip flop design that detects whether the new data is different from the present state, and uses that to generate a clock pulse only if necessary.

Congratulation!

Your post is the best and most valuable post in this thread!

Invincible! Marvelous! Smartest!

Your post makes me shameful and speechless!

Hope you join my later post.

I will continue to pursue my next sets of inventions!

Thank you.

Weng