How Many Blocks Do You Use When Designing a FSM?

[tggzzz]

I was taught that the unary minus in -3 simply meant 0-3.

Yeah, that was the unconvincing "explanation" I suffered too.

It convinced me as much as the explanation that wings generate lift because a glob air has to travel further over the top surface in order to meet up with the corresponding glob that goes under the wing. No, the globs don't meet up and that isn't how lift is generated!

I wonder if the "high neg" evolved from signed-magnitude notation where the most significant bit is the sign and all other bits represented a positive value. -7 => b'1111 and +7 => b'0111.  This was a popular encoding in the early days of computers.  It eventually lost out to 1's and 2's complement.

APL started as a mathematical notation, and only mutated into a programming language a few years later. When it did, not all computers were twos complement; some were ones complement.

But to turn back towards the original thread, APL is a good illustration that brevity can be taken too far. Sometimes more is better; it is all a matter of good taste.

[SiliconWizard]

Let's try to stay on topic... but as the "coding effort" was one of the criterions mentioned in the linked article, a few points come to mind.

- "Coding effort" is a very vague term. What would be seen as more "effort" to someone may look like the same, or even less "effort" to someone else.
- When people try to quantify it, a few metrics pop up. The number of LOCs is commonly used, even though it's obviously flawed on several levels. Usually LOCs are counted excluding comments and blank lines. But is that really related to the "coding effort"? Not really. Expressing the same functionality with fewer LOCs can actually take much more effort.
- As has been said here, and that I often say as well, when writing in any language, readability is key. If better readability means more LOCs, so be it; you're not likely to get anything better (fewer bugs for instance) by making your code less readable.
- When comparing languages and/or coding styles, "verbosity" is often a key marker. But that has to be clearly understood, and clearly defined. Some languages are inherently more "verbose" than others (such as VHDL is more "verbose"  than Verilog), so a similar implementation will take more "code", but is this extra code a source of bugs? I don't buy it whatsoever. So that's another way considering LOCs and verbosity in particular is completely flawed. Considering verbosity, the extra "coding effort" is merely some typing effort, and of course, aiming for the shortest code possible can lead to absurd, unreadable and completely unmaintainable code.
- Linking the average number of "bugs" to the number of LOCs is also a common metric. Whereas it's flawed, it kind of becomes statistically significant in a given team using given tools if the number of LOCs is large enough. It's hard or impossible to transpose it to other teams, and if the number of LOCs is small, it usually doesn't make any sense anyway.
- Back to HDLs: a typical HDL project is usually much smaller than a typical software project, so definitely the number of LOCs can't be used statistically to infer the potential number of bugs IMO, even in a given team using given tools.
- Considering the coding effort, the number of "statements" is a slightly better metric than the number of LOCs. But it's still flawed. The basic idea is that if you need to write more statements to implement a given design, there are just more opportunities to introduce bugs. Statements itself is a vague metric. To make sense, we should consider statements that actually have an effect. But even so, sometimes implementing a given feature in fewer statements is much harder, and thus is more likely to introduce bugs than merely splitting the implementation over several statements, even if it's more code. And of course, as already said, if it helps readability, it's also likely to help limit the number of bugs.
- One factor that makes code harder to write correctly and maintain is splitting implementation in too many places that have dependencies between themselves. Back to HDLs and FSMs, splitting a given FSM into several processes (depending of course on the structure and FSM itself) can fall into this category, in which case, even though it may lead to fewer LOCs (or better, statements), is much harder to get correct and even harder to maintain.

[tggzzz]

Let's try to stay on topic... but as the "coding effort" was one of the criterions mentioned in the linked article, a few points come to mind.

- "Coding effort" is a very vague term. What would be seen as more "effort" to someone may look like the same, or even less "effort" to someone else.
- When people try to quantify it, a few metrics pop up. The number of LOCs is commonly used, even though it's obviously flawed on several levels. Usually LOCs are counted excluding comments and blank lines. But is that really related to the "coding effort"? Not really. Expressing the same functionality with fewer LOCs can actually take much more effort.

