Finite State Machines

[logictom]

I'm just doing some revision and have a question on FSM's.
I'm given the following diagram

The questions are:
1. Determine if the FSM is Mealy or Moore
2. Detect redundant states in the FSM
3. Eliminate redundant states and redraw.

My answers:
1. Mealy

2.

S3 and S4 are redundant

3.

Redrawn

Can anyone confirm if this is correct or not?
Last time I did this was about year and a half ago and I only have one example in my notes.
Thanks

[armandas]

1. Output depends on the state as well as input, so Mealy.
2. S3 and S4 are the same, but I'd say that only S4 is redundant and have to be removed. Why create a new state?
3. Looks right, but, as mentioned above, A may be left as S3.

[logictom]

I wasn't too sure about if needed to define as a new state or could just merge them.
Thanks for clearing that up

[logictom]

I've another question but this one you have to derive the FSM from some Verilog, I have very little experience with Verilog but think this is correct.

Code: [Select]

module fsm1 (y, clk, reset, e, r);

input clk, reset, e, r;
output y;
reg y;

parameter [3:0] A = 4'b0010,
B = 4'b0001,
C = 4'b1000,
D = 4'b0100;

reg [3:0] state, next;

always @ (posedge clk or posedge reset)
if(reset) state <= A;
else state <= next;

always @ (state or r or e) begin
if(!e) next=state; else
case (state)
A: if (r) next = D; else next = B;
B: if (r) next = A; else next = C;
C: if (r) next = B; else next = D;
D: if (r) next = C; else next = A;
default: next = A;
endcase
end

assign y <= state[0] | state[2];

endmodule

The FSM:


This FSM being a Moore machine Mealy machine because it has more than one output?
Is this correct?
Thanks again

[Mechatrommer]

may i know whats that XX/XXXX symbols stand for?

[logictom]

In the first diagram it's xx/yyyy where xx is the path taken when the input is xx and the yyyy is the ouput.

The second it x/yyyy where x is the State and yyyy is the output.

[armandas]

From lines

Code: [Select]

output y;
<...>
assign y <= state[0] | state[2];

I'd say the code represents a Moore machine. Number of outputs has nothing to do with the model.
The image seems right.. but I'm not good at reading Verilog.

[logictom]

From lines

Code: [Select]

output y;
<...>
assign y <= state[0] | state[2];

I'd say the code represents a Moore machine. Number of outputs has nothing to do with the model.
The image seems right.. but I'm not good at reading Verilog.

Yeah you're right, I originally thought Moore but then I confused myself thinking it was Mealy but looking over it again I've got it now

Not on subject but something else I'm revising can anyone point me to a good explanation with examples of binary decision diagrams and ROBDD's? (How to produce one when given a boolean expression)

Thanks again armandas

[A-sic Enginerd]

This looks like someone working on some homework. 

Anyway....that's a Moore output. Why? It's only dependent on the fsm being in a particular state. In this case, sure it can be in one of two states, but still it's based only on the state of the fsm. The inputs don't come into the equation.

Now, a couple bits of constructive criticism:
assign y <= blah;  // bad. Using non-blocking assignment with an assign statement. Don't do this. "IF" it simulates correctly, it may still give you issues at synthesis time.

Also, this is not the cleanest of ways to provide the output either. It will certainly work a lot of the time, but it is subject to generating a glitchy output during state transitions. So if the timing path starts hedging towards the critical edge of things, this could give you some headache. The better way to do it would be to generate the outputs directly from the fsm and as a registered output. An example of how I personally would code something like this:
(yes, I'm going to leave some stuff out and call this a code "snip-it", not the complete thing. Not to mention I've been coding in System Verilog for the past year which allows some terseness compared to Verilog)

reg y, next_y;

always @ (blah)
begin
   next_y = y;

   case (state)
      A:begin
            if (r)
            begin
                next_y = 1'b0;
                next    = D;
            end
            else
            begin
               next_y = 1'b1;
               next     = B;
            end
         end

      <B looks pretty similar>

      C: begin
            if (r)
            begin
                next_y = 1'b1;
                next    = B;
            end
            else
            begin
               next_y = 1'b0;
               next     = D;
            end
         end

      <rest of states, including default>
   endcase
end

