§5.1 Moore and Mealy machine semantics

Unit 5, Lesson 1: Moore and Mealy machine semantics

Learning focus: Moore outputs depend on registered state; Mealy outputs can react immediately to inputs through combinational logic. Either architecture needs a complete default transition.

1. The idea in engineering context

Moore outputs depend on registered state; Mealy outputs can react immediately to inputs through combinational logic. Either architecture needs a complete default transition. This principle belongs within finite-state machines and controllers. To reason correctly, decide what kind of object each symbol represents: a Boolean truth value, a signed integer, a sample of a waveform, a device threshold, a state bit, or a timed event. An equation may be mathematically valid yet describe the wrong physical or temporal quantity. In a circuit drawing, label all inputs, outputs and control signals with direction and active polarity. If a signal can be unknown, undefined or invalid, describe what the receiving block must do rather than silently treating the signal as zero.

A useful preliminary step is to state the behavior without naming any particular component. For the topic moore and mealy machine semantics, write an input-output contract in plain language and translate it to a truth table, transition table, numerical equation or timing diagram as appropriate. The same contract should survive translation into a schematic, a behavioral simulation and an HDL module. If an implementation changes the contract, the change must be documented as a new requirement rather than hidden as a convenience.

2. A checkable example

A turnstile Moore controller moves LOCKED→OPEN after a coin; a Mealy implementation can assert unlock during the coin event. Reproduce this calculation or Boolean reasoning from the definitions, showing intermediate bit patterns and units where relevant. When the example uses an idealized value, state explicitly that the numerical values are illustrative teaching inputs, not component specifications. If it refers to a word length, compute the representable range; if it refers to timing, identify the relevant clock domain, edge and uncertainty terms; and if it refers to a voltage, distinguish absolute maximum ratings from guaranteed digital logic levels.

Alternate check. Explain the expected result qualitatively before computing it. A binary carry chain, parity function, or state transition often has an intuitive conserved property: changing one input can affect a particular output but not every unrelated output. Compare the intuitive expectation with the mathematical answer and resolve discrepancies by writing a smaller exhaustive example. This is especially important when signed interpretation, bit ordering or active-low conventions may reverse an apparently obvious answer.

3. Design method and derivation

Temporal specification. Make a timeline containing clock edges, pre-edge data, post-edge state and observable outputs. Mark all changes that can occur asynchronously. A signal described as valid 'at the edge' is not sufficient unless setup and hold requirements are met in the hardware implementation. Use a reset sequence to establish a known state and test what happens if the enable signal changes close to a clock edge.

The next step is to make the dependence of output on input explicit. Start with the simplest special case: zero data, inactive enable, reset asserted, or minimum address as appropriate. Then test the opposite boundary, including all-one words, maximum carry, saturated load, or final counter state. For moore and mealy machine semantics, list which of these tests are informative and which are irrelevant. Do not automatically assign meaning to a don't-care or illegal combination. If a simplification assumes certain input codes never occur, describe how the enclosing system enforces that assumption.

Controller reasoning. A design is easier to verify when the number of states and their meaning are explicit. For every state, define outputs, permitted next states and conditions for remaining in place. Write the illegal-state behavior in addition to the nominal transition graph. Test whether a requested action is lost during reset or when two requests arrive together. Safety properties and liveness properties must be stated separately; one forbids bad events, the other asks that desired events eventually occur.

4. Failure modes and limits

Topic-specific pitfall: An asynchronous sensor glitch may propagate directly to Mealy outputs. A reliable engineering write-up names the condition that triggers the failure, the observable symptom and the quickest discriminating test. For a functional bug, compare expected and actual truth-table rows; for a timing bug, inspect waveform edges and clock assumptions; for a numeric bug, inspect sign extension and intermediate widths; and for an interface bug, check whether validity and acknowledgement share the same interpretation at each endpoint.

Unit-level model boundary: An FSM can be functionally complete yet physically unsafe if asynchronous inputs or reset removal are unqualified. Avoid extrapolating an ideal gate model into a claim about any particular commercial part. Robustness also requires considering reset entry, temperature-dependent device performance and asynchronous external disturbances whenever they are relevant. If a measured device disagrees with a model, first verify the input stimulus, measurement bandwidth and grounding before declaring the underlying logic theory incorrect.

5. Worked design workflow

1. Specify: write a sentence that defines each input, output and its width; resolve any ambiguous invalid or simultaneous input behavior.

2. Model: select a Boolean expression, transition relation or time equation that captures the defined behavior and state all assumptions.

3. Derive: compute the result for the particular illustrative case above. If there is arithmetic, keep bit widths explicit through every intermediate operation.

4. Cross-check: compare against an independently enumerated case or a direct formula. Document discrepancies rather than adjusting the expected answer to match the implementation.