Precisely. I often know I am succeeding when the number of lines of my code is reducing. If any managers were stupid enough to have a LOC/day or more LOC==more complete metric, then they would be having kittens.

- As has been said here, and that I often say as well, when writing in any language, readability is key. If better readability means more LOCs, so be it; you're not likely to get anything better (fewer bugs for instance) by making your code less readable.
- When comparing languages and/or coding styles, "verbosity" is often a key marker. But that has to be clearly understood, and clearly defined. Some languages are inherently more "verbose" than others (such as VHDL is more "verbose"  than Verilog), so a similar implementation will take more "code", but is this extra code a source of bugs? I don't buy it whatsoever. So that's another way considering LOCs and verbosity in particular is completely flawed. Considering verbosity, the extra "coding effort" is merely some typing effort, and of course, aiming for the shortest code possible can lead to absurd, unreadable and completely unmaintainable code.

Precisely. Frequently more typing means static errors are discovered earlier, thus reducing the overall project duration.

As for typing effort, in a decent language plus IDE plus design patterns, autocompletion removes a lot of the keyboard bashing. That's possible because the "extra" typing elsewhere has reduced the number of possibly valid options at this point in the code - and that means fewer static errors.

- One factor that makes code harder to write correctly and maintain is splitting implementation in too many places that have dependencies between themselves. Back to HDLs and FSMs, splitting a given FSM into several processes (depending of course on the structure and FSM itself) can fall into this category, in which case, even though it may lead to fewer LOCs (or better, statements), is much harder to get correct and even harder to maintain.

Tastefully splitting a single FSM into multiple cooperating FSMs is likely to be more effective at reducing bugs than fiddling with two processes vs three processes, or fiddling with the numbers of lines of code.

Tasteful use of appropriate design patterns may (or may not) increase the number of lines of code, but should increase the clarity of the implementation.

[Sal Ammoniac]

Tasteful use of appropriate design patterns may (or may not) increase the number of lines of code, but should increase the clarity of the implementation.

As long as you don't go overboard and start creating things like SimpleBeanFactoryAwareAspectInstanceFactory and AbstractInterceptorDrivenBeanDefinitionDecorator.

[tggzzz]

Tasteful use of appropriate design patterns may (or may not) increase the number of lines of code, but should increase the clarity of the implementation.

As long as you don't go overboard and start creating things like SimpleBeanFactoryAwareAspectInstanceFactory and AbstractInterceptorDrivenBeanDefinitionDecorator.

Without context I can't tell whether those display good taste or bad taste

Typing them will be relatively painless, using ctrl-space or whatever the IDE uses for autocompletion (I conjecture without evidence that VHDL might be better than Verilog in that respect).

They occupy a lot of horizontal space, maybe 20% of my window's width. Just as well we have more than 80*24 screens now Modules/namespaces help a lot too.

[0db]

back to fsm: anyone does how how SCALA implement fsm? with one block? two blocks? three blocks? with one block + variables?

[Bassman59]

Typing them will be relatively painless, using ctrl-space or whatever the IDE uses for autocompletion (I conjecture without evidence that VHDL might be better than Verilog in that respect).

emacs vhdl-mode: tab autocompletes. And it auto-completes and generates templates, too!

[Bassman59]

back to fsm: anyone does how how SCALA implement fsm? with one block? two blocks? three blocks? with one block + variables?

Nobody uses SCALA

[SiliconWizard]

back to fsm: anyone does how how SCALA implement fsm? with one block? two blocks? three blocks? with one block + variables?

Nobody uses SCALA

