8
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

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.

schematic

simulate this circuit – Schematic created using CircuitLab

enter image description here

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.

enter image description here

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.

schematic

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.

\$\endgroup\$
6
  • \$\begingroup\$ Thank you! So the extra one clock cycle from the flip flop adds time for the metastability to stabilise? Also, why would we put a flip flop, at the end of a FSM? \$\endgroup\$
    – Eren
    Commented Nov 21, 2017 at 12:49
  • \$\begingroup\$ @Eren Yes adds time and gives it a safe place, logically, to settle into synchronism. Generally you want all the outputs to change at the same time. So the last stage should normally be a flip-flop, or more accurately, "latch" output, so the outputs are all synchronous. \$\endgroup\$
    – Trevor_G
    Commented Nov 21, 2017 at 12:52
  • 1
    \$\begingroup\$ gave you+1 for multiple gates, but on trust that you correct your final paragraphs. Metastability in the sync latch matters as well, because that can be passed into the circuit. There is no cure for metastability. However, you can reduce the likelyhood down to vanishingly small probability by waiting longer before the final decision. In order to avoid reducing clock rate, this is usually done by pipelining extra D-flops before it. Once the probaility of error is down to once in the age of the universe, for 1billion circuits at max clock rate, most folks deem metastability 'cured' \$\endgroup\$
    – Neil_UK
    Commented Nov 21, 2017 at 13:57
  • \$\begingroup\$ @Neil_UK yup, I was trying to say that, without confusing the OP too much. Still a work in progress. Got to step out for the day though. Thanks. \$\endgroup\$
    – Trevor_G
    Commented Nov 21, 2017 at 14:00
  • 1
    \$\begingroup\$ Metastability is a bogeyman in these kinds of discussions. In reality, the situation you describe where you feed multiple inputs across the clock boundary will fail way more often than you get metastability events. Routing delays can skew on the order of nanoseconds which means a change in the data may reach one flip flop before the rising edge of the receiving clock and may reach another flip flop after the rising edge. I make this distinction because metastability is only an issue in cases where you have very little slack, whereas routing skew is always an issue. \$\endgroup\$
    – jalalipop
    Commented Nov 21, 2017 at 20:20
3
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you very much! I just have one more question if that is ok. Adding the flip flops before the inputs and after the outputs will cause a shift of two clock cycles. Will the shifting cause any trouble for our state machine? There was an analogy with Person A counting to 7 and asking Person B if he counted correctly. B will analyse it and answers "Yes". If we had a flip flop in front and after output the answer "yes" would reach person A when he is already at 9. I don't see how this would cause any trouble though besides latency \$\endgroup\$
    – Eren
    Commented Nov 21, 2017 at 15:05
  • \$\begingroup\$ After latching the inputs in a clock cycle, We get the output in the next clock cycle itself. Functionality will remain same. State transition in every clock cycle. That's how FSM is usually designed. \$\endgroup\$
    – Mitu Raj
    Commented Nov 21, 2017 at 15:15
  • \$\begingroup\$ Yea thats the delay caused by flip-flop, But that's not affecting the functionality. \$\endgroup\$
    – Mitu Raj
    Commented Nov 21, 2017 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.