Peter D. Minns - Digital System Design using FSMs

1 Cover

2 Title Page

3 Copyright Page

4 Preface

5 Acknowledgements

6 About the Companion Website

7 Guide to Supplementary Resources

8 1 Introduction to Finite State Machines 1.1 SOME NOTES ON STYLE

9 2 Using FSMs to Control External Devices2.1 INTRODUCTION

10 3 Introduction to FSM Synthesis 3.1 INTRODUCTION 3.2 TUTORIALS COVERING CHAPTERS 1, 2, AND 3

11 4 Asynchronous FSM Methods4.1 INTRODUCTION TO ASYNCHRONOUS FSM 4.2 SUMMARY 4.3 TUTORIALS

12 5 Clocked One Hot Method of FSM Design5.1 INTRODUCTION 5.2 TUTORIALS ON THE CLOCKED ONE HOT FSM METHOD

13 6 Further Event‐Driven FSM Design6.1 INTRODUCTION 6.2 CONCLUSIONS

14 7 Petri Net FSM Design7.1 INTRODUCTION 7.2 TUTORIALS USING PETRI NET FSM 7.3 CONCLUSIONS

15 Appendix A1: Boolean Algebra A1.1 BASIC GATE SYMBOLS A1.2 THE EXCLUSIVE OR AND EXCLUSIVE NOR A1.3 LAWS OF BOOLEAN ALGEBRA A1.4 EXAMPLES OF APPLYING THE LAWS OF BOOLEAN ALGEBRA A1.5 SUMMARY

16 Appendix A2: Use of Verilog HDL and Logisim to FSM A2.1 THE SINGLE‐PULSE GENERATOR WITH MEMORY CLOCK‐DRIVEN FSM A2.2 TEST BENCH MODULE AND ITS PURPOSE A2.3 USING SYNAPTICAD SOFTWARE A2.4 MORE DIRECT METHOD A2.5 A VERY SIMPLE GUIDE TO USING THE LOGISIM SIMULATOR A2.6 USING FLIP‐FLOPS IN A CIRCUIT A2.7 EXAMPLE SINGLE‐PULSE FSM A2.8 HOW TO USE THE SIMULATOR TO SIMULATE THE SINGLE‐PULSE FSM A2.9 USING LOGISIM WITH THE TRUTH TABLE APPROACH A2.10 SUMMARY

17 Appendix A3: Counters, Shift Registers, Input, and Output with an FSM A3.1 BASIC DOWN SYNCHRONOUS BINARY COUNTER DEVELOPMENT A3.2 EXAMPLE OF A FOUR‐BIT SYNCHRONOUS UP COUNTER WITH T TYPE FLIP‐FLOPS A3.3 PARALLEL LOADING COUNTERS – USING T FLIP‐FLOPS A3.4 USING D FLIP‐FLOPS TO BUILD PARALLEL LOADING COUNTERS A3.5 SIMPLE BINARY UP COUNTER WITH PARALLEL INPUTS A3.6 CLOCK CIRCUIT TO DRIVE THE COUNTER (AND FSM) A3.7 COUNTER DESIGN USING DON’T CARE STATES A3.8 SHIFT REGISTERS A3.9 DEALING WITH INPUT AND OUTPUT SIGNALS USING FSM A3.10 USING LOGISIM TO WORK WITH LARGER FSM SYSTEMS A3.11 SUMMARY

18 Appendix A4: Finite State Machines Using Verilog Behavioural ModeA4.1 INTRODUCTION A4.2 THE SINGLE‐PULSE/MULTIPLE‐PULSE GENERATOR WITH MEMORY FSM A4.3 THE MEMORY TESTER FSM REVISITED A4.4 SUMMARY

19 Appendix A5: Programming a Finite State MachineA5.1 INTRODUCTION A5.2 THE PARALLEL LOADING COUNTER A5.3 THE MULTIPLEXER A5.4 THE MICRO INSTRUCTION A5.5 THE MEMORY A5.6 THE INSTRUCTION SET A5.7 SIMPLE EXAMPLE: SINGLE‐PULSE FSM A5.8 THE FINAL EXAMPLE A5.9 THE PROGRAM CODE A5.10 RETURNING UNUSED STATES VIA OTHER TRANSITION PATHS A5.11 SUMMARY

20 Appendix A6: The Rotational Detector Using Logisim Simulator with Sub‐Circuits A6.1 USING THE TWO‐STATE DIAGRAM ARRANGEMENT

21 BibliographyREFERENCES FURTHER READING

22 Index

23 End User License Agreement

1 Appendix A3Table A3.1 The binary down counter.

