Finite State Machines: Finite State Machines By Mike Chen
Finite State Machines vs. Combinational Logic Units: Finite State Machines vs. Combinational Logic Units Combinational logic units are a type of logic circuit whose output is a pure function of the present input only. Finite State Machines, used in sequential logic, have outputs that depend on both the present input as well as the history of the input.
A Finite State Machine: A Finite State Machine A sequential logic unit which Takes an input and a current state Produces an output and a new state It is called a Finite State Machine because it can have, at most, a finite number of states. It is composed of a combinational logic unit and flip-flops placed in such a way as to maintain state information.
Representing a Finite State Machine: Representing a Finite State Machine It can be represented using a state transition table which shows the current state , input , any outputs , and the next state . Input Current State Input 0 Input 1 …. Input n State 0 State 1 …. State n Next State / Output …. Next State / Output …. …. …. …. …. …. …. …. ….
Representing a Finite State Machine: Representing a Finite State Machine It can also be represented using a state diagram which has the same information as the state transition diagram. State 0 State 1 Input / Output Input / Output
Example 1: A Modulo-4 Synchronous Counter: Example 1: A Modulo-4 Synchronous Counter Counts from 0 to 3 and then repeats. It has a clock input (CLK) and a RESET input. Outputs appear as a sequence of values (q 1 and q 0 ) at time steps corresponding to the clock. As the outputs are generated, a new state (s 1 s 0 ) is generated which takes on values of 00, 01, 10, and 11 and are fed back to the input.
The Mod-4 Counter: The Mod-4 Counter Requires four states, encoded in binary, with at least two bits for them to be encoded uniquely. A = 00 B = 01 C = 10 D = 11 The input requires only a single bit. 0 | 1
State Transition Diagram for the Mod-4 Counter: State Transition Diagram for the Mod-4 Counter
State Table for the Mod-4 Counter: State Table for the Mod-4 Counter
State Assignment for the Mod-4 Counter: State Assignment for the Mod-4 Counter
Truth Table for the Mod-4 Counter: Truth Table for the Mod-4 Counter
Logic Design for Mod-4 Counter: Logic Design for Mod-4 Counter
Example 2: A Sequence Detector: Example 2: A Sequence Detector Design a sequence detector using D flip-flops and 8-to-1 multiplexers. The sequence detector outputs a 1 when exactly two of the last three inputs are 1. An input of 011011100 produces the output of 001111010 There is a one-bit serial input line and we will assume that initially no inputs have been seen. Note : the sequence detector cannot output a 1 until at least three inputs have been read.
The Sequence Detector: The Sequence Detector There are a total of eight sequences that the machine can observe: 000, 001, 010, 011, 100, 101, 110, 111 We will assume that state A is the initial state where no inputs have been fed into the machine. In states B and C, only one input has been fed into the machine and therefore we cannot output a 1.
State Transition Diagram for the Sequence Detector: State Transition Diagram for the Sequence Detector
State Table and State Assignment for the Sequence Detector: State Table and State Assignment for the Sequence Detector
Truth Table for the Sequence Detector: Truth Table for the Sequence Detector
Creating the Circuit for the Sequence Detector: Creating the Circuit for the Sequence Detector There needs to be one flip-flop for each state variable, so a total of three are needed. Also, there are three next state functions and one output function, so four 8-to-1 multiplexers are needed.
Logic Diagram for the Sequence Detector: Logic Diagram for the Sequence Detector
Example 3: A Vending Machine Controller: Example 3: A Vending Machine Controller Design a vending machine controller using D-flip flops and a Programmable Logic Array (PLA). The vending machine accepts three types of inputs: a nickel (5¢), a dime (10¢), or a quarter (25¢). When the value of the total inserted coins equals or exceeds 20¢, the machine dispenses the merchandise, returns any excess change, and waits for the next transaction.
The Vending Machine Controller: The Vending Machine Controller For simplicity, we will assume that if the machine currently has 15¢ and the user inserts a quarter, the merchandise will be dispensed, 15¢ will be returned, and the machine will keep 5¢ and await for more money. This way, we can use 4 states to represent all possible states: A (00) = 0¢ C (10) = 10¢ B (01) = 5¢ D (11) = 15¢ We will need two bits each to uniquely encode all possible states as well as inputs.
State Transition Diagram for the Vending Machine: State Transition Diagram for the Vending Machine Input / Output 2 Output 1 Output 0 Input = N ickel | D ime | Q uarter Output 2 = 1 | 0 = Dispense / Do not dispense merchandise Output 1 = 1 | 0 = Return / Do not return a nickel in change Output 0 = 1 | 0 = Return / Do not return a dime in change
State Table and State Assignment for the Vending Machine: State Table and State Assignment for the Vending Machine Present State = s n Input = x n Output = z n
Truth Table for the Vending Machine: Truth Table for the Vending Machine s 1 s 2 x 1 x 0 s 1 s 0 z 2 z 1 z 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 2 0 0 1 0 0 0 1 1 0 3 0 0 1 1 d d d d d 4 0 1 0 0 1 0 0 0 0 5 0 1 0 1 1 1 0 0 0 6 0 1 1 0 0 0 1 0 1 7 0 1 1 1 d d d d d 8 1 0 0 0 1 1 0 0 0 9 1 0 0 1 0 0 1 0 0 10 1 0 1 0 0 0 1 0 0 11 1 0 1 1 0 0 1 1 1 12 1 1 0 0 d d d d d 13 1 1 0 1 0 0 1 1 0 14 1 1 1 0 1 1 1 1 1 15 1 1 1 1 d d d d d For the FSM circuit, we will need: Two D flip-flops to represent the two state bits. PLA that takes four inputs (two for the present state bits and two for the coin bits) and has five outputs (two for the next state bits and three for the dispense and return bits).
Logic Design for the Vending Machine: Logic Design for the Vending Machine Assumes the clock input is asserted only on an event such as the user inserting a coin into the machine. 5x5 PLA Q D s 0 Q D s 1 CLK z 2 z 1 z 0 x 1 x 0