State Minimization and Unused States in Digital System Design

During the design of digital systems, it is crucial to minimize the number of states to optimize storage elements. This process involves identifying and merging redundant states while ensuring consistent outputs and transitions. By reusing and merging states effectively, unnecessary complexities can be eliminated, leading to more efficient and streamlined digital systems.

• State Minimization
• Digital Systems
• Design Optimization
• Redundant States

zclaf Follow

Uploaded on Sep 11, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. ECE 352 State Minimization and Unused States Digital System Fundamentals State Minimization Unused States 1 1 1

2. State Minimization Sometimes during design, we might think we need more states than we actually do Adding a state can increase # of storage elements: # FFs ceil(log2(# states)) Eliminating redundant states: Reuse states when possible (loop back) Merge states when appropriate (same outgoing transitions and same outputs) After each merge, also need to check if the newly merged state can be merged with any others Remember only OUTGOING transitions matter! State Minimization and Unused States 2 2 2

3. Identifying Merge-able States Moore Machine: Merge states w/same outputs & next state State Minimization and Unused States A=0 A=0 To merge two states: Their outputs must match Arrows must go to the same places for the same values (same next state ) Remember to match outgoing transitions! K L 0 0 A=1 A=0 A=1 M 1 A=1 reset 3 3 3

4. Identifying Merge-able States Moore Machine: Merge states w/same outputs & next state Same transition for A=0 Same outputs State Minimization and Unused States A=0 A=0 A=0 To merge two states: Their outputs must match Arrows must go to the same places for the same values (same next state ) Remember to match outgoing transitions! K L KL 0 0 0 A=1 A=1 A=0 A=1 M M A=0 1 1 A=1 reset A=1 reset FSM with merged KL state Same transition for A=1 4 4 4

5. Identifying Merge-able States Mealy Machine: Merge states w/same next state / output transitions State Minimization and Unused States 0/0 0/1 X Y To merge two states: Arrows must go to the same places for the same input values Outputs must match on arrows also Remember to match outgoing transitions! 1/0 0/1 1/0 1/0 Z reset 5 5 5

6. Identifying Merge-able States Mealy Machine: Merge states w/same next state / output transitions Same transition for A=0 Same outputs on A=1 transitions State Minimization and Unused States 0/0 0/0 0/1 X Y To merge two states: Arrows must go to the same places for the same input values Outputs must match on arrows also Remember to match outgoing transitions! Y 0/1 1/0 0/1 1/0 1/0 XZ Z 1/0 reset reset 1/0 Same outputs on A=0 transitions Same transition for A=1 FSM with merged XZ state 6 6 6

7. Unused States With n flip-flops, the FSM will have 2n states Specification may not require all 2n states, so we have a choice: Consider those states don t-care situations Benefit: simplifies the logic Downside: what if we transition to an unused state? Assign a next state value to all states Benefit: can reset or signal an error Downside: requires more logic State Minimization and Unused States 7 7 7

8. Unused States Example State Minimization and Unused States CURR IN NEXT OUT Q1Q0 A D1 D0 Y 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 X X 1 X X 1 X X 8 8 8

9. Unused States Example State Minimization and Unused States 0/0 CURR IN NEXT OUT Q1Q0 A D1 D0 Y 11 0 0 0 0 1 0 1/1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 D0 = Q1 A + Q1 A D1 = Q0 A Y = Q1 A 1 1 1 0 1 1 1 0 1 1 X X X X 1 1 1 X X 1 X X X 1 X X 0 0 X 0 9 9 9

10. Unused States Example State Minimization and Unused States 0/0 11 1/1 In this example, we don t care what happens if we get to the 11 state But we may want to know what happens If our circuit goes into this state, we need to debug it! 10 10 10

11. Dont-Cares Don t-cares can express that a particular variable does not affect a transition Similar to shorthand notation where we use X in an input column of a truth table 1X Inputs: A B Output: Y State Minimization and Unused States X0 M K 0 0 X1 0X reset Example: In state K, only care about A, and in state M, only care about B In this case, each arrow represents two transitions Don t-cares can also be used to simplify output equations, but that is less common 11 11 11

12. ECE 352 State Minimization and Unused States Digital System Fundamentals State Minimization Unused States 12 12 12