Why do we need to synchronise asynchronous inputs in FSM?

Question

I have been newly learning digital electronics. I know that there are gates which perform logic functions, I learned about RS-Latch, D-Latch and Master-Slave-D-Flip-Flop. Now that I can perform logic functions and store states, I can create a Finite-State-Machine (for example traffic light). In class, we talked about this particular traffic light example and there was a discussion about what problems arise, if we would add a start/stop button (signal to traffic light that a pedestrian is waiting for green light).

Conclusion was, that this button would be an asynchronous input we need to put an flip flop before the state machine so this input can be first synchronised.

What I don't understand is, what is the problem with the asynchronous inputs? Why do we need to synchronise it? And why would a flip flop in front of the state machine or the back help with synchronising? I read trough several articles, talking about "metastability" but I still don't understand.

Thanks a lot.

Answer 1

As you already understand, your traffic light controller state machine is a synchronous machine. That is, it is driven by some clock in such a way that all combinatorial logic changes happen and settle out to stable values long enough before the next clock edge to meet the required set-up times.

^{simulate this circuit – Schematic created using CircuitLab}

If the data changes within that setup time the final output will not only be unpredictable, but due to meta-stability, can actually float or dance around some intermediate value for a while before it picks a final value. It can even oscillate between logic one and logic zero at a high frequency causing considerable current flow and heating.

As such, any asynchronous input to a state machine needs to be synchronized at some point in order for the system to work as you expect it to. However, that does not necessarily mean you ALWAYS need to add another latch to the system.

If the input is only proceeding to a single "next gate" AND the state of the input is independent of all other inputs, then it really does not matter if the signal arrives late to the party. Basically, you need to ask... "If we miss the input for a clock cycle, does it matter?"

If however, the input feeds multiple gates that is different. The next gates may see different logic levels and propagate an erroneous state to the next latch. Basically a variety of bad things can happen.

This can be illustrated with your simple example. Note if the metastability at REG1 has not settled before the next clock, it could cause both the WALK and Traffic light to turn on at the same time, or neither could turn on.

^{simulate this circuit}

Further, if an asynchronous input has a relationship with another asynchronous input that you expect to happen at the same time, the second input may be recognized but the first one not.

In both cases you need to add a synchronizing latch to the input to bring the signal timing into line with the state machines clock. Notice, this adds one clock cycle delay, or a half clock cycle delay if you use the other edge of the clock signal.

However, you may be asking, "but doesn't THAT latch suffer from the same problem?" and of course, the answer would be yes it does. But the trick here is to allow that potential meta-stability to happen at a point in the circuit where it does not matter as I highlighted above.

Finding that point can be problematic with dependant inputs. Normally, extra logic needs to be added to qualify those inputs.

However, be aware metastability is a probability thing. Although, because of differences in manufacturing tolerances, most latches will pick-a-side very quickly, there is the possibility that it will remain unstable for quite some time. The longer the gap between clock pulses the higher the probability that it will have settled. As such, if your system clock is at a high frequency it is prudent to divide it down to do the pre-latch to allow for more settling time. However, even then there are no guarantees.

A final thought. I mentioned that there is the possibility of meta-stability induced high currents and heating when synchronizing a random external input. Unfortunately, there is very little you can do to correct that and long metastability issues other than removing asynchronous input circuits.

Answer 2

One problem with asynchronous designs, is the presence of race or hazards. Say for example in this circuit, let A = 1, B = 0 and C = 1 initially and so D is stable and settled at 1.

Now let B changed to 1 and C changed to 0 at the same moment. Its obvious that D will remain at 1. But in real circuits, propagation delays and wire delays matter. Hence it is very much possible that the change in C reaches the OR gate faster than the change in B propagates to the OR gate , through the AND gate. The result is that D is pulled to 0 momentarily, before it goes again to its stable state 1. This is are called race or hazard. This momentary glitch may trigger whatever circuit is present after D ,and this unwanted transition gets propagated through the whole circuit. This causes unwanted power dissipation and possibly error in functionality.

To avoid these problems, we can register the inputs and outputs by adding a D-flip-flops before all the inputs A,B,C, and after the output D. So that now our circuit latches only stable inputs at clock-edges, computes the expression, latches D and outputs it only in the next clock edge. This ensure that no such glitches in inputs or outputs are propagated in our circuit, provided that all the inputs to flip-flops meet setup and hold time.

This is the main reason why synchronous designs are more preferred, despite the speed that asynchronous designs give.