Build Instructions

Collapse

• 1

  ▇▇▇▇ A Simple State Machine ▇▇▇▇

  This diagram shows what could be one of the simplest state machines possible.

  It operates a hypothetical air machine at a gas station. You insert a quarter and the air compressor turns on for a fixed amount of time. When the timer runs out, the compressor goes off and they system waits for more money. 

  This is very simple, of course, but it illustrates a few things. The blue circles are states and the double circle indicates the state the system starts in. In some diagrams, you'll see an arrow coming from nowhere labeled reset or some other way of identifying the initial state.

  The lines are transitions. The labels on them should tell you why you'd move from one state to another and what outputs occur on those transitions. There's some variations possible on this and we'll talk about them later, but this is basically it.

  Coding this in Verilog would be pretty simple:

  `timescale 1s/100ms
  module airpressure(input clk, input reset, input coin, output compressor);
  
     reg state; // 1 = on, 0 = off
  
     reg gotcoin;
     reg [6:0] timer;
     localparam timerinit=60;  // must fit in timer!
     wire nextstate;
    
  // logic for output
     assign compressor=state;
  // logic for next state
     assign nextstate=state?timer!=0:gotcoin;
  
    // Manage state and timer (for simplicity,
    // assuming clock is every second and that's
    // sufficient for the coin slot
      always @(posedge clk)
  
        if (reset)  // initial conditions
            begin state<=0;
              gotcoin<=1'b0;
              timer<=0;
            end
  
         else
             begin
                 state<=nextstate;
                 if (nextstate) timer<=timerinit;
                 if (timer!=0) timer<=timer-1;
                 gotcoin<=coin;
            end
    
  endmodule

   Of course, you could argue that an SR flip flop could do the same job and you'd be right.  But this framework will allow us to build more complicated machines. For example, what if you wanted to change the price and allow more types of coins? Or let the user add coins to extend the time?

  Here's part of the simulation:

  Note that I made the simplifying assumption that the clock was one second and the coin acceptor would hold its output that long. In real life, you'd need to implement the timer differently, I'm sure.

  Don't forget you can run all of this yourself in EDA Playground. Consider changing the code to require two quarters instead of one. What would have to change?

• 2

  ▇▇▇▇ Adding Complexity ▇▇▇▇

  Instead of two quarters, suppose we just want to let the machine take nickles (5 cents), dimes (10 cents), and quarters (25 cents). The price is still 25 cents, but you don't have to have a quarter. If you put too much money in, we'll just keep it and dispense the same amount of air.

  Take a minute and try to sketch the state diagram for that before you proceed. Although in this case, you could have a very simple state machine that keeps track of the total, try thinking about how to not store the sum but remember the current value as part of the machine's state.

  Too Simple

  You could, of course, have a state for every possible sequence of coins:

  • 25 cents
  • 10 cents, 10 cents, 5 cents
  • 5 cents, 5 cents, 5 cents, 5 cents, 5 cents
  • ... etc.

  This gets you a lot of states fast. Keep in mind, that the second line (10/10/5) could also be 5/10/10 or 10/5/10 so the number of states will grow fast.

  Better

  The trick is to gather up equivalent states -- something we will talk a little bit about in a future section on state machine optimization. If you imagine the entire sea of states that would make up the above list, you should realize that every state that represents 20 cents is exactly the same as far as outputs and transistions go. So it makes sense you can merge them into one single state. Since this machine is pretty simple we can do that just by thinking about it and you should wind up with something like this:

  To simplify things, I am not showing the outputs. They are the same as before. The On state turns on the compressor and leaving the On state turns the compressor back off. The Inxx (like In5) means the input of a coin with that value. In10/25 means either a 10 cent or 25 cent coin detection.

  Heuristics

  As I mentioned, you could do better than this by applying some domain knowledge. We already did this a bit by supposing we have a timer. That is, we didn't have a state for 59 seconds left, 58 seconds left, etc. You could apply this same logic to keeping count of the coins in a separate register. Your state machine would then look like this:

  As a practical matter, this may be the best implementation, but it doesn't show off the state machine very well and real projects will have many more states. But like most design problems, there are many ways to solve this and there are probably many more, too.

• 3

  ▇▇▇▇ State Implementation ▇▇▇▇

  When creating a state machine, there are two things to consider: How to represent the state you are currently in is the most obvious one. This may seem like a trivial concern, but as you'll see, there is more to it than meets the eye.

  The second decision is how you translate your logic into a state machine. There are many possible ways, of course, but most people prefer to use the following methodology:

  1. Use a clocked always block to store the current state.
  2. Create one or more pieces of combinatorial logic to compute the output for the current state.
  3. Create one or more pieces of combinatorial logic to compute the output for the next state.

  Represent!

  The machines we have looked at so far have a pretty small number of states. So there's no real problem representing the states as normal binary numbers. For example, a parity checker might have an idle state (0), an odd state (1), and an even state (2). You use two flip flops and you are "wasting" one state (since 3 is an illegal state). But that's not a big deal.

  However, any time you want to decode the state, you have to examine both state variables. Again, for two that's not a big deal, but what if you had, say 100 states in 8 bits? Or 1000 states in 10? Finding state 821 will take a few inverters and an AND gate. Of course, storing 1000 states in 10 bits is relatively compact, too.

  But what if you don't care about compactness. You care about speed. Probably the fastest method to represent state is the so-called "one hot" method. In the case of the parity machine we would have three binary bits for the state. Idle might be 001, odd would be 010, and even would be 100. At all times, there is only one flip flop set -- which makes sense if you think about the name one-hot.

  Now it is easy to detect a particular state by examining a single bit. So it is fast and easy, what's the downside? You'll need to pay attention to reset because 000 isn't a legitimate state. You sometimes see people use a "modified one-hot" where 000 is the initial state, but if you ever need to decode that state, you lose the advantage.

  Space is another problem. If you really had 1000 states (and, yes, that's probably bigger than you should have) then you'd need 1000 bits of state. Another more subtle problem is reliability. If you want to detect an illegal state, you'll need some sort of gating arrangement that asserts only if more than one state bit asserts. That gets complicated fast with too many bits.

  Still, one-hot is often a great choice for state encoding, and you see it used frequently. With negative logic you sometimes see "one cold" encoding which is the same as one hot, but the active state is zero.

  Gray Codes

  Speaking of reliability, gray code encoding is also possible in some cases. This is similar to the numeric representation except the bit patterns are selected so that only one bit changes per state transition. For example, this wasn't true with the parity machine we mentioned before. In binary, the states were 00, 01 and 10. If you can go from 01 to 10 or vice versa, that's two bit flips. We say the hamming distance between those states is two.

  If we made the parity machine gray, it would turn into a one hot. But consider a different example. Let's say we have a state machine that will count the number of button pushes from 1 to 3. A simple encoding would be two binary bits: 00, 01, 10, and 11 where 00 is the idle state. But, again, the transition between 01 and 10, as well as 11 and 00 requires two bit flips. With a gray code, the states might be: 00 01 11 10. Now each transition only takes one bit flip. 

  There are other encodings like Johnson and O'Brien that seek to minimize bit changes between adjacent states. These schemes can be useful when you want to use combinatorial logic to detect state changes or you are worried about power consumption. 

  It isn't always possible to build a gray or similar sequence without some work. For example,  consider the 00, 01, 11, 10 sequence mentioned above. That's fine if the states go from one to another in sequence. But what if state 00 could go to state 11? You'd need to rearrange the code or use more bits. This is a big problem if you add or change transitions in the middle of the design. 

  Coding Style

  Let's consider a state machine to figure out if the sum of positive numbers is even or odd. It doesn't matter how many bits the numbers are, because all we need to do is look at the last bit of any number to know if it is even or odd. An even number plus an even number is even. An odd number plus an odd number is even. And an even number plus an odd number stays odd.

  We will need three states: idle, odd, and even and let's use one hot encoding, just for practice. It is handy to use localparam to name the states so:

  module odd_even_sum_detect(input clk, input reset, input bit0, 
          output oddled, output evenled);
  
     reg [2:0] state; 
     reg inbit;
     localparam idle=3'b001;
     localparam odd=3'b010;
     localparam even=3'b100;

  Of course, this is a simple example, so you might have even had:

     reg idle, odd, even;

  This gets clumsy, though, when you need to reset things or examine several states at once.

  Remember, we said it is customary to put the state machine into at least three parts. The first part is state management. We'll also use this as an excuse to save the input bit so if it changes externally, we won't care.

     reg [2:0] nextstate;
      always @(posedge clk)
          if (reset) 
            begin
              state<=idle;
              inbit=1'b0;
            end
         else
             begin
                 state<=nextstate;
                 inbit<=bit0;
            end

  Obviously, the trick now is to compute nextstate. This could be done with an assign or with a combinatorial always block. I'll use the always block:
  

      always @(*)
        begin
            if (state==odd) nextstate=inbit?even:odd;
            else nextstate=inbit?odd:even;
       end

  There are a few interesting things to notice here. First, the idle state is zero so it is intrinsically even. The else branch catches both cases. That's the second point, though. You must assign nextstate in all cases so you don't infer a latch. If you fail to do so, the synthesizer will assume you want to keep the next state, but not with a flip flop and you will get a latch. This is usually undesirable.
  

  Because this is combinatorial, you can use = instead of <= and the last assignment is going to "win." So you could, for example, assign something at the top of block as a default or, if using a case statement, be sure to include a default case. In this example, even an illegal state (if one were possible) or an idle state would still get an assignment because we only check for odd and then do something for everything else.

  You might also notice that if state is odd, nextstate is the inverse of inbit otherwise, it is inbit. So you could write this as:

  nextstate=(state==odd)^inbit;

  However, this is less intuitive and -- as we will talk about later -- the tools may even figure that out on our behalf. 

  That leaves one more piece to write. The output section which is, again, combinatorial. This time I'll use assign, but I could do another always @(*) if I wanted to.

     assign oddled=state==odd;
     assign evenled=state==even;

  You hope your synthesizer would figure out that checking for all the bits is not necessary, but if it really checks for 010 and 100, that is kind of a waste. If you want to be more explicit, you could say:

     assign oddled=state[1];
     assign evenled=state[2];

  Having a single clocked piece of code along with a combinatorial part to compute the next state and another to compute the output is known as the "3 process style" of state machine. However, some argue that this is more error prone. You can easily put everything in one place (the "1 process style"):

  always @(posedge clk)
  
          if (reset) 
            begin
              state<=idle;
            end
         else
             begin
                 state<=state==odd?(bit0?even:odd):(bit0?odd:even);
  
                 oddled<=state[1];
  
                 evenled=state[2];
            end

  For something this simple, it is fine. Note that I now don't need to latch inbit because that's done inherently when I store state. Of course, now oddled and evenled are reg types. I could have stayed with the assign and had a "2 process" state machine.

  Which one is best? That's a hotly debated topic. In general, you should pick the style you are most comfortable with for the task at hand.

View all 11 instructions