Finite State Machine and
The Design of Sequential Circuits
◆Finite State Machine (FSM)
Copyright By PowCoder代写 加微信 powcoder
– Concept of the FSM model
– Analytic tools for FSM: how to describe an FSM?
◆Design of sequential circuits
– Use FSM as the Model
– Illustrate the design process through examples
Example from Last Lecture ◆3-bit Synchronous Counter
– The counter will count through 000, 001, … , 111, then get back to 000
– Each count (e.g., 001) is a state of the counter (machine)
– The number of possible states is finite
– This 3-bit Synchronous Counter is an example of Finite State Machine
Concept of FSM
◆FSM is an abstract model to describe real-world systems
– It uses states to represent the situations that the system is in
– It specifies how the states of the system would change based on the external input, and how the system would produce external output accordingly
– The 3-bit Synchronous Counter is a special case – it does not have external input and output
Concept of FSM
◆FSM is an abstract model to describe real-world systems
– However, the 3-bit Synchronous Counter did demonstrate an essential part of FSM – the memory component to store the state
Concept of FSM
(an external input)
(an external output)
Change state
Change state
(an external output)
(an external input)
happy state
Formal Model of FSM ◆FSM=(S,I,O,π)
– S: the finite set of states
– I: the finite set of external inputs
– O: the finite set of external outputs
– π: state transition function: define the relations among input, output, current state, next state
Formal Model of FSM
◆Two important relations for FSM
– Next state = external input + current state (i.e., the next state depends on the current state and the external input)
– External output = external input + current state (note: not exactly as this; detailed later)
Formal Model of FSM
memory compoennt
memory compoennt: store the state of the machine
combinational logic: relates the current state, external input and output, next state
Two Sub-Models: Mealy Machine vs. Moore Machine
Mealy Machine
Moore Machine
Output and next state depend on both current state and input
Next state depends on both current state and input However, output depends only on current state
How to Represent FSM
◆There are two basic approaches
– State diagram
– State table
– Key: represent the relations among current state, input and next state, output
– Know how to transform between state diagram and state table
State Diagram
◆Circles: represent states
– Labelled with S_k to denote the state (or a binary encoding) ◆Directed arcs: represent the transitions between states
– Labelled with input/output for that state transition
Two circles: initial state
State Diagram
Example: the current state is S_k, given an external input a, the state will transit to the next state S_j, and the external output is p
Encoding of states: we ususally use binary numbers to encode the states; for example, if there are four states: S_0 (00), S_1 (01), S_2(10), and S_3(11).
State Diagram
◆Some restrictions on state diagram
– Time is discretized: use clock signal to control the timming of the transitioning of states (synchronous!) — we usually use time t and t+1 to denote the timing for the current state and next state
– FSM can only be in one state at a time — therefore, only in one state (or one circle) at a time
State Diagram
◆Mealy machine and Moore machine can be
labelled differently
– Mealy machine: label directed arcs with input/output for that state transition
– Moore machine: since output depends only on state, we can label directed arcs with input for that state transition, and label state circles with S_k/output
S_k/output
State Diagram Example
State diagram is a clear visualization of FSM; but it is not that convinient for computation – we use an alternative, which is state table
State Table
Different input values (example: 2 input values)
Current State
Next State
Current State
Next State
Different states (example: 4 states)
State Table Example
Current State
Next State
Fill in the blanks in class
A Short Summary
◆FSM = (States, Inputs, Outputs, State Transition
– State diagram
– State table
– We know these tools to describe it, but what’s the analytical task?
The Essential Analytical Task for FSM
◆Given state diagram/state table, derive the functions
that specify the relations among next state, output,
current state, and input
– Next state = f (current state, input)
– Output = g (current state, input)
– The design of sequential circuits relies on the above two functions
◆Approach: Truth Table and Karnaugh Map
Example: Pattern Detector
◆Design a machine that will detect a specific bit pattern
– It receives bit stream
– It has one output Z: if the bit pattern appears in the bit stream,
the output Z = 1; otherwise, Z = 0
Discrete time
Input bit stream
Detect the bit pattern 1101
Modelling the Problem using FSM ◆States and States Transitions
– We use the following states to model the possible situations that the machine is in (detect pattern 1101)
– S0: the initial state
– S1: the first desired symbol (1) is detected
– S2: the desired sub-pattern 11 is detected
– S3: the desired sub-pattern 110 is detected
– Intuition: we want to record the situations that will lead to the target pattern 1101
Modelling the Problem using FSM
◆States and States Transitions (pattern 1101)
Worth to note:
(1) the transitions from S0 to S1 to S2 to S3 (when desired bit is received)
(2) For most of the cases when undesired bit is received, it goes back to S0 (restart the detection again) (3) Some special cases: S2 goes back to S2 (11 when received 1); S3 goes to S1 (110 when received 1)
This process needs case-by-case careful design
From State Diagram to Functions ◆Approach: use Truth Table and Karnaugh Map
– Encode the states, input, and output
– S0 (00), S1(01), S2(10), S3(11)
– Construct the state diagram (it is actually a truth table) – Now you can use K-map
From State Diagram to Functions
In the State Diagram (truth table):
(1) we use two bits P1，P0 to denote the current state; use N1, N0 for the next state
(2) (P1,P0,X) are the variables, N1, N0, Z are the function values
(3) Given a combination of (P1,P0,X), we need to find the value for N1, N0, Z from the state diagram
From State Diagram to Functions
The two important relations: Next state = current state + input Output = current state + input
We can then construct the circuits using memory components and combinational logic
A Short Summary
◆Using FSM as the Model and Analytical Tools to solve real-world problems
– Modelling the problem: define the states and transitioning of states (the core; not an easy task)
– Deriving the functions (engineering work) – From functions to circuit implementation
◆Finite State Machine (FSM) – Concept of the FSM model
– Analytic tools for FSM: how to describe an FSM? ◆Design of sequential circuits
– Use FSM as the Model
– Illustrate the design process through examples
Previously
◆For a real-world problem, we know how to get the
relations (functions) among external input, current
state and next state, external output
– For implementation using Flip-Flops, we need the input/output of that type of flip-flops (note the input/output here is different from the external input and external output)
– What are the relations between current state/next state and input/output of flip-flops?
A Recap of Terminologies on Flip-Flops ◆Flip-flop
– Symbol (diagram)
– Characteristic table/characteristic equation – Excitation table
Example: J-K Flip-Flop
Characteric table
Excitation table
the output of flip- flop Q is the current state
Characteric equation
Current state + input (of flip-flop) -> next state?
Note, we could use different notations for current/next state: Q_t/Q_{t+1}, Q_n/Q_{n+1}
Current state + next state -> input?
This is what we want to design circuits (it can be obtained from the characterisc table)
Common Flip-Flop Types
Back to the Previous Problem
◆We are given the state diagram of FSM
– we can drive the functions:
– Next state = f (external input, current state)
– External output = g (external input, current state)
– Note: f, g can be realized using combinational logic
– However, we need to use Flip-Flops to represent the states. What’s the next state? What’s the input to the flip-flops?
Implementation using Flip-Flops
◆The key question is to decide the input of the FF
– Note: we already know the relationships among external output, external input, current state and next state (we use the output of FF to denote both the current and next state
– It is the input to the FF that decides how to drive the current state to the next state
Implementation using D Flip-Flop ◆For D Flip-flop, it is easy
– Characteristic equation: Q_{next} = D
– Next state = f (external input, current state) – D = f (external input, current state)
Implementation using Other Flip-Flops ◆Generally, for other flip-flops
– We will use the excitation table of that flip-flop to derive the excitation table of the circuit
– Excitation table: what inputs of the flip-flop are required to transit from one state to the next state
– This excitation table of the circuit is also a truth table: the inputs of the flip-flop are the function values and others are variables
Example: use J-K Flip-Flop
◆Design a sequential circuit whose state diagram is
shown as follows, using J-K Flip-Flops
Use the outputs of two J-K Flip-Flops Q0, Q1 to denote the four states
Use X to denote the external input There is no external output for this FSM
Example: use J-K Flip-Flop
◆State table and the excitation table of J-K
State table
Exitation table of J-K
Excitation table of the cuircuit
Example: use J-K Flip-Flop ◆Excitation table of the circuit
For example: the first row, look at Q0, 0 -> 0, the required inputs are J0 = 0, K0 =X
This is a truth table with Q0, Q1, x as variables and J0, K0, J1, K1 as function values (it contains don’t care conditions)
Example: use J-K Flip-Flop ◆K-Map, SOP form, and circuit
K1 = Q0 XOR X
Summary of Design Procedure
◆Critical steps of designing sequential circuits
– FSM model (this is the hardest part): define the states and state transitions
– The rest is routine:
– State table + excitation table of flip-flops -> excitation table of the
– Use K-map to derive the SOP form of two functions:
– Input of Flip-flips = current state (output of flip-flops) + external input
– External output = current state (output of flip-flops) + external input
Exercise 1 -Demo
◆Design a sequential circuit whose state table is specified
as follows, using D flip-flops
Exercise 2
◆Design a counter (using J-K FFs) that has an Enable input.
When Enable = 1, it increments through the sequence 0,
1, 2, 3, 0, 1, … with each clock tick; when Enable = 0, the
counter remain in its current state
◆Specify the FSM to model this problem: what are the
input, states, output, and state diagram?
Exercise 3: Analysis of Sequential Circuits ◆Given a Sequential Circuit, we want to analyze the
function of this circuit. The key: derive the FSM (state diagram) — the inverse procedure of designing
Exercise 3: Analysis of Sequential Circuits
◆ Drive the state diagram/table for the following sequential circuits ◆ Equivalently, we need to derive the two functions: next state = f
(current state, external input) and external output = g(current state, external input)
(note: due to space limited, this circuit is not connected)
Learning Requirements
◆Use FSM to model real-world problems (only very simple
◆The design procedure: from state diagram to functions,
to circuits (important)
◆The analysis: from circuits to state diagrams (only very
simple circuits)
– FSM model (this is the hardest part): define the states and state transitions
After Class
◆Try to finish the three exercises to get familiar with the
procedure; solution will be uploaded
Midterm Exam
◆Time: Mar. 18 (Friday): 2:30 – 5:00 pm
◆Coverage: Lec 1 – Lec 8 (MIPS > 60%)
◆Style: MC, Fill in Blanks, and Questions similar to HW (as
an exercise for Final Exam) ◆Might be hard! Get prepared!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com