5. Implement: map the model to gates or synthesizable RTL, leaving enough information to identify clocking, reset and active polarities.

6. Verify: test boundaries and one deliberate fault injection, then record whether the result is logical, simulated, measured or formally proven.

This workflow is intentionally stricter than drawing a plausible diagram. An executable calculator can confirm arithmetic while missing an incorrect interpretation of its inputs. Conversely, a timing waveform can look convincing even if the specification omitted a simultaneous request. A successful solution must connect intent, derivation and independent observation.

6. Laboratory and simulation protocol

Investigation: Compare observable latency of Moore and Mealy implementations of the same controller. Construct a small input matrix containing at least one nominal case, a lower boundary, an upper boundary and a deliberately ambiguous or invalid stimulus. Before running a browser model, write your predicted output and the rule that supports it. Run the experiment, record the output and compare. If the model disagrees with your prediction, determine whether the error is in your rule, your convention, or the model. Explicitly distinguish calculated values from observed electrical measurements; the provided browser apps are not instruments connected to hardware.

Extensions. Repeat the test with an input changed by one bit or one clock cycle. If the result is unchanged, explain which invariance made that possible. If the result changes, identify the exact dependency path. Next ask whether this exercise would still work with a real gate driving several receivers, a different supply voltage, or a clock with uncertainty. That question may require a data sheet, timing analysis or physical measurement beyond the ideal simulation.

7. Guided exercises

1. Derive and explain. Starting from the definition behind moore and mealy machine semantics, construct the smallest nontrivial truth table, bit pattern, timing diagram or state-transition example. Label all relevant conventions. Provide an independent cross-check.

2. Boundary case. Modify the worked example so that one parameter is at its legal minimum and another at its legal maximum. Recompute the expected result and explain whether the nominal assumption still holds.

3. Find the error. Analyze this claim: “An asynchronous sensor glitch may propagate directly to Mealy outputs.” Identify a concrete input condition that reveals the problem, describe the output symptom and propose a correction or safety guard.

4. Design choice. Compare two implementations of the lesson's function: a direct gate-level representation and a modular block with explicit interface signals. State their likely advantages in clarity, area, timing or testability without assuming a universal winner.

5. Verification. Write five test vectors (including a boundary and invalid input), expected results and a single assertion or invariant that should hold across the set. Explain how a false-positive test could occur.

8. Reflection and further study

The central question of Moore and Mealy machine semantics is not whether an expression looks familiar, but whether a particular result follows from a complete set of stated assumptions. Recheck the significance of each bit and event, the boundary conditions and the consequences of implementing the abstraction in physical hardware. In design reviews, a clearly documented failed assumption is more valuable than a visually polished schematic with hidden undefined behavior. Before moving on, write a three-sentence summary: what this mechanism guarantees, what it does not guarantee, and the simplest independent test that would reveal a mistake.

§5.2 State diagrams and transition tables

Unit 5, Lesson 2: State diagrams and transition tables

Learning focus: States are distinctions about remembered history; arrows specify triggering conditions and outputs. Start the design with reset and an explicit default case.

1. The idea in engineering context

States are distinctions about remembered history; arrows specify triggering conditions and outputs. Start the design with reset and an explicit default case. This principle belongs within finite-state machines and controllers. To reason correctly, decide what kind of object each symbol represents: a Boolean truth value, a signed integer, a sample of a waveform, a device threshold, a state bit, or a timed event. An equation may be mathematically valid yet describe the wrong physical or temporal quantity. In a circuit drawing, label all inputs, outputs and control signals with direction and active polarity. If a signal can be unknown, undefined or invalid, describe what the receiving block must do rather than silently treating the signal as zero.

A useful preliminary step is to state the behavior without naming any particular component. For the topic state diagrams and transition tables, write an input-output contract in plain language and translate it to a truth table, transition table, numerical equation or timing diagram as appropriate. The same contract should survive translation into a schematic, a behavioral simulation and an HDL module. If an implementation changes the contract, the change must be documented as a new requirement rather than hidden as a convenience.

2. A checkable example

A two-state request/acknowledge controller remains WAIT until request=1, then enters ACK until request returns to 0. Reproduce this calculation or Boolean reasoning from the definitions, showing intermediate bit patterns and units where relevant. When the example uses an idealized value, state explicitly that the numerical values are illustrative teaching inputs, not component specifications. If it refers to a word length, compute the representable range; if it refers to timing, identify the relevant clock domain, edge and uncertainty terms; and if it refers to a voltage, distinguish absolute maximum ratings from guaranteed digital logic levels.