I suppose he's talking about Chisel, which is based on Scala? It would probably take someone who knows Chisel very well to answer this question.
(So, that's not quite nobody, but still a niche.)

[0db]

I suppose he's talking about Chisel, which is based on Scala?

Yup. Precisely. Chisel/Scala implements fsm-s in the same way the C language implements arrays in assembly. But I wonder how?!?

[NorthGuy]

I don't think the two-block habit comes from ancient languages. It comes from the theory. FSM is two transforms:

Code: [Select]

(inputs,state) -> state
state -> output
Hence, the straightforward implementation uses two processes. The first one is clocked to calculate the next state, and the second one is typically combinatorial to calculate the output.

From the programming viewpoint, it's certainly easier to use one process because everything is in one place. If you used two processes, they often would have similar "ifs" and "cases". You're certainly better off if you have only one copy of each of these.

From the design viewpoint, it doesn't matter if you used one process or two. The result is likely to be identical.

[ejeffrey]

I don't think the two-block habit comes from ancient languages. It comes from the theory. FSM is two transforms:

Code: [Select]

(inputs,state) -> state
state -> output
Hence, the straightforward implementation uses two processes. The first one is clocked to calculate the next state, and the second one is typically combinatorial to calculate the output.

From the programming viewpoint, it's certainly easier to use one process because everything is in one place. If you used two processes, they often would have similar "ifs" and "cases". You're certainly better off if you have only one copy of each of these.

From the design viewpoint, it doesn't matter if you used one process or two. The result is likely to be identical.

I don't think that is the way the OP was discussing using a two process block.  The canonical "two-process" FSM that I have seen has a combinatorial process to calculate the next state and a clocked process to actually assign "state <= next"  and to handle reset.  If the output is non-trivial and placed in its own process then that would be a 3 process FSM.

You could certainly write a 2 process FSM that uses a single sequential process for the state logic and a separate combinatoric one for output assignment, but I don't think that is what most people above were talking about.

[rstofer]

From the design viewpoint, it doesn't matter if you used one process or two. The result is likely to be identical.

 

It seems to me, when it comes to providing signals to logic outside the FSM, there is a one clock delay in the clocked-only design because of the Moore model (the outputs, in this case, are registered).  The Moore model produces less glitches (if they matter) but there is a delay (latency).  Pipelines fit in here somewhere...

There is a book, "Finite State Machines in Hardware - Theory and Design (with VHDL and SystemVerilog)" by Volnei A. Pedroni that spends 300+ pages on this stuff.   The author breaks FSMs into 3 categories 1) Regular State Machines, 2) Timed State Machines and 3) Recursive State Machines (having code like y=y+1 where y has to be stored somewhere) along with Mealy and Moore implementations of each in both VHDL and SystemVerilog (which looks more like VHDL than Verilog).

I haven't finished the book but it's a pretty good read.  It covers things I hadn't thought about and points out where my use of Karnaugh maps has been deficient when thinking in terms of glitch free transitions.  Minimal logic isn't always the goal!  I have to believe I used to know this stuff but it's been a long time since I was in school.

I really wanted an introduction to SystemVerilog and since all of the complexity in my projects revolves around FSMs, this seemed like a targeted approach.

https://www.amazon.com/gp/product/0262019663

[rstofer]

You could certainly write a 2 process FSM that uses a single sequential process for the state logic and a separate combinatoric one for output assignment, but I don't think that is what most people above were talking about.

Alas, that is exactly what I was describing:  One clocked process to deal with reset and setting state <= next_state along with a much larger combinational process to generate next_state and all of the FSM outputs.  Definitely a Mealy machine.

The one trap for young players is that every output of an FSM must be defined at every instant in time.  This leads to setting default output values for every output  at the top of the combinational process.  This sometimes gets overlooked when adding additional outputs later on.  It turns out that most trivial textbook examples don't do this, they just specify every output in every state and conditional.  Sometimes textbook examples are misleading!

[Bassman59]

From the design viewpoint, it doesn't matter if you used one process or two. The result is likely to be identical.

 

It seems to me, when it comes to providing signals to logic outside the FSM, there is a one clock delay in the clocked-only design because of the Moore model (the outputs, in this case, are registered).  The Moore model produces less glitches (if they matter) but there is a delay (latency).  Pipelines fit in here somewhere...