always @ (posedge clk or negedge reset)
begin
   if (reset)
   begin
      state <= A;
      y      <= 1'b1;
   end
   else
   begin
      state <= next;
      y      <= next_y;
    end
end

Notice that the big difference is y is its own flop. If you get in this habit of creating all registered outputs, your own life will be just that much easier in the long run, not to mention anyone designing a block that might be using your output will thank you.

[djsb]

Hi,
I wish I understood this stuff. I'm still trying to find some educational material/tutorials. Anyone suggest anything?

David.

[logictom]

This looks like someone working on some homework. 

Anyway....that's a Moore output. Why? It's only dependent on the fsm being in a particular state. In this case, sure it can be in one of two states, but still it's based only on the state of the fsm. The inputs don't come into the equation.
---
Notice that the big difference is y is its own flop. If you get in this habit of creating all registered outputs, your own life will be just that much easier in the long run, not to mention anyone designing a block that might be using your output will thank you.

Thanks A-sic, not quite homework, revision for an exam this week, even more fun... the code was in a previous exam paper, not code written by me, I can work out what it means but fail miserably at writing it, I keep trying to write it like C The next question was actually to rewrite the assign <=y section so thanks for the input.

Are you after material on FSM's or Verilog David?

[A-sic Enginerd]

Hi,
I wish I understood this stuff. I'm still trying to find some educational material/tutorials. Anyone suggest anything?

David.