Alternate check. Explain the expected result qualitatively before computing it. A binary carry chain, parity function, or state transition often has an intuitive conserved property: changing one input can affect a particular output but not every unrelated output. Compare the intuitive expectation with the mathematical answer and resolve discrepancies by writing a smaller exhaustive example. This is especially important when signed interpretation, bit ordering or active-low conventions may reverse an apparently obvious answer.

3. Design method and derivation

Temporal specification. Make a timeline containing clock edges, pre-edge data, post-edge state and observable outputs. Mark all changes that can occur asynchronously. A signal described as valid 'at the edge' is not sufficient unless setup and hold requirements are met in the hardware implementation. Use a reset sequence to establish a known state and test what happens if the enable signal changes close to a clock edge.

The next step is to make the dependence of output on input explicit. Start with the simplest special case: zero data, inactive enable, reset asserted, or minimum address as appropriate. Then test the opposite boundary, including all-one words, maximum carry, saturated load, or final counter state. For state diagrams and transition tables, list which of these tests are informative and which are irrelevant. Do not automatically assign meaning to a don't-care or illegal combination. If a simplification assumes certain input codes never occur, describe how the enclosing system enforces that assumption.

Controller reasoning. A design is easier to verify when the number of states and their meaning are explicit. For every state, define outputs, permitted next states and conditions for remaining in place. Write the illegal-state behavior in addition to the nominal transition graph. Test whether a requested action is lost during reset or when two requests arrive together. Safety properties and liveness properties must be stated separately; one forbids bad events, the other asks that desired events eventually occur.

4. Failure modes and limits

Topic-specific pitfall: A diagram without conditions for simultaneous signals is incomplete. A reliable engineering write-up names the condition that triggers the failure, the observable symptom and the quickest discriminating test. For a functional bug, compare expected and actual truth-table rows; for a timing bug, inspect waveform edges and clock assumptions; for a numeric bug, inspect sign extension and intermediate widths; and for an interface bug, check whether validity and acknowledgement share the same interpretation at each endpoint.

Unit-level model boundary: An FSM can be functionally complete yet physically unsafe if asynchronous inputs or reset removal are unqualified. Avoid extrapolating an ideal gate model into a claim about any particular commercial part. Robustness also requires considering reset entry, temperature-dependent device performance and asynchronous external disturbances whenever they are relevant. If a measured device disagrees with a model, first verify the input stimulus, measurement bandwidth and grounding before declaring the underlying logic theory incorrect.

5. Worked design workflow

1. Specify: write a sentence that defines each input, output and its width; resolve any ambiguous invalid or simultaneous input behavior.

2. Model: select a Boolean expression, transition relation or time equation that captures the defined behavior and state all assumptions.

3. Derive: compute the result for the particular illustrative case above. If there is arithmetic, keep bit widths explicit through every intermediate operation.

4. Cross-check: compare against an independently enumerated case or a direct formula. Document discrepancies rather than adjusting the expected answer to match the implementation.

5. Implement: map the model to gates or synthesizable RTL, leaving enough information to identify clocking, reset and active polarities.

6. Verify: test boundaries and one deliberate fault injection, then record whether the result is logical, simulated, measured or formally proven.

This workflow is intentionally stricter than drawing a plausible diagram. An executable calculator can confirm arithmetic while missing an incorrect interpretation of its inputs. Conversely, a timing waveform can look convincing even if the specification omitted a simultaneous request. A successful solution must connect intent, derivation and independent observation.

6. Laboratory and simulation protocol

Investigation: Derive a table for all current-state and input combinations. Construct a small input matrix containing at least one nominal case, a lower boundary, an upper boundary and a deliberately ambiguous or invalid stimulus. Before running a browser model, write your predicted output and the rule that supports it. Run the experiment, record the output and compare. If the model disagrees with your prediction, determine whether the error is in your rule, your convention, or the model. Explicitly distinguish calculated values from observed electrical measurements; the provided browser apps are not instruments connected to hardware.

Extensions. Repeat the test with an input changed by one bit or one clock cycle. If the result is unchanged, explain which invariance made that possible. If the result changes, identify the exact dependency path. Next ask whether this exercise would still work with a real gate driving several receivers, a different supply voltage, or a clock with uncertainty. That question may require a data sheet, timing analysis or physical measurement beyond the ideal simulation.

7. Guided exercises

1. Derive and explain. Starting from the definition behind state diagrams and transition tables, construct the smallest nontrivial truth table, bit pattern, timing diagram or state-transition example. Label all relevant conventions. Provide an independent cross-check.

2. Boundary case. Modify the worked example so that one parameter is at its legal minimum and another at its legal maximum. Recompute the expected result and explain whether the nominal assumption still holds.

3. Find the error. Analyze this claim: “A diagram without conditions for simultaneous signals is incomplete.” Identify a concrete input condition that reveals the problem, describe the output symptom and propose a correction or safety guard.