And the glitching is the reason why the state machine outputs are registered.

In the two-process model, you have a combinatorial process assigning all outputs and the next state as well as a synchronous process registering the next-state as well as possibly registering the outputs. If you don't have the registered outputs, you stand a good chance of glitching because of all of the decoding paths.

So if you are going to register the state register -- which you have to do, anyway -- and you're going to register the machine outputs, then why not combine that all into one synchronous process?

There is an argument mentioned in this thread and elsewhere that goes, "well, I have a signal foo and if I assign it in state S_FOO, then with a synchronous process then foo looks like it changes in the next state S_BAR! AND I DON'T LIKE THAT!" That's a pretty silly argument,

There is a book, "Finite State Machines in Hardware - Theory and Design (with VHDL and SystemVerilog)" by Volnei A. Pedroni that spends 300+ pages on this stuff.   The author breaks FSMs into 3 categories 1) Regular State Machines, 2) Timed State Machines and 3) Recursive State Machines (having code like y=y+1 where y has to be stored somewhere) along with Mealy and Moore implementations of each in both VHDL and SystemVerilog (which looks more like VHDL than Verilog).

My reason for calling the discussion about Mealy-vs-Moore-vs-Whatever state machines "academic" is because when you design your logic, you might combine all of the elements of those types and your result is a mix. And really, to reiterate again, what matters is the actual functionality of the logic, not whether the code fits into some predefined pigeonhole.

[Sal Ammoniac]

I haven't finished the book but it's a pretty good read.

I've had that book on my Amazon shopping list for a while now and based on your comments will get and read it.

I really wanted an introduction to SystemVerilog and since all of the complexity in my projects revolves around FSMs, this seemed like a targeted approach.

My go-to book for SystemVerilog is this one. It's not specific to FSMs, but covers all the basics with an emphasis on synthesizable RTL.

https://www.amazon.com/RTL-Modeling-SystemVerilog-Simulation-Synthesis/dp/1546776346/

[rstofer]

My go-to book for SystemVerilog is this one. It's not specific to FSMs, but covers all the basics with an emphasis on synthesizable RTL.

https://www.amazon.com/RTL-Modeling-SystemVerilog-Simulation-Synthesis/dp/1546776346/

Well that was expensive!  Education has never been free.

Basically, my interests are really on synthesizable RTL.  I don't spend a lot of time with simulation even though I'm trying to learn more about it.

[Someone]

New answer:
less than 1 block

Writing out a dense module today that the tools decided was best implemented in 2 state machines (all 3 majors, but they didn't agree on the encoding), despite their only being one block. Resource usage was around where a hand made implementation would reach and it tests out ok in simulation and hardware. So another win for using high level languages as high level languages.

[SiliconWizard]

I suppose he's talking about Chisel, which is based on Scala?

Yup. Precisely. Chisel/Scala implements fsm-s in the same way the C language implements arrays in assembly. But I wonder how?!?

Doesn't look like anyone here really uses Chisel. If you're interested in it, you should probably download the tools, learn how to use them, then implement a few FSMs in Chisel, get them translated to Verilog by the tools and see for yourself. As with many code generation tools, I would expect somewhat difficult to read output, and possibly a lot of separate processes instead of just one or two. But really, you should try it.

[SiliconWizard]

I don't think the two-block habit comes from ancient languages. It comes from the theory. FSM is two transforms:

Code: [Select]

(inputs,state) -> state
state -> output
Hence, the straightforward implementation uses two processes. The first one is clocked to calculate the next state, and the second one is typically combinatorial to calculate the output.

Yes, it's very likely where that originally comes from, and it's a pretty common approach in education. It's much easier to get students to understand the theory. A single, or more than 2 process-approach would probably look pretty confusing to most people learning FSMs, at least if you want to teach them the theory, and not just a bunch of recipes.

From the programming viewpoint, it's certainly easier to use one process because everything is in one place. If you used two processes, they often would have similar "ifs" and "cases". You're certainly better off if you have only one copy of each of these.

Yeah that's my view as well. Of course that depends on how exactly you implement your FSMs. But if you use a two-process approach, and you need to modify both processes (which is often the case) if you later add a state, or modify one, then that's two places to maintain instead of just one, and thus a potential aggravated risk of introducing bugs. OTOH, of course if your FSM becomes very large, splitting it in several parts will make it easier to maintain too - but then, the best way is not necessarily to use the "textbook" two-process way.

As someone already said (I think), if you have several clocked processes on the same clock, you can always combine all of them in a single process - that will do the exact same. Likewise, you can split a big clocked process into several ones. It's all in readability and how you structure your code.

[Sal Ammoniac]

There is a book, "Finite State Machines in Hardware - Theory and Design (with VHDL and SystemVerilog)" by Volnei A. Pedroni that spends 300+ pages on this stuff.   The author breaks FSMs into 3 categories 1) Regular State Machines, 2) Timed State Machines and 3) Recursive State Machines (having code like y=y+1 where y has to be stored somewhere) along with Mealy and Moore implementations of each in both VHDL and SystemVerilog (which looks more like VHDL than Verilog).

