State Machines

State machines are central and critical to most functions implemented directly in semiconductors. Broadly speaking they are analgous with the software that drives a computer. In practice a microprocessor is a huge user programmable state machine with vast resources. When one writes software, one is essentially enumerating new states for the massive state machine that is the computer as a whole.

Whilst a computer would have massive resources like disk drives, memory, VDU and so forth, the state machines in our serial port are far more constrained. For the serial port, we have in equivalent terms, memory locations. None of these can directly be read or written from our central machines. The memory locations have associated functional behaviours. The state machine can only control them correctly because we have predicted the behaviour of the resources in all conditions and set out in the state machine how to deal with them. Perhaps the best direct computer analogy is that the resources are controlled, behave, and indicate their status much like a microprocessor ALU. The ALU is controlled and indicates state through the condition codes register.

As was alluded some while back, the state machine will normally not actually process any data it's self. It is probably better to consider the state machine as a strategic approach to control in a semiconductor design. In practice, the state machine and its resources, are one of many small bespoke computers all operating in parallel.

The state machines that control the transmitter and receiver of our serial port are fairly straightforward. Both are intended to be Moore machines. When considered in isolation they are actually Mealy machines, but given the synchronous nature of the remainder of the interface these Mealy machines can be considered "safe". In actual fact, and as we shall see, these machines must be Mealy machines in order that the interface can actually work.

Implicit in the previous paragraph is the idea that Mealy machines are somewhat undesirable. In general terms this is true but, as in this case, sometimes they are essential to creating a functional system. To understand the reasons behind this assertion we must consider the differences between Mealy and Moore machines. The following diagram makes these differences explicit;

As can be seen in the diagram, there isn't much difference between the two. Critically, the and gate and the wire in red, promote a Moore machine into a Mealy machine. Overall the state machine shown above is a simple counter. A sliced array of half adders act to take the current count output value, add one, and feed it back into the flip flops as a next output value. On a rising edge of the clock, the next output becomes the current output.

The counter can be caused to either count, or stay the same, by virtue of the carry in signal on the least significant bit of the sliced adder array. The additional logic tacked onto the outputs, is commonly referred to as an output decoder. This name would usually hold irrespective of the Moore or Mealy class of the machine.

On the diagram the red dotted rings indicate the clock relative time point of the signals in the state machine. Naturally the input signal, the count enable, is at time zero relative to the clock. The counter outputs are marked time plus one. This signifies that the outputs are a function of the inputs after one clock cycle. Clearly if the inputs are not synchronised with the clock, then it may be less than one cycle, but usually this would not be the case.

The important distinction between Moore and Mealy machines is that Moore machines do not have output decoders that combine signals of different time reference, whereas Mealy machines do. The single "and" gate in the Mealy machine is an output decoder, chained on to the Moore machine output decoder. When you look you'll see that the inputs to the Moore output decoder are all t+1 signals. The "and" gate Mealy decoder tacked on combines the t+1 signals from Moore, and the overall machine inputs which are t+0.

Mentioned earlier, was that Mealy machines are undesirable. This is for two quite separate reasons. The first is that a Mealy machine directly implies the use of an output decoder, and in turn output decoders are undesirable, either on Moore or Mealy machines. The second is that by nature a Mealy machine combines signals of different time reference, and this makes for more complex thinking when coding Mealy machines.

When creating a state machine one may not know intricate detail of what is being connected to or who wrote it. From the perspective of providing simple understandable interfaces, it is important that there are no awkward time differences between each of the inputs and each of the outputs on a functional module. This isn't always going to be possible to achieve. In practice, computing takes time and it is more or less a given that there will be some time difference between the input and the output, this is known as pipeline delay. What is not so pleasant, is debugging a module where some inputs exhibit different delays to the output, or the outputs different delays to the input.

An output decoder will naturally add a settling delay after the rising edge of the clock. This reduces the time available in any given cycle for further asynchronous computation. For this reason one would naturally want to put flip flops on the output decoder, and give the user the maximum cycle time to do their own onward processing. The problem is that doing so introduces a further delay, and upsets the balance between the direct state outputs and the output decoder outputs. This then is why output decoders are undesirable.

In many cases one cannot avoid using an output decoder. In those cases a simple solution is either not to register the output decoder, or to balance up by putting extra flip flops on the state output, increasing the pipeline delay. Either of these approaches has it's disadvantages. In most processing modules like, say, multipliers it won't matter if the pipeline delay is perhaps even ten cycles longer. As long as the length is known the delay is expected by an outside designer. In a state machine the problem is usually that some event occurs, and in the next clock cycle the event generator expects a corresponding notification to have modified it's state. Adding pipeline delay in this circumstance makes a problem that could not be solved by a Moore machine more and more intractable.

Forgetting the state machine drawn above, consider a state machine that controls some notional "mode". Perhaps one of it's resources is a counter. This is illustrated in our overall serial port example. The counter is used as a timer. When it reaches a specific count value, it indicates an event point, in time. The state machine needs to know this point in time to properly control the mode, but depending on the mode the counter may continue counting, or start counting again immediately from zero.

The state machine has no problem detecting the terminal count, and entering a new state. The next states might be called continue and reset respectively. The problem is that the new state must indicate the action, and by then it is too late to do so. If the terminal count is signalled, changing state takes one cycle, the reset is signalled but then the actual counter reset takes another. The only way to avoid this problem is to use the Mealy machine.

The Mealy machine allows one to specify from the state machine, ahead of time, what should happen. In this example the state before continue or reset might be called choose. When in state choose, allow terminal count to reset directly if the next state will be reset. Alternatively, prevent terminal count from resetting, if the next state will be continue. The terminal count, may, directly cause the counter to reset it's self. This can only occur if the mode of the state machine allows it.

Moore machines are better because when used without an output decoder, they are neater and simpler. The difficulty with them is that they cannot always solve real world problems. When working with existing code it's quite difficult to tell the difference in thinking, just by looking at the code. However well written and meaningful the code is, one still needs to look surrounding resources to understand the detail of the state machine function. Nevertheless, the ability to recognise a Mealy machine is a clear clue as to the thinking necessary.

The normal approach to this problem is to have one person, or a tight knit team, working on a group of resources. The individual or small group are then responsible for producing a functional block which then contains a state machine and the resources. A state machine would normally need to be integrated with it's resources to an exceptional degree of precision.

Next, and finally we'll look at the test harness for the serial port.