State Machine Design in AHDL

FreeCore Library
State Machine Design in AHDL
by
Håkan Pettersson
and
Rune Baeverrud

Modifications to this Text

Modified	Description
July 11, 1997	- Added section "Alternative way of entering State Machines using TABLE" - Added section "Illegal states in 1-hot encoded state machines" - Added section "Register your external inputs!" - Added section "When should you be using a Moore or Mealy state machine?"

Different Types of State Machines

There are basically two different types of state machines available, both of them are very easily written in AHDL. The two types are (with explanation) :

Moore state machine	Mealy state machine
A state machine in which the present state depends only on its previous input and previous state, and the present output depends only on the present state.	A type of state machine in which the outputs are a function of the inputs and the current state.

The most common way of describing a state machine is by drawing a bubble diagram that shows all the states and all the transitions between the states. We will start by giving an example of a Moore state machine and then describing how to change the design into a Mealy state machine.

Example of a Moore state machine

States	S0, S1, S2, S3
Inputs	clk, reset, up_down
Outputs	out1, out2

SUBDESIGN moore
(
  clk, reset, up_down : INPUT ;
  out[1..0]           : OUTPUT;
)

VARIABLE
  moore_state : MACHINE WITH STATES (S0,S1,S2,S3);

BEGIN   
  moore_state.clk = clk;
  moore_state.reset = reset;
  CASE moore_state IS
    WHEN S0 =>
      out[] = B"00";
      IF up_down THEN
        moore_state = S1;
      ELSE
        moore_state = S2;
      END IF;
    WHEN S1 =>
      out[] = B"01";
      IF up_down THEN
        moore_state = S3;
      ELSE
        moore_state = S0;
      END IF;
    WHEN S2 =>
      out[] = B"10";
      IF up_down THEN
        moore_state = S0;
      ELSE
        moore_state = S3;
      END IF;
    WHEN S3 =>
      out[] = B"11";
      IF up_down THEN
        moore_state = S2;
      ELSE
        moore_state = S1;
      END IF;
    WHEN OTHERS =>
      moore_state = S0;
  END CASE;
END;

In the above example we are implementing the Moore state machine directly from the state diagram. Please note the direct one-to-one mapping from the diagram to the CASE statement, which make the AHDL code implementation very straight-forward.

How to change it into the Mealy state machine

States	S0, S1, S2, S3
Inputs	clk, reset, CntEn, up_down
Outputs	out1, out2, Move

Now that we have implemented the Moore state machine, how do we change it into the Mealy variant? It is quite simple actually - all we have to do is to make the output dependent on the input, and this is done by inserting IF-THEN statements into the WHEN statements. For example, in state S0 the output Move should be 0 if CntEn == 0, but 1 if CntEn == 1, and that would make the WHEN statement for state S0 look like this:

    WHEN S0 =>
      out[] = B"00";
      IF up_down THEN
        moore_state = S1;
      ELSE
        moore_state = S2;
      END IF;
-- here comes the part that makes the Moore into a Mealy
      IF CntEn == B"0" THEN
        Move = B"0";
      ELSE
        Move = B"1";
      END IF;

The rest of the WHENs should be changed accordingly.

When should you be using a Moore or Mealy state machine?

From the examples above, you can easily see that you may get more output combinations from a Mealy machine than with a Moore machine, given the same number of states. The reason for this is that the output of a Moore machine only depends on the current state, but in a Mealy machine the output depends on some input as well. Therefore, to achieve the same set of output values in the two types of state machines, a Moore machine will generally be consuming more states than a Mealy machine would do. That does not necessarily mean that the Moore machine will be consuming more logic than in the Mealy case, since in the Mealy case there would also be some consumption of logic resources for the output decoding.

An advantage of a Moore machine is that the output is independent of changes to the inputs, so the the behaviour of a Moore machine in a complex system may be less critical than in the Mealy case. In a Mealy machine, if your inputs are not well behaved, you may encounter problems with glitchy outputs.

You should generally expect a higher achievable system clock rate with a Moore machine than with a Mealy machine, because of the shorter combinational logic paths involved.

Why use reset?

The reset is there to ensure that the state machine starts up in a known state. The start up state will always be the first state declared in the WITH STATES (...) list. In the examples above that would be state S0.

Why should you use CASE statements?