Like logictom said - it depends on what you're after.
If you're looking for stuff on digital design and FSMs -I'd recommend Wakerly. I went through school with what I believe was the second edition (it's at home, I'm at work, so can't confirm that right this minute), but it was a very well written and easy to follow book. This is a book that covers the fundamentals and is meant for the beginner digital designer.

If you're looking more for how to code in an HDL (Verilog or VHDL), that's a different arena. I've looked at, and own a few different ones, mostly on Verilog, and none of them are all that great. Hard to read / not really all that well written and they pretty much all make heavy use of building a project as the book goes. So each chapter would draw on the previous. So that works fine if you're reading it cover to cover, but if you want / need more of a reference type material, forget it. And maybe that's why I haven't been that enthralled with them because I was fortunate enough to be in the right place at the right time and was taught Verilog as an advanced study class while in college, by a an engineer that was working for a top notch company and they were looking to grow and groom their own asic engineers. So all I've ever needed from a text was as a reference manual.

There are a couple of Verilog tutorial sites on the web that I've used that are not too bad for a reference, but I think they might be a bit tough to actually learn the language from raw.
One is this one: http://www.asic-world.com/

Also, check out websites from Stuart Sutherland and / or Cliff Cummings.
http://www.sutherland-hdl.com/ and http://www.sunburst-design.com/papers/ respectively. Their sites change regularly so sometimes there's useful info there, other times it's burried in the mud. These guys are the guys that wrote the book on Verilog......literally.

For VHDL......I just don't go there. During my 15 yrs of doing chip design, we always cringe when someone hands us a chunk of IP that's written in VHDL. Not because we can't use it, but because it's a PITA language and no one I know likes it. Verilog is to C, as VHDL would be to say......Turbo Pascal.

[jahonen]

For VHDL......I just don't go there. During my 15 yrs of doing chip design, we always cringe when someone hands us a chunk of IP that's written in VHDL. Not because we can't use it, but because it's a PITA language and no one I know likes it. Verilog is to C, as VHDL would be to say......Turbo Pascal.

Here in Finland, most designs are done with VHDL. I don't know any companies around here who have been using Verilog. I have personally done few FPGA designs, and I didn't find VHDL such painful (well, maybe sometimes to be honest). I know that it is picky language for many reasons. One VHDL feature (or ADA too) is strong typing. For example, std_logic_vector, signed and unsigned are different types (although actual underlying physical representation is exactly same) and can't be directly combined without explicitly describing how the combination should be made. Of course the design should be made so that each signal is represented with appropriate data type, so there would be no need for type conversions. Unfortunately people tend to be sloppy in this respect and so using implicit "C-type" conversions will seem so convenient. In C/Verilog you can always freely mix various data types and it "works", but I think not having implicit conversions prevents some stupid mistakes you can easily make.

As they say, C is the language for the people who like to debug.

Regards,
Janne

[A-sic Enginerd]

For VHDL......I just don't go there. During my 15 yrs of doing chip design, we always cringe when someone hands us a chunk of IP that's written in VHDL. Not because we can't use it, but because it's a PITA language and no one I know likes it. Verilog is to C, as VHDL would be to say......Turbo Pascal.

Here in Finland, most designs are done with VHDL. I don't know any companies around here who have been using Verilog. I have personally done few FPGA designs, and I didn't find VHDL such painful (well, maybe sometimes to be honest). I know that it is picky language for many reasons. One VHDL feature (or ADA too) is strong typing. For example, std_logic_vector, signed and unsigned are different types (although actual underlying physical representation is exactly same) and can't be directly combined without explicitly describing how the combination should be made. Of course the design should be made so that each signal is represented with appropriate data type, so there would be no need for type conversions. Unfortunately people tend to be sloppy in this respect and so using implicit "C-type" conversions will seem so convenient. In C/Verilog you can always freely mix various data types and it "works", but I think not having implicit conversions prevents some stupid mistakes you can easily make.

As they say, C is the language for the people who like to debug.

Regards,
Janne

Hehe....I was wondering if I was going to hear back on something like that. 

They each have their merits. The only comment I would make to your point - I will agree it is a valid one, within limits. If we're talking strictly a pure digital design, then the sorts of things you point out become moot. Why? Because the designer should be thinking down at the hardware level anyway, and even as you said it yourself "...actual underlying physical representation is exactly same.". However, when we start getting into the verification side of things and using the full breadth of a language, any language, then yeah.....that's a whole other ball of wax and the type of argument you bring to the table certainly has a great deal more merit.

As a side note: I learned that tidbit when I started my career that yeah, VHDL was the prominent language in Europe. Never understood that - why the difference? Why do some regions of the planet prefer one language and others go the other way? I think that's one for the philosophers to figure out.

[charliex]

I've heard that its because once , one was open and cheaper, one was spendy. and given the economic distance between the the USA and the ROW at the time, thats why. its plausible, but i don't know if thats why.

i've read countless times that X is dead , long live Y, but it rarely happens.

now its system verilog vs vhdl/verilog, it amazes me anyone gets the time to get anything done

[kc1980]

If you were a complete novice in the US, which of the three would you choose to learn?  VHDL, Verilog or SystemC.

[A-sic Enginerd]

If you were a complete novice in the US, which of the three would you choose to learn?  VHDL, Verilog or SystemC.

In the US - Verilog. Followed by System Verilog. SystemC is out there, but losing support from the EDA vendors. Hell, as it is, even though vendors claim support for System Verilog we're constantly finding bugs and holes in their support for it. It's not fully ready for prime time just yet. (sorry, for those in the know, don't confuse that statement with PrimeTime).

And actually, I do believe there is pretty wide and default support for Verilog 2001. Take a look at it. It has stuff in it to circumvent many of the pitfalls rookies (or even sometimes experienced designers) run into. Things like sensitivity lists on always blocks. Starting with 2001 they can be short cut with stuff like:
always @ (*)  // or something like that. It's kind of slipping away already after coding System Verilog for a year where sensitivity lists are basically gone all together.

[charliex]

If you were a complete novice in the US, which of the three would you choose to learn?  VHDL, Verilog or SystemC.

I found this guys tutorials pretty handy, http://www.asic-world.com/verilog/veritut.html but i'm a FPGA n00b so FWIW.

[jahonen]

They each have their merits. The only comment I would make to your point - I will agree it is a valid one, within limits. If we're talking strictly a pure digital design, then the sorts of things you point out become moot. Why? Because the designer should be thinking down at the hardware level anyway, and even as you said it yourself "...actual underlying physical representation is exactly same.". However, when we start getting into the verification side of things and using the full breadth of a language, any language, then yeah.....that's a whole other ball of wax and the type of argument you bring to the table certainly has a great deal more merit.

There are some cases where actual encoding is best left to compiler/synthesizer, like how Altera recommends doing state machine encodings on their FPGAs, where you shouldn't try to describe actual states but just what you need and leave rest to the design software. So it typically is something like this (in VHDL):

Code: [Select]

type STATES_T is (STATE_A, STATE_B, STATE_C);

-- and then

signal state : STATES_T := STATE_A;

-- finally

process(clk, reset)
begin
  if reset = '1' then
    state <= STATE_A;
  elsif rising_edge(clk) then
    case state is
      when STATE_A =>
        state <= STATE_B;
      when STATE_B =>
        state <= STATE_C;
      when STATE_C =>
        state <= STATE_A;
      when others => null;
    end case;
  end if;
end process;

It seems logical from the basis that probably the design software written by people who know the inner workings of their chips very intimately, know their stuff better than average designer. Trying to optimize FPGA designs using a Karnaugh map is usually a wasted time since smallest design unit in the typical FPGA can encode any combinatorial function up to 4 input variables. It takes same amount of building block space whether there are two or four input variables. Using the karnaugh map for more than 4 variables is quite difficult indeed.

But I guess that its a bit different when doing ASIC stuff, where you do everything from scratch (or almost), so you can benefit from even small reduction from logic functions.

Regards,
Janne

[A-sic Enginerd]

Hmmm...it's been a long time since I've written code to specifically target an FPGA, but I guess I could see a rationale for letting a vendors tools choose the encoding. Although, I'm not 100% sure I can truly appreciate the differences compared to the trade-offs seen in general of using BCD vs. grey vs. one hot. Many of our designs have been put to FPGA as a prototyping effort or to serve as a development platform for the FW and SW folks until real silicon arrives, but fsm encoding schemes has never even been an issue in discussions. The bigger issues are always about timing paths and clock speeds since an FPGA can't handle what actual Si does so we sometimes do some creative things (e.g.: staging flops on datapaths) to help with that. (Won't even get into the utilization issue and whether there's even an FPGA in existence big enough to contain the design).

And what's this karnaugh map thing you speak of? 

(Pretty sure I stopped doing those mid way through college. Now days the synthesis tools can pretty much always do a better job of optimization than even the most talented engineer can)

[jahonen]

I didn't mean that encoding would be a problem, but that nowadays you can leave many details (and often it would be best) to the synthesis to worry about and concentrate on the more higher-level aspect of the design. I think that is what you said too.

Regards,
Janne

[logictom]

I've had little experience with FPGA's and fancy having a tinker with one, are there any good cheap development boards?
What are the software options, the little I have used was with Xilinx ISE is this a standard tool or are there alternatives? Free or limited
Thanks

[jahonen]

I've had little experience with FPGA's and fancy having a tinker with one, are there any good cheap development boards?
What are the software options, the little I have used was with Xilinx ISE is this a standard tool or are there alternatives? Free or limited
Thanks

If you can work with Altera FPGA's, then you could use Quartus, which is similar to the Xilinx ISE (I keep hearing that Quartus is somewhat more user-friendly than ISE, but YMMV). That is free for smaller chips (pretty much everything but Stratix families). I don't think there is free/limited third-party design software for either Altera or Xilinx.

Regards,
Janne

[charliex]

ISE WebPack is free just limited, sparkfun, digilient, fpga4fun and gadget factory all have cheap fpga boards to work with.

I've yet to try a software tool i'd consider decent for FPGA's though, you get spoilt rotten with C/C++ etc IDE's.

[A-sic Enginerd]

ISE WebPack is free just limited, sparkfun, digilient, fpga4fun and gadget factory all have cheap fpga boards to work with.

I've yet to try a software tool i'd consider decent for FPGA's though, you get spoilt rotten with C/C++ etc IDE's.

Hehe, funny you mention this. The tools support for FPGA's has always been.....well.....crap. Even the ones you pay for at the commercial level are always one step behind the actual chip hardware and riddled with bugs and holes. Our teams have always had a person become the specialist to drive the tools of the day and what that really means is they spend their time finding the holes or bugs in the tools and how best to work around them. It's not terribly uncommon that we have to even go back into the RTL design and do a little massaging or workarounds to keep the FPGA tools happy.

And yes, software IDE's have always outclassed any form of hardware IDE's. Although, I've recently been getting some time with Synopsys DVE to be used with VCS. The back annotated debugging can be pretty nice. I know Verdi can do the same, but with System Verilog there have been a few things that one does better than the other and vice versa.