Title: EE4218_EHSD / Sequential Logic Optimisation
On every note of this deck, unless a note says otherwise:
Title: EE4218_EHSD::Sequential Logic Optimisation
Logo: tum_logo.png

Front: Which two models are commonly used for modeling synchronous circuits?
Back: - State-based model
- Structural model

Front: The state-based model has ______ notion of state, and ______ notion of area and delay.
Back: The state-based model has explicit notion of state, and implicit notion of area and delay.

Front: The structural model has ______ notion of state, and ______ notion of area and delay.
Back: The structural model has implicit notion of state, and explicit notion of area and delay.

Front: What are some optimisations for the state-based model?
Back: - State minimization
- State encoding

Front: What are some optimisations for the structural model?
Back: - Retiming
- Synchronous logic transformations

Front: What is the typical flow for modeling synchronous circuits?
Back: 1. FSM specification
2. State minimization
3. State encoding
4. Combinational (next-state, output) logic optimisation 5, State extraction (for verification)
5. Retiming and synchronous transformations

Front: What kind of FSM is this?
Back: A Mealy Machine.

Front: What kind of FSM is this?
Back: A Moore Machine.

Front: Describe the problem "State Minimization"!
Back: Objective is to reduce the number of states and hence the area

Front: What is a completely-specified finite-state machine?
Back: No don't care conditions

Front: What happens if a FSM is not completely-specified?
Back: - Unspecified transitions and/or outputs
- Intractable problem

Front: Define "equivalent states".
Back: Two states are equivalent if and only if:
- They lead to identical outputs and
- Their next-states are equivalent

Front: What are the three steps in "stepwise partition refinement"
Back: 1. Initially, all states in the same partition block
2. Iteratively refine partition blocks
3. At convergence partition blocks identify equivalent states

Front: How is the initial partition in the refinement procedure formed?
Back: States belong to the same block when outputs are the same for any input.

Front: How is the next partition in the refinement procedure formed?
Back: States belong to the same block if they were previously in the same block and their next states are in the same block for any input.

Front: When does the refinement procedure end?
Back: When convergence is reached.

Front: Perform the "stepwise partition refinement" algorithm:

Front: Explain how the Implication Chart Method works.
Back: 1. Cross out those cells corresponding to state pairs which are I/O incompatible
2. Write down the conditions for equivalence for other pairs
3. Cross out more cells if any of the indexed chart entries are already cross out
4. Repeat (3) until no more cells can be crossed out
5. Pairs corresponding to cells which are not crossed out are equivalent

Front: How are conditions for equivalence for other pairs written down in the Implication Chart Method?
Back: - Conditions are called implications
- Example : S3 and S4 are equivalent only if S2-S4 are equivalent and S1-S5 are equivalent

Front: Define "compatible states".
Back: Two states are compatible if and only if:
- They lead to identiical outputs if specified
- Their next states are compatible

Front: Is Compatibility transitive?
Back: No, it is not an equivalence relation.

Front: How to minimise incompletely-specified FSMs?
Back: Find a minimum number of partition blocks such that:
- All states are covered
- All implications are satisfied

Front: What is State Encoding?
Back: Process of assigning bit vectors to each symbolic state.

Front: State Encoding maps a ______ representation into a _____ one.
Back: State Encoding maps a state-based representation into a structural one.

Front: Is the optimal solution of state encoding tractable?
Back: No. it is intractable.

Front: What are some non-optimal strategies for state encoding?
Back: - Sequential
- Random
- One-Hot
- Heuristic

Front: What are advantages of One-hot Encoding?
Back: - Simple to encode
- Combinational logic is usually small
- Suitable for FPGAs, as proper initialisation is needed

Front: What are disadvantages of One-hot Encoding?
Back: - Proper initialisation needed
- Large number of states will need large number of FFs

Front: What are some heuristics for State Encodings?
Back: - Adjacent codes to states that:
  - share a common next-state
  - share a common predecessor (ancestor) state
  - have a common output behaviour
- Gray and Johnson codes

Front: What is State Extraction?
Back: Recover state information from a structural moel

Front: What are vertices in a Synchronous network graph?
Back: SOP/POS expressions <-> Gates

Front: What are edges in a Synchronous network graph?
Back: Dependencies <-> Nets

Front: What are edge weights in a Synchronous network graph?
Back: Synchronous delays <-> Registers

Front: What is Retiming?
Back: Change register postions -> Change weights on graph

Front: Explain Relaxation-based Retiming Algorithm!
Back: 1. Find vertices with data ready > φ
2. Retime these vertices by 1. Make sure that no edge has a negative weight
3. Repeat until predicate from (1) is false for all v.
4. If a legal retiming is not found in |V] iterations, then no legal retiming exists for that φ