Digital System Design using FSMs
Description
Explore this concise guide perfect for digital designers and students of electronic engineering who work in or study embedded systems
Digital System Design using FSMs: A Practical Learning Approach delivers a thorough update on the author's earlier work, FSM-Based Digital Design using Verilog HDL. The new book retains the foundational content from the first book while including refreshed content to cover the design of Finite State Machines delivered in a linear programmed learning format. The author describes a different form of State Machines based on Toggle Flip Flops and Data Flip Flops.
The book includes many figures of which 15 are Verilog HDL simulations that readers can use to test out the design methods described in the book, as well as 19 Logisim simulation files with figures. Additional circuits are also contained within the Wiley web folder. It has tutorials and exercises, including comprehensive coverage of real-world examples demonstrated alongside the frame-by-frame presentations of the techniques used.
In addition to covering the necessary Boolean algebra in sufficient detail for the reader to implement the FSM based systems used in the book, readers will also benefit from the inclusion of:
* A thorough introduction to finite-state machines and state diagrams for the design of electronic circuits and systems
* An exploration of using state diagrams to control external hardware subsystems
* Discussions of synthesizing hardware from a state diagram, synchronous and asynchronous finite-state machine designs, and testing finite-state machines using a test-bench module
* A treatment of the One Hot Technique in finite-state machine design
* An examination of Verilog HDL, including its elements
* An analysis of Petri-Nets including both sequential and parallel system design
Suitable for design engineers and senior technicians seeking to enhance their skills in developing digital systems, Digital System Design using FSMs: A Practical Learning Approach will also earn a place in the libraries of undergraduate and graduate electrical and electronic engineering students and researchers.
More details
Other editions
Additional editions
Person
Content
- Cover
- Title Page
- Copyright Page
- Contents
- Preface
- Acknowledgements
- About the Companion Website
- Guide to Supplementary Resources
- Chapter 1 Introduction to Finite State Machines
- 1.1 Some Notes on Style
- Chapter 2 Using FSMs to Control External Devices
- 2.1 Introduction
- Chapter 3 Introduction to FSM Synthesis
- 3.1 Introduction
- 3.2 Tutorials Covering Chapters 1, 2, and 3
- 3.2.1 Binary data serial transmitter FSM
- 3.2.2 The high low FSM system
- 3.2.3 The clocked watchdog timer FSM
- 3.2.4 The asynchronous receiver system clocked FSM
- Chapter 4 Asynchronous FSM Methods
- 4.1 Introduction to Asynchronous FSM
- 4.2 Summary
- 4.3 Tutorials
- 4.3.1 FSM motor with fault detection
- 4.3.2 The mower in four and two states
- Chapter 5 Clocked One Hot Method of FSM Design
- 5.1 Introduction
- 5.2 Tutorials on the Clocked one Hot FSM Method
- 5.2.1 Seven-state system clocked one hot method
- 5.2.2 Memory tester FSM
- 5.2.3 Eight-bit sequence detector FSM
- Chapter 6 Further Event-Driven FSM Design
- 6.1 Introduction
- 6.2 Conclusions
- Chapter 7 Petri Net FSM Design
- 7.1 Introduction
- 7.2 Tutorials Using Petri Net FSM
- 7.2.1 Controlled shared resource Petri nets
- 7.2.2 Serial clock-driven Petri net FSM
- 7.2.3 Using asynchronous (event-driven) design with Petri nets
- 7.3 Conclusions
- Appendix A1: Boolean Algebra
- A1.1 Basic Gate Symbols
- A1.2 The Exclusive OR and Exclusive NOR
- A1.3 Laws of Boolean Algebra
- A1.3.1 Basic OR rules
- A1.3.2 Basic AND rules
- A1.3.3 Associative and commutative laws
- A1.3.4 Distributive laws
- A1.3.5 Auxiliary rule for static 1 hazard removal
- A1.3.6 Consensus theorem
- A1.3.7 The effect of signal delay in logic gates
- A1.3.8 De-Morgan's theorem
- A1.4 Examples of Applying the Laws of Boolean Algebra
- A1.4.1 Converting AND-OR to NAND
- A1.4.2 Converting AND-OR to NOR
- A1.4.3 Logical adjacency rule
- A1.5 Summary
- 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.5.1 The Logisim top level menu items
- 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.8.1 Using Logisim with the truth table approach
- A2.9 Using Logisim with the Truth Table Approach
- A2.9.1 Useful note
- A2.10 Summary
- 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.10.1 The equations
- A3.11 Summary
- Appendix A3: Counters, Shift Registers, Input, and Output with an FSM
- A4.1 Introduction
- A4.2 The Single-Pulse/Multiple-Pulse Generator with Memory FSM
- A4.3 The Memory Tester FSM Revisited
- A4.4 Summary
- Appendix A5: Programming a Finite State Machine
- A5.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
- Appendix A6: The Rotational Detector Using Logisim Simulator with Sub-Circuits
- A6.1 Using the Two-State Diagram Arrangement
- Bibliography
- Index
- EULA
1
Introduction to Finite State Machines
This chapter (like all other chapters) is written in the form of a linear frame, programmed learning text. This is to help you learn the basic skills required to design clocked finite state machines (FMSs) so that you can develop your own designs based on traditional T flip-flops and D flip-flops. Later, other techniques will be introduced, such as 'one hot' and 'asynchronous finite state machines', but these will be developed along the same lines as the work covered in this chapter.
The text is organized into 'frames'. Each frame follows on consecutively from the previous one, but at times you may be redirected to other frames, depending upon your response to the questions you are asked. Do not cheat, but follow the frames as indicated.
1.1 SOME NOTES ON STYLE
Bold denotes questions for you to answer to check your understanding of the material, highlights important points, or indicates an aside when further ideas are presented.
Please read this chapter first, and attempt all the questions before moving on to the later chapters. Note that the book can be read as a textbook. The programmed aspect of the book makes it more suitable for individuals to read and learn in their own time.
Frame 1.1 What is a Finite State Machine?
A finite state machine (FSM) is a digital sequential circuit that can follow a number of predefined states under the control of one or more inputs. Each state is a stable entity that the machine can occupy. It can move from this state to another state under the control of an outside world input.
Figure 1.1 Block diagram of an FSM-based application.
In Figure 1.1, we see an FSM with three outside world inputs (p, q, and the clock) and three outside world outputs (X, Y, and Z). Note some FSMs have a clock input; those that don't belong to a type of FSM called 'asynchronous FSM'. However, this chapter deals with the more usual synchronous FSM, which do have a clock input. Only Chapter 4 and Chapter 6 will look at asynchronous FSM.
Synchronous FSM can move between states only if a clock pulse occurs.
Task:Draw a block diagram for an FSM with five inputs (x, y, z, t, and a clock) and with two outputs (P and Q).
When you have done this, turn to Frame 1.2.
Frame 1.2
The FSM with five inputs (x, y, z, t, and a clock) and two outputs (P and Q) is shown in Figure 1.2.
If you did not get this answer, go back and re-read Frame 1.1. Don't worry about using a mixture of both upper- and lower-case letters here; the only thing that matters is that the same letters are used.
Each state of the FSM needs to be identifiable. This is achieved by using a number of internal flip-flops within the FSM block. An FSM with four states would require two flip-flops since two flip-flops can store 22 = 4 state numbers.
Figure 1.2 Block diagram with five inputs and two outputs.
Each state has a unique state number, and states are usually assigned numbers, such as s0 (state 0), s1, s2, and s3 (for a four-state example).
As you can see, the rule here is 2number of flip-flops.
So an FSM with 13 states would require 24 flip-flops (i.e. 15 states of which 13 are used in the FSM and states 14 and 15 remain unused.
How many flip-flops would be required for an FSM using 34 states?
What would the state numbers be for this FSM?
When you have answered these questions, turn to Frame 1.3.
Frame 1.3
The answer to the previous question is:
In general: 24 = 16 states, 25 = 32 states, 26 = 64 states, 27 = 128 states, and so on.
What would the state number be for this FSM?
Answer:
The unused states would be s34 through to s63.
Note that the states run through from s0 to sn-1, for n states.
As well as containing flip-flops to uniquely define the individual states of the FSM, there is also combinational logic, which defines the outside world outputs. In addition, the outside world inputs connect to combinational logic, which supplies the flip-flops' inputs.
Please turn to Frame 1.4.
Frame 1.4
Figure 1.3 illustrates the internal architecture for a Mealy FSM.
Figure 1.3 Block diagram of a Mealy state machine structure.
Note the feed forward paths between the outside world inputs and the input to the output decoder.
The figure shows that the FSM has a number of inputs that connect to the next state decoder (combinational) logic. The Q outputs of the memory element flip-flops connect to the output decoder logic, which in turn connects to the outside world outputs via the output decoder.
The flip-flop outputs are used as next state inputs to the next state decoder, and it is these that determine the next state that the FSM will move to. Once the FSM has moved to this next state, its flip-flops acquire a new present state as dictated by the next state decoder.
Note that some of the outside world inputs connect directly to the output decoder logic. This is the main feature of the Mealy type of FSM. This affects the outputs of the FSM.
Please turn to Frame 1.5.
Frame 1.5
Another architectural form for an FSM is the Moore FSM, as shown in Figure 1.4.
Figure 1.4 Block diagram of a Moore state machine structure.
This FSM differs from the Mealy FSM in that it does not have the feed forward paths.
This type of FSM is very common. Note that the outside world outputs are a function of the flip-flop outputs only (unlike the Mealy FSM architecture where the outside world outputs are a function of flip-flop outputs and some outside world inputs).
We will be using both Moore and Mealy FSM in our designs.
Please turn to Frame 1.6.
Frame 1.6
Complete the following:
- A Moore FSM differs to that of a Mealy FSM in that it has.
- This means that the Moore FSM outputs depend on.
- Whilst the Mealy FSM outputs can depend upon.
If you cannot complete the above sentences, go back and read Frame 1.4 and Frame 1.5.
When you have completed these questions, please go to Frame 1.7.
Frame 1.7
If we look at the Moore FSM architecture again and remove all of the outside world inputs apart from the clock, and we also remove the output decoding logic, we are left with a very familiar architecture. This is shown in Figure 1.5.
Figure 1.5 Block diagram of a Class C state machine structure.
This architecture is in fact the synchronous counter the reader may have already seen in previous studies. Note that an up/down counter would have the additional outside world input 'up/down', which would be used to control the direction of counting.
The flip-flop outputs in this architecture are used to connect directly to the outside world.
Please move on to Frame 1.8.
Frame 1.8
Historically, two types of state diagrams have evolved, one for the design of the Mealy FSM the other for the design of the Moore FSM. The two are known as 'Mealy state diagrams' and 'Moore state diagrams'.
These days we use a more general type of state diagram, which can be used to design both the Mealy and Moore type of FSM. This is the type of state diagram we use throughout this book. As you will learn, it allows you to build a lot of ideas into the FSM diagram.
Figure 1.6 shows each state of the FSM and the transitions to and from that state to other states.
The states are usually drawn as circles (but some people like to use a square box).
The transitions between states are shown as an arrowed line connected between the states.
Figure 1.6 Transition between states.
In addition to the transitional line between states, there is an input signal name.
The right-angled lines _| represent the clock input (in this case a rising edge 0 to 1) (Figure 1.7).
Figure 1.7 Transition with and without outside world inputs.
In Figure 1.7, the transition between states s0 and s1 will occur at the clock pulse in the upper state...