4. Design choice. Compare two implementations of the lesson's function: a direct gate-level representation and a modular block with explicit interface signals. State their likely advantages in clarity, area, timing or testability without assuming a universal winner.

5. Verification. Write five test vectors (including a boundary and invalid input), expected results and a single assertion or invariant that should hold across the set. Explain how a false-positive test could occur.

8. Reflection and further study

The central question of State diagrams and transition tables is not whether an expression looks familiar, but whether a particular result follows from a complete set of stated assumptions. Recheck the significance of each bit and event, the boundary conditions and the consequences of implementing the abstraction in physical hardware. In design reviews, a clearly documented failed assumption is more valuable than a visually polished schematic with hidden undefined behavior. Before moving on, write a three-sentence summary: what this mechanism guarantees, what it does not guarantee, and the simplest independent test that would reveal a mistake.

§5.3 State encoding and illegal-state recovery

Unit 5, Lesson 3: State encoding and illegal-state recovery

Learning focus: Binary encoding minimizes the nominal number of flip-flops; one-hot encoding may simplify combinational decoding at the cost of extra storage.

1. The idea in engineering context

Binary encoding minimizes the nominal number of flip-flops; one-hot encoding may simplify combinational decoding at the cost of extra storage. This principle belongs within finite-state machines and controllers. To reason correctly, decide what kind of object each symbol represents: a Boolean truth value, a signed integer, a sample of a waveform, a device threshold, a state bit, or a timed event. An equation may be mathematically valid yet describe the wrong physical or temporal quantity. In a circuit drawing, label all inputs, outputs and control signals with direction and active polarity. If a signal can be unknown, undefined or invalid, describe what the receiving block must do rather than silently treating the signal as zero.

A useful preliminary step is to state the behavior without naming any particular component. For the topic state encoding and illegal-state recovery, write an input-output contract in plain language and translate it to a truth table, transition table, numerical equation or timing diagram as appropriate. The same contract should survive translation into a schematic, a behavioral simulation and an HDL module. If an implementation changes the contract, the change must be documented as a new requirement rather than hidden as a convenience.

2. A checkable example

Eight states require at least three binary flip-flops, whereas a conventional one-hot implementation uses eight. Reproduce this calculation or Boolean reasoning from the definitions, showing intermediate bit patterns and units where relevant. When the example uses an idealized value, state explicitly that the numerical values are illustrative teaching inputs, not component specifications. If it refers to a word length, compute the representable range; if it refers to timing, identify the relevant clock domain, edge and uncertainty terms; and if it refers to a voltage, distinguish absolute maximum ratings from guaranteed digital logic levels.

Alternate check. Explain the expected result qualitatively before computing it. A binary carry chain, parity function, or state transition often has an intuitive conserved property: changing one input can affect a particular output but not every unrelated output. Compare the intuitive expectation with the mathematical answer and resolve discrepancies by writing a smaller exhaustive example. This is especially important when signed interpretation, bit ordering or active-low conventions may reverse an apparently obvious answer.

3. Design method and derivation

Temporal specification. Make a timeline containing clock edges, pre-edge data, post-edge state and observable outputs. Mark all changes that can occur asynchronously. A signal described as valid 'at the edge' is not sufficient unless setup and hold requirements are met in the hardware implementation. Use a reset sequence to establish a known state and test what happens if the enable signal changes close to a clock edge.

The next step is to make the dependence of output on input explicit. Start with the simplest special case: zero data, inactive enable, reset asserted, or minimum address as appropriate. Then test the opposite boundary, including all-one words, maximum carry, saturated load, or final counter state. For state encoding and illegal-state recovery, list which of these tests are informative and which are irrelevant. Do not automatically assign meaning to a don't-care or illegal combination. If a simplification assumes certain input codes never occur, describe how the enclosing system enforces that assumption.

Controller reasoning. A design is easier to verify when the number of states and their meaning are explicit. For every state, define outputs, permitted next states and conditions for remaining in place. Write the illegal-state behavior in addition to the nominal transition graph. Test whether a requested action is lost during reset or when two requests arrive together. Safety properties and liveness properties must be stated separately; one forbids bad events, the other asks that desired events eventually occur.

4. Failure modes and limits

Topic-specific pitfall: An illegal state can be reached by a transient fault or from unknown startup conditions. A reliable engineering write-up names the condition that triggers the failure, the observable symptom and the quickest discriminating test. For a functional bug, compare expected and actual truth-table rows; for a timing bug, inspect waveform edges and clock assumptions; for a numeric bug, inspect sign extension and intermediate widths; and for an interface bug, check whether validity and acknowledgement share the same interpretation at each endpoint.