My copy of this book arrived and I spent the day yesterday reading it. It’s a very thorough introduction to FSMs and covers them in lots of detail. Recommend.

One caveat, however... In his SystemVerilog examples he uses non-blocking assignments exclusively, even in purely combinational always_comb blocks. There’s not a blocking assignment to be seen anywhere.  This is not standard practice, which is to use non-blocking assignments in sequential always blocks, blocking assignments in combinational always blocks, and not to mix the two. At the very least, his SystemVerilog is going to have synthesis/simulation mismatches.

[SiliconWizard]

There is a book, "Finite State Machines in Hardware - Theory and Design (with VHDL and SystemVerilog)" by Volnei A. Pedroni that spends 300+ pages on this stuff.   The author breaks FSMs into 3 categories 1) Regular State Machines, 2) Timed State Machines and 3) Recursive State Machines (having code like y=y+1 where y has to be stored somewhere) along with Mealy and Moore implementations of each in both VHDL and SystemVerilog (which looks more like VHDL than Verilog).

One caveat, however... In his SystemVerilog examples he uses non-blocking assignments exclusively, even in purely combinational always_comb blocks. There’s not a blocking assignment to be seen anywhere.  This is not standard practice, which is to use non-blocking assignments in sequential always blocks, blocking assignments in combinational always blocks, and not to mix the two. At the very least, his SystemVerilog is going to have synthesis/simulation mismatches.

That doesn't look too good.

[Sal Ammoniac]

There is a book, "Finite State Machines in Hardware - Theory and Design (with VHDL and SystemVerilog)" by Volnei A. Pedroni that spends 300+ pages on this stuff.   The author breaks FSMs into 3 categories 1) Regular State Machines, 2) Timed State Machines and 3) Recursive State Machines (having code like y=y+1 where y has to be stored somewhere) along with Mealy and Moore implementations of each in both VHDL and SystemVerilog (which looks more like VHDL than Verilog).

One caveat, however... In his SystemVerilog examples he uses non-blocking assignments exclusively, even in purely combinational always_comb blocks. There’s not a blocking assignment to be seen anywhere.  This is not standard practice, which is to use non-blocking assignments in sequential always blocks, blocking assignments in combinational always blocks, and not to mix the two. At the very least, his SystemVerilog is going to have synthesis/simulation mismatches.

That doesn't look too good.

No, it doesn’t. Pedroni is known for his VHDL books, so perhaps he isn’t familiar enough with SystemVerilog to understand the implications, or perhaps he had a grad student do the translation.

On the plus side, this book is published by MIT Press, so it’s tightly edited and I found no typos or misspellings. This is in extreme contrast to Stu Sutherland’s SystemVerilog book, which is self-published, and has hundreds of typos scattered throughout the book, sometimes several on a page.