It's easier to use the CASE statement than nested IF-THEN statements:

It is a lot easier to read CASE blocks than nested IF-THENs
There is a direct one-to-one mapping between the state machine bubble diagram and a CASE block. This makes it very easy to implement the AHDL code directly from the state diagram. Check out the examples above.
When using the CASE statement you can use the OTHERS keyword to take care of the don't care states, this will make the state machine to always get back to a known state even after initialization failures. If using IF-THEN statements you must keep track of all possible and impossible (don't care) states yourself, which can be hard if the state machine is big.
The CASE statement is not level sensitive, i.e. it doesn't matter in what order you enter the WHENs, whereas the IF statement is sensitive to the evaluation order of the IFs.

Where should you specify the outputs?

If you have a small state machine, like the Moore state machine example above, it is rather easy to see the overall structure of the state machine right away from the code. But when the state machine grows in size it gets more and more complicated to see what is going on. What you can do then is to specify the transitions in one CASE clause and the outputs in another. This won't affect the synthesis of the state machine, but rather give you more easily readable code. By using this technique - the Moore example would look like this :

(Skipped declaration)

  CASE moore_state IS
    WHEN S0 =>
      IF up_down THEN
        moore_state = S1;
      ELSE
        moore_state = S2;
      END IF;
    WHEN S1 =>
      IF up_down THEN
        moore_state = S3;
      ELSE
        moore_state = S0;
      END IF;
    WHEN S2 =>
      IF up_down THEN
        moore_state = S0;
      ELSE
        moore_state = S3;
      END IF;
    WHEN S3 =>
      IF up_down THEN
        moore_state = S2;
      ELSE
        moore_state = S1;
      END IF;
    WHEN OTHERS =>
      moore_state = S0;
  END CASE;
END;

% Outputs from state machine %
  CASE moore_state IS
    WHEN S0 =>
      out[] = B"00";
    WHEN S1 =>
      out[] = B"01";
    WHEN S2 =>
      out[] = B"10";
    WHEN S3 =>
      out[] = B"11";
  END CASE;

Consider now adding a couple of counters controlled by the state machine. Instead of implementing the counter logic in the main state machine control block above, you should implement the counter logic in separate blocks, like this:

-- controls the counter[] variable
  CASE moore_state IS
    WHEN S0, S1 =>
      count[] = count[] + 1;
    WHEN S2 =>
      count[] = count[] + 2;
    WHEN OTHERS =>
      count[] = count[];
  END CASE;

-- controls the beers[] variable
  IF moore_state == S0 THEN
    beers[] = beers[] - 1;
  ELSE
    beers[] = beers[];
  END;

The alternative to the above approach would be to fully specify both beers[] and counter[] for every single possible condition in the main block! This design methodology will save a lot of code space and make the code much more readable!

Alternative way of entering State Machines using TABLE

There is an alternative way of entering state machines by using the TABLE statement. Please keep in mind that you cannot enter expressions like count[] = count[] + 1 within a table, so you would have to keep this kind of constructs outside of the table.

SUBDESIGN mealy
(
  clk, reset, y : INPUT ; 
  z             : OUTPUT;
) 
VARIABLE
ss : MACHINE WITH STATES (S0,S1,S2,S3);

BEGIN
  ss.clk = clk;
  ss.reset = reset;
  TABLE
    ss, y => z, ss;
    s0, 0 => 0, s0;
    s0, 1 => 1, s1;
    s1, 0 => 1, s1;
    s1, 1 => 0, s2;
    s2, 0 => 0, s2;
    s2, 1 => 1, s3;
    s3, 0 => 0, s3;
    s3, 1 => 1, s0;
  END TABLE;
END;

Register your external inputs!

If your state machine is designed with the possibility to branch to several other states from a given state depending on your input signals, we recommend that you register (sample) the external inputs to your state machine. In this way you can be safe with regard to not violate the setup/hold requirements for the inputs to the state machine, preventing it from entering illegal states.

Encoding of state machines

You can specify the encoding of the state machine yourself, but if you don't then MAX+PLUS II will do it for you. MAX+PLUS II uses 1-hot encoding for the FLEX parts and binary encoding for the MAX parts. Differences between 1-hot and binary encoding :

1-hot encoding: uses one register for each state, this is very good if you have register intensive architectures such as the FLEX devices. Does not need a lot of decoding.
Binary encoding: Uses N number of registers for 2^N number of states. This demands more decoding of the states which is why it is useful for product term based architechtures such as the MAX devices.

If you want to specify the type of encoding yourself, for instance if you want to use Gray coding instead, it could be done like this:

SUBDESIGN moore 
( 
  clk, reset, up_down : INPUT ; 
  out[1..0]  : OUTPUT; 
)

VARIABLE 
  moore_state : MACHINE OF BITS (q1, q2) WITH STATES ( 
    S0 = B"00",
    S1 = B"01",
    S2 = B"11",
    S3 = B"10");

BEGIN 
 .... 
END;

More on the WHEN OTHERS clause

Note: You cannot use the WHEN OTHERS clause to recover from undefined states!

Consider the following state machine declaration:

VARIABLE 
  Porche : MACHINE WITH STATES (S0, S1, S2, S3, S4);

This machine has 5 states, and the machine could be controlled like this:

  CASE Porche IS
    WHEN S0 =>
      Porche = S1;
    WHEN S1 =>
      Porche = S2;
    WHEN S2 =>
      Porche = S3;
    WHEN S3 =>
      Porche = S4;
    WHEN S4 =>
      Porche = S0;
    WHEN OTHERS =>
      Porche = S0;
  END CASE;

When compiling this for a FLEX architecture, the state machine will use 1-hot encoding and consume exactly 5 state registers - one for each state. The WHEN OTHERS statement is not really necessary (but still good programming style though) because there are no other possible legal states.

When compiling this for a MAX architecture, the state machine will use binary encoding, and 3 state registers are needed to represent the 5 required states. But with 3 bits encoding - there will actually be a total of 8 states possible including the undefined states. This is where the WHEN OTHERS clause is really useful, to account for the unused states and make a recovery from these states possible. But you will need to define these states to be able to recover from them, and you should therefore change the declaration of the state machine to something like this:

-- State machine declaration with exactly 8 (2^N, N=3) states
VARIABLE 
  Porche : MACHINE WITH STATES (S0, S1, S2, S3, S4, rubbish, dummy2, dummy3);

Illegal states in 1-hot encoded state machines

A 1-hot coded state machine is no better than a binary coded state machine with regard to entering and recovering from illegal states. In fact, it is worse, since it is impossible to define the illegal states and so be able to recover from them. The illegal states of a 1-hot encoded state machines occur if more than one state bit is active at any given time. This could be caused by inputs violating the setup/hold times, or clocking the state machine too fast.

More on 1-hot encoding

The first state you define in the WITH STATES (...) clause is the default/reset condition you enter after a system reset. That would be the S0 state in the examples above. You may very well be in the belief (like most people are) that this state machine would be encoded like this:

	state bit S3	state bit S2	state bit S1	state bit S0
State S0	0	0	0	1
State S1	0	0	1	0
State S2	0	1	0	0
State S3	1	0	0	0

If it were - how could you possibly enter state S0 after a system reset? After all - all registers are cleared to zero on a system reset! Actually, the 1-hot encoding is done a little differently, more like this:

	state bit S3	state bit S2	state bit S1	state bit S0
State S0	0	0	0	0
State S1	0	0	1	1
State S2	0	1	0	1
State S3	1	0	0	1

The state bit corresponding to the default/reset state (S0) is actually inverted, so that all state bits are 0's after system reset. This is still 1-hot coding though, and you still only have to check a single state bit to determine if you are in a particular state or not.

This is not something you will have to worry about, as MAX+PLUS II will take care of all this for you and hide the implementation details. We just provided it here for your convenience.

State machines using the EABs in Flex 10K

It is possible to use the EABs in Altera's FLEX 10K family as logic, and as such implement state machines. But to do so you need to implement the state machine in two levels. One file that describes the behaviour of the state machine, and one file to connect all the needed inputs and outputs. An example of this can be found in the Altera Atlas Solutions Database. Click on the icon to the right to go there.

About this page

I hope that this has been of any value to you and we wish you good luck in designing state machines in the future. If you still think that state machines are a bit tricky to design we can suggest you have a look at http://www.hardi.se/english/welcome.htm - they have graphical state machine editors available.

Håkan Pettersson
Rune Baeverrud

Last updated 28 Jul 1999 07:23