Unit-level model boundary: An FSM can be functionally complete yet physically unsafe if asynchronous inputs or reset removal are unqualified. Avoid extrapolating an ideal gate model into a claim about any particular commercial part. Robustness also requires considering reset entry, temperature-dependent device performance and asynchronous external disturbances whenever they are relevant. If a measured device disagrees with a model, first verify the input stimulus, measurement bandwidth and grounding before declaring the underlying logic theory incorrect.

5. Worked design workflow

1. Specify: write a sentence that defines each input, output and its width; resolve any ambiguous invalid or simultaneous input behavior.

2. Model: select a Boolean expression, transition relation or time equation that captures the defined behavior and state all assumptions.

3. Derive: compute the result for the particular illustrative case above. If there is arithmetic, keep bit widths explicit through every intermediate operation.

4. Cross-check: compare against an independently enumerated case or a direct formula. Document discrepancies rather than adjusting the expected answer to match the implementation.

5. Implement: map the model to gates or synthesizable RTL, leaving enough information to identify clocking, reset and active polarities.

6. Verify: test boundaries and one deliberate fault injection, then record whether the result is logical, simulated, measured or formally proven.

This workflow is intentionally stricter than drawing a plausible diagram. An executable calculator can confirm arithmetic while missing an incorrect interpretation of its inputs. Conversely, a timing waveform can look convincing even if the specification omitted a simultaneous request. A successful solution must connect intent, derivation and independent observation.

6. Laboratory and simulation protocol

Investigation: Implement binary and one-hot encodings and compare next-state complexity. Construct a small input matrix containing at least one nominal case, a lower boundary, an upper boundary and a deliberately ambiguous or invalid stimulus. Before running a browser model, write your predicted output and the rule that supports it. Run the experiment, record the output and compare. If the model disagrees with your prediction, determine whether the error is in your rule, your convention, or the model. Explicitly distinguish calculated values from observed electrical measurements; the provided browser apps are not instruments connected to hardware.

Extensions. Repeat the test with an input changed by one bit or one clock cycle. If the result is unchanged, explain which invariance made that possible. If the result changes, identify the exact dependency path. Next ask whether this exercise would still work with a real gate driving several receivers, a different supply voltage, or a clock with uncertainty. That question may require a data sheet, timing analysis or physical measurement beyond the ideal simulation.

7. Guided exercises

1. Derive and explain. Starting from the definition behind state encoding and illegal-state recovery, construct the smallest nontrivial truth table, bit pattern, timing diagram or state-transition example. Label all relevant conventions. Provide an independent cross-check.

2. Boundary case. Modify the worked example so that one parameter is at its legal minimum and another at its legal maximum. Recompute the expected result and explain whether the nominal assumption still holds.

3. Find the error. Analyze this claim: “An illegal state can be reached by a transient fault or from unknown startup conditions.” Identify a concrete input condition that reveals the problem, describe the output symptom and propose a correction or safety guard.

4. Design choice. Compare two implementations of the lesson's function: a direct gate-level representation and a modular block with explicit interface signals. State their likely advantages in clarity, area, timing or testability without assuming a universal winner.

5. Verification. Write five test vectors (including a boundary and invalid input), expected results and a single assertion or invariant that should hold across the set. Explain how a false-positive test could occur.

8. Reflection and further study

The central question of State encoding and illegal-state recovery is not whether an expression looks familiar, but whether a particular result follows from a complete set of stated assumptions. Recheck the significance of each bit and event, the boundary conditions and the consequences of implementing the abstraction in physical hardware. In design reviews, a clearly documented failed assumption is more valuable than a visually polished schematic with hidden undefined behavior. Before moving on, write a three-sentence summary: what this mechanism guarantees, what it does not guarantee, and the simplest independent test that would reveal a mistake.

§5.4 Traffic-light controller case study

Unit 5, Lesson 4: Traffic-light controller case study

Learning focus: A traffic controller enforces mutual exclusion of conflicting green outputs while satisfying minimum phase dwell requirements. The model must define yellow and all-red intervals.

1. The idea in engineering context

A traffic controller enforces mutual exclusion of conflicting green outputs while satisfying minimum phase dwell requirements. The model must define yellow and all-red intervals. This principle belongs within finite-state machines and controllers. To reason correctly, decide what kind of object each symbol represents: a Boolean truth value, a signed integer, a sample of a waveform, a device threshold, a state bit, or a timed event. An equation may be mathematically valid yet describe the wrong physical or temporal quantity. In a circuit drawing, label all inputs, outputs and control signals with direction and active polarity. If a signal can be unknown, undefined or invalid, describe what the receiving block must do rather than silently treating the signal as zero.

A useful preliminary step is to state the behavior without naming any particular component. For the topic traffic-light controller case study, write an input-output contract in plain language and translate it to a truth table, transition table, numerical equation or timing diagram as appropriate. The same contract should survive translation into a schematic, a behavioral simulation and an HDL module. If an implementation changes the contract, the change must be documented as a new requirement rather than hidden as a convenience.

2. A checkable example

With 10 s main green, 3 s yellow, 1 s all-red, 6 s side green, 3 s yellow, 1 s all-red, the repeating cycle is 24 s. Reproduce this calculation or Boolean reasoning from the definitions, showing intermediate bit patterns and units where relevant. When the example uses an idealized value, state explicitly that the numerical values are illustrative teaching inputs, not component specifications. If it refers to a word length, compute the representable range; if it refers to timing, identify the relevant clock domain, edge and uncertainty terms; and if it refers to a voltage, distinguish absolute maximum ratings from guaranteed digital logic levels.

Alternate check. Explain the expected result qualitatively before computing it. A binary carry chain, parity function, or state transition often has an intuitive conserved property: changing one input can affect a particular output but not every unrelated output. Compare the intuitive expectation with the mathematical answer and resolve discrepancies by writing a smaller exhaustive example. This is especially important when signed interpretation, bit ordering or active-low conventions may reverse an apparently obvious answer.

3. Design method and derivation

Temporal specification. Make a timeline containing clock edges, pre-edge data, post-edge state and observable outputs. Mark all changes that can occur asynchronously. A signal described as valid 'at the edge' is not sufficient unless setup and hold requirements are met in the hardware implementation. Use a reset sequence to establish a known state and test what happens if the enable signal changes close to a clock edge.

The next step is to make the dependence of output on input explicit. Start with the simplest special case: zero data, inactive enable, reset asserted, or minimum address as appropriate. Then test the opposite boundary, including all-one words, maximum carry, saturated load, or final counter state. For traffic-light controller case study, list which of these tests are informative and which are irrelevant. Do not automatically assign meaning to a don't-care or illegal combination. If a simplification assumes certain input codes never occur, describe how the enclosing system enforces that assumption.

Controller reasoning. A design is easier to verify when the number of states and their meaning are explicit. For every state, define outputs, permitted next states and conditions for remaining in place. Write the illegal-state behavior in addition to the nominal transition graph. Test whether a requested action is lost during reset or when two requests arrive together. Safety properties and liveness properties must be stated separately; one forbids bad events, the other asks that desired events eventually occur.

4. Failure modes and limits

Topic-specific pitfall: Directly using asynchronous pedestrian inputs without conditioning can cause erratic transitions. A reliable engineering write-up names the condition that triggers the failure, the observable symptom and the quickest discriminating test. For a functional bug, compare expected and actual truth-table rows; for a timing bug, inspect waveform edges and clock assumptions; for a numeric bug, inspect sign extension and intermediate widths; and for an interface bug, check whether validity and acknowledgement share the same interpretation at each endpoint.

Unit-level model boundary: An FSM can be functionally complete yet physically unsafe if asynchronous inputs or reset removal are unqualified. Avoid extrapolating an ideal gate model into a claim about any particular commercial part. Robustness also requires considering reset entry, temperature-dependent device performance and asynchronous external disturbances whenever they are relevant. If a measured device disagrees with a model, first verify the input stimulus, measurement bandwidth and grounding before declaring the underlying logic theory incorrect.

5. Worked design workflow

1. Specify: write a sentence that defines each input, output and its width; resolve any ambiguous invalid or simultaneous input behavior.

2. Model: select a Boolean expression, transition relation or time equation that captures the defined behavior and state all assumptions.

3. Derive: compute the result for the particular illustrative case above. If there is arithmetic, keep bit widths explicit through every intermediate operation.

4. Cross-check: compare against an independently enumerated case or a direct formula. Document discrepancies rather than adjusting the expected answer to match the implementation.

5. Implement: map the model to gates or synthesizable RTL, leaving enough information to identify clocking, reset and active polarities.

6. Verify: test boundaries and one deliberate fault injection, then record whether the result is logical, simulated, measured or formally proven.

This workflow is intentionally stricter than drawing a plausible diagram. An executable calculator can confirm arithmetic while missing an incorrect interpretation of its inputs. Conversely, a timing waveform can look convincing even if the specification omitted a simultaneous request. A successful solution must connect intent, derivation and independent observation.

6. Laboratory and simulation protocol

Investigation: Prove that incompatible green signals are never simultaneously asserted. Construct a small input matrix containing at least one nominal case, a lower boundary, an upper boundary and a deliberately ambiguous or invalid stimulus. Before running a browser model, write your predicted output and the rule that supports it. Run the experiment, record the output and compare. If the model disagrees with your prediction, determine whether the error is in your rule, your convention, or the model. Explicitly distinguish calculated values from observed electrical measurements; the provided browser apps are not instruments connected to hardware.

Extensions. Repeat the test with an input changed by one bit or one clock cycle. If the result is unchanged, explain which invariance made that possible. If the result changes, identify the exact dependency path. Next ask whether this exercise would still work with a real gate driving several receivers, a different supply voltage, or a clock with uncertainty. That question may require a data sheet, timing analysis or physical measurement beyond the ideal simulation.

7. Guided exercises

1. Derive and explain. Starting from the definition behind traffic-light controller case study, construct the smallest nontrivial truth table, bit pattern, timing diagram or state-transition example. Label all relevant conventions. Provide an independent cross-check.

2. Boundary case. Modify the worked example so that one parameter is at its legal minimum and another at its legal maximum. Recompute the expected result and explain whether the nominal assumption still holds.

3. Find the error. Analyze this claim: “Directly using asynchronous pedestrian inputs without conditioning can cause erratic transitions.” Identify a concrete input condition that reveals the problem, describe the output symptom and propose a correction or safety guard.

4. Design choice. Compare two implementations of the lesson's function: a direct gate-level representation and a modular block with explicit interface signals. State their likely advantages in clarity, area, timing or testability without assuming a universal winner.

5. Verification. Write five test vectors (including a boundary and invalid input), expected results and a single assertion or invariant that should hold across the set. Explain how a false-positive test could occur.

8. Reflection and further study

The central question of Traffic-light controller case study is not whether an expression looks familiar, but whether a particular result follows from a complete set of stated assumptions. Recheck the significance of each bit and event, the boundary conditions and the consequences of implementing the abstraction in physical hardware. In design reviews, a clearly documented failed assumption is more valuable than a visually polished schematic with hidden undefined behavior. Before moving on, write a three-sentence summary: what this mechanism guarantees, what it does not guarantee, and the simplest independent test that would reveal a mistake.

§5.5 Controller verification and invariants

Unit 5, Lesson 5: Controller verification and invariants

Learning focus: An invariant states a property that should hold in every reachable state, while coverage asks whether meaningful states and transitions were exercised.

1. The idea in engineering context

An invariant states a property that should hold in every reachable state, while coverage asks whether meaningful states and transitions were exercised. This principle belongs within finite-state machines and controllers. To reason correctly, decide what kind of object each symbol represents: a Boolean truth value, a signed integer, a sample of a waveform, a device threshold, a state bit, or a timed event. An equation may be mathematically valid yet describe the wrong physical or temporal quantity. In a circuit drawing, label all inputs, outputs and control signals with direction and active polarity. If a signal can be unknown, undefined or invalid, describe what the receiving block must do rather than silently treating the signal as zero.

A useful preliminary step is to state the behavior without naming any particular component. For the topic controller verification and invariants, write an input-output contract in plain language and translate it to a truth table, transition table, numerical equation or timing diagram as appropriate. The same contract should survive translation into a schematic, a behavioral simulation and an HDL module. If an implementation changes the contract, the change must be documented as a new requirement rather than hidden as a convenience.

2. A checkable example

For a two-resource arbiter, the invariant NOT(grant0 AND grant1) ensures exclusion irrespective of request timing. Reproduce this calculation or Boolean reasoning from the definitions, showing intermediate bit patterns and units where relevant. When the example uses an idealized value, state explicitly that the numerical values are illustrative teaching inputs, not component specifications. If it refers to a word length, compute the representable range; if it refers to timing, identify the relevant clock domain, edge and uncertainty terms; and if it refers to a voltage, distinguish absolute maximum ratings from guaranteed digital logic levels.

Alternate check. Explain the expected result qualitatively before computing it. A binary carry chain, parity function, or state transition often has an intuitive conserved property: changing one input can affect a particular output but not every unrelated output. Compare the intuitive expectation with the mathematical answer and resolve discrepancies by writing a smaller exhaustive example. This is especially important when signed interpretation, bit ordering or active-low conventions may reverse an apparently obvious answer.

3. Design method and derivation

Temporal specification. Make a timeline containing clock edges, pre-edge data, post-edge state and observable outputs. Mark all changes that can occur asynchronously. A signal described as valid 'at the edge' is not sufficient unless setup and hold requirements are met in the hardware implementation. Use a reset sequence to establish a known state and test what happens if the enable signal changes close to a clock edge.

The next step is to make the dependence of output on input explicit. Start with the simplest special case: zero data, inactive enable, reset asserted, or minimum address as appropriate. Then test the opposite boundary, including all-one words, maximum carry, saturated load, or final counter state. For controller verification and invariants, list which of these tests are informative and which are irrelevant. Do not automatically assign meaning to a don't-care or illegal combination. If a simplification assumes certain input codes never occur, describe how the enclosing system enforces that assumption.

Controller reasoning. A design is easier to verify when the number of states and their meaning are explicit. For every state, define outputs, permitted next states and conditions for remaining in place. Write the illegal-state behavior in addition to the nominal transition graph. Test whether a requested action is lost during reset or when two requests arrive together. Safety properties and liveness properties must be stated separately; one forbids bad events, the other asks that desired events eventually occur.

4. Failure modes and limits

Topic-specific pitfall: Passing a few nominal waveforms does not establish safe behavior under reset or simultaneous events. A reliable engineering write-up names the condition that triggers the failure, the observable symptom and the quickest discriminating test. For a functional bug, compare expected and actual truth-table rows; for a timing bug, inspect waveform edges and clock assumptions; for a numeric bug, inspect sign extension and intermediate widths; and for an interface bug, check whether validity and acknowledgement share the same interpretation at each endpoint.

Unit-level model boundary: An FSM can be functionally complete yet physically unsafe if asynchronous inputs or reset removal are unqualified. Avoid extrapolating an ideal gate model into a claim about any particular commercial part. Robustness also requires considering reset entry, temperature-dependent device performance and asynchronous external disturbances whenever they are relevant. If a measured device disagrees with a model, first verify the input stimulus, measurement bandwidth and grounding before declaring the underlying logic theory incorrect.

5. Worked design workflow

1. Specify: write a sentence that defines each input, output and its width; resolve any ambiguous invalid or simultaneous input behavior.

2. Model: select a Boolean expression, transition relation or time equation that captures the defined behavior and state all assumptions.

3. Derive: compute the result for the particular illustrative case above. If there is arithmetic, keep bit widths explicit through every intermediate operation.

4. Cross-check: compare against an independently enumerated case or a direct formula. Document discrepancies rather than adjusting the expected answer to match the implementation.

5. Implement: map the model to gates or synthesizable RTL, leaving enough information to identify clocking, reset and active polarities.

6. Verify: test boundaries and one deliberate fault injection, then record whether the result is logical, simulated, measured or formally proven.

This workflow is intentionally stricter than drawing a plausible diagram. An executable calculator can confirm arithmetic while missing an incorrect interpretation of its inputs. Conversely, a timing waveform can look convincing even if the specification omitted a simultaneous request. A successful solution must connect intent, derivation and independent observation.

6. Laboratory and simulation protocol

Investigation: Create tests for reset, starvation, rapid request toggling and illegal state recovery. Construct a small input matrix containing at least one nominal case, a lower boundary, an upper boundary and a deliberately ambiguous or invalid stimulus. Before running a browser model, write your predicted output and the rule that supports it. Run the experiment, record the output and compare. If the model disagrees with your prediction, determine whether the error is in your rule, your convention, or the model. Explicitly distinguish calculated values from observed electrical measurements; the provided browser apps are not instruments connected to hardware.

Extensions. Repeat the test with an input changed by one bit or one clock cycle. If the result is unchanged, explain which invariance made that possible. If the result changes, identify the exact dependency path. Next ask whether this exercise would still work with a real gate driving several receivers, a different supply voltage, or a clock with uncertainty. That question may require a data sheet, timing analysis or physical measurement beyond the ideal simulation.

7. Guided exercises

1. Derive and explain. Starting from the definition behind controller verification and invariants, construct the smallest nontrivial truth table, bit pattern, timing diagram or state-transition example. Label all relevant conventions. Provide an independent cross-check.

2. Boundary case. Modify the worked example so that one parameter is at its legal minimum and another at its legal maximum. Recompute the expected result and explain whether the nominal assumption still holds.

3. Find the error. Analyze this claim: “Passing a few nominal waveforms does not establish safe behavior under reset or simultaneous events.” Identify a concrete input condition that reveals the problem, describe the output symptom and propose a correction or safety guard.

4. Design choice. Compare two implementations of the lesson's function: a direct gate-level representation and a modular block with explicit interface signals. State their likely advantages in clarity, area, timing or testability without assuming a universal winner.

5. Verification. Write five test vectors (including a boundary and invalid input), expected results and a single assertion or invariant that should hold across the set. Explain how a false-positive test could occur.

8. Reflection and further study

The central question of Controller verification and invariants is not whether an expression looks familiar, but whether a particular result follows from a complete set of stated assumptions. Recheck the significance of each bit and event, the boundary conditions and the consequences of implementing the abstraction in physical hardware. In design reviews, a clearly documented failed assumption is more valuable than a visually polished schematic with hidden undefined behavior. Before moving on, write a three-sentence summary: what this mechanism guarantees, what it does not guarantee, and the simplest independent test that would reveal a mistake.