1 Chapter 1 Figure 1.1 Block diagram of an FSM‐based application. Figure 1.2 Block diagram with five inputs and two outputs. Figure 1.3 Block diagram of a Mealy state machine structure. Figure 1.4 Block diagram of a Moore state machine structure. Figure 1.5 Block diagram of a Class C state machine structure. Figure 1.6 Transition between states. Figure 1.7 Transition with and without outside world inputs. Figure 1.8 Outside world input between states. Figure 1.9 Placement of outside world outputs. Figure 1.10 The block diagram for the state diagram shown in Figure 1.9. Figure 1.11 Block diagram of single pulse with memory FSM. Figure 1.12 State diagram for single pulse with memory FSM. Figure 1.13 State diagram for single‐pulse generator with memory and dummy s... Figure 1.14 Block diagram for the FSM. Figure 1.15 State diagram of single‐pulse generator with a multipulse featur... Figure 1.16 Block diagram showing secondary state variables in the FSM. Figure 1.17 State diagram with Mealy output P . Figure 1.18 Timing diagram showing Moore and Mealy outputs. Figure 1.19 Development of a 101 pattern generator sequence. Figure 1.20 Complete state diagram for the 101 pattern generator. Figure 1.21 Modified state diagram with output P as a Mealy output. Figure 1.22 State diagram with Mealy P output in s3. Figure 1.23 Timing diagram showing the effect of input x on output P .

2 Chapter 2 Figure 2.1 A timing module. Figure 2.2 Wait state sequence to control the timing module. Figure 2.3 Block diagram showing how to use the timing module with an RC tim... Figure 2.4 State diagram showing how to use the timing module. Figure 2.5 Block diagram controlling an ADC from a state diagram. Figure 2.6 Block diagram for a small DAS. Figure 2.7 Control of a memory device note negating circles at /CS,/W,/R. Figure 2.8 Timing of the control of a memory device. Figure 2.9 T1 to T4 timing stages. Figure 2.10 Using FSM to control the writing of data to a memory device. Figure 2.11 State diagram of the DAS.Figure 2.12a Block diagram for the two D detector FSM.Figure 2.12b State diagram to detect d twice.Figure 2.13 Block diagram to detect a 1010 sequence.Figure 2.14 Timing diagram showing the 1010 d input and its effect on the P ...Figure 2.15 A 110 sequence detector FSM.Figure 2.16 A possible 110 detector attempt.

3 Chapter 3Figure 3.1 T type flip‐flop using exclusive OR and a D type flip‐flop.Figure 3.2 State diagram for the single‐pulse generator with memory having M...Figure 3.3 A different state diagram using T type flip‐flops.Figure 3.4 Repeated diagram.Figure 3.5 D type flip‐flop with its characteristics.Figure 3.6 Timing showing behaviour of D type flip‐flop.Figure 3.7 The effect of a glitch.Figure 3.8 A complete example.Figure 3.9 State diagram with single/multiple‐pulse FSM.Figure 3.10 State diagram of Figure 3.9 again.Figure 3.11 Different ABCD transitions in a two‐way branch. Figure 3.12 Some more examples to try.Figure 3.13 A state diagram with two two‐way branches.Figure 3.14 The effect of asynchronous and synchronous resets.Figure 3.15 Complete design circuit for the FSM.Figure 3.16 Repeat of completed circuit showing P output with and without cl...Figure 3.17 This example has an x input for Mealy output L .Figure 3.18 Use this to complete the design equations.Figure 3.19 The circuit with lower AND gate to allow reset of flip‐flop B .Figure 3.20 The effect of Moore/Mealy outputs for P and L .Figure 3.21 CS and W outputs using De‐Morgan’s rule.Figure 3.22 How W and R are used.Figure 3.23 Block diagram of the binary data serial transmitter.Figure 3.24 State diagram for binary data serial transmitter.Figure 3.25 With additional dummy state s7.Figure 3.26 Simulation of the binary data serial transmitter.Figure 3.27 The high low FSM system.Figure 3.28 State diagram of the high‐low system.Figure 3.29 Simulation of the high‐low system.Figure 3.30 The clocked watchdog timer.Figure 3.31 State diagram of the watchdog timer.Figure 3.32 Simulation of the watchdog timer.Figure 3.33 Data packet protocol.Figure 3.34 Block diagram of the asynchronous receiver.Figure 3.35 The state diagram for an asynchronous receiver.Figure 3.36 Simulation of the asynchronous receiver.

4 c04Figure 4.1 Event and clocked block diagram and state diagram.Figure 4.2 Event and clocked block diagram and state diagram.Figure 4.3 General event cell.Figure 4.4 Inputs to the event cell.Figure 4.5 Inputs and present state output of event cell.Figure 4.6 Circuit of event cell using characteristic equation.Figure 4.7 An example of the complete method.Figure 4.8 The example again.Figure 4.9 Event cell to help form B equation.Figure 4.10 Using the short cut method.Figure 4.11 Replacing s3 to s0 transition sp with /st.Figure 4.12 A different example using the short cut method.Figure 4.13 Example with Mealy output