Class Notes (811,138)
CSC258H1 (46)
Lecture

# CH 5 - FSM

6 Pages
70 Views

School
University of Toronto St. George
Department
Computer Science
Course
CSC258H1
Professor
Steve Engels
Semester
Winter

Description
SEQUENTIAL CIRCUIT DESIGN  Circuits using flip-flops  Example #1: Shift registers o A series of D flip-flops can store a multi-bit value (such as a 16-bit int) o Data can be shifted into this register 1 bit at a time, over 16 clock cycles o Implementing the register with these special D flip-flops will now maintain values in the register until overwritten by setting EN high  Example 3: Counters o Ex. 4-bit shift register used to store 1011 then 0000 o Consider the T flip-flop  Read from Q3 to Q0  Output is inverted when input T is high o What happens when a series of T flip-fliops are connected together in sequence o More interesting  Connect the output of one flip-flop to the clock input of the next  Example #2: Load registers o One can also load a register’s values all at once, by feeding signals to This is a 4-bit ripple counter  Which is an example of an asynchronous circuit each flip-flop  Timing isn’t quite synchronized with the rising clock pulse  Ex. a 4-bit load register  Cheap to implement, but unreliable for timing o To control when this register is allowed to load its values, we introduce the D flip-flop with enable o This is a synchronous counter, with a slight delay o Truth table EN D QT QT+1 0 0 0 0 0 0 1 1  Could be synchronized even more by having each AND gate 0 1 0 0 combine outputs of all previous flip-flops 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 o Counters are often implemented with a parallel load and clear inputs  Loading a counter value is used for countdowns  Designing with flip-flops o Counters and registers are examples of how flip-flops can implement useful circuits that store values o Sequential circuits are the basis for memory, instruction processing, and any other operation that requires the circuit to remember past data values. o These past data values are also called the states of the circuit. o Sequential circuits use combinational logic to determine what the next state of the system should be, based on the past state and the current input values.  State example: counters o With counters, each state is the current number that is stored in the counter o On each clock tick, the circuit transitions from one state to the next, based on the inputs o State tables help to illustrate how the states of the circuit change with various input values  Transitions are understood to take place on the clock ticks  Can also be represented with flip-flop values, instead of state labels. Note: flip-flop values are both inputs and outputs of the circuit State Prev. F1 F2 F3 Write State Next F1 F2 F3 Zero 0 0 0 0 Zero 0 0 0 Zero 0 0 0 1 One 0 0 1 One 0 0 1 0 One 0 0 1 One 0 0 1 1 Two 0 1 0 Two 0 1 0 0 Two 0 1 0 Two 0 1 0 1 Three 0 1 1 Three 0 1 1 0 Three 0 1 1 Three 0 1 1 1 Four 1 0 0 Four 1 0 0 0 Four 1 0 0 Four 1 0 0 1 Five 1 0 1 Five 1 0 1 0 Five 1 0 1 Five 1 0 1 1 Six 1 1 0 Six 1 1 0 0 Six 1 1 0 Six 1 1 0 1 Seven 1 1 1 Seven 1 1 1 0 Seven 1 1 1 Seven 1 1 1 1 Zero 0 0 0  Example #3: Counters – moved to feb04ce o Let Green = 00, Yellow = 01, Red = 10  Finite State Machines o State table o From theory courses, mainly used to describe the grammars of a State Prev. F F Write State Next F ’ F ’ 1 0 1 0 language, or to model sequence data Green 0 0 0 Green 0 0  A finite state machine is an abstract model that captures the Green 0 0 1 Yellow 0 1 operation of a sequential circuit Yellow 0 1 0 Yellow 0 1  Finite State Machines are models for an actual circuit Yellow 0 1 1 Red 1 0 design Red 1 0 0 Red 1 0  These states represent internal states of the circuit which Red 1 0 1 Green 0 0 are stored in the flip-flop values  FSM design steps o A FSM is define (in general) as: o 1. Draw state diagram o 2. Derive state table from state diagram  A finite set of states  A finite set of transitions between states triggered by inputs to o 3. Assign flip-flop configuration to each state the state machine  Number of flip-flops needed is ceiling2log (# of states))  Output values that are associated with each state or transition o 4. Redraw state table with flip-flop values (depending on the machine) o 5. Derive combinational circuit for output and for each flip-flop input  State and end states for the state machine  FSM Example #4: Recognizer  FSM Example #1: Tickle Me Elmo o Recognize a sequence of input values, and raise a signal if that input o Toy reacts differently each time it is squeezed has been seen o Questions to ask: o Example: Three high values in a row  Understood to mean that the input has been high for three  What are the inputs?  What are the states of this machine? rising clock edges  How do you change from one state to the next  Assumes a single input X and a single output Z o 1. State diagram  In this case, the states are labeled with the input values that have been seen up to now  Transitions between states are indicated by the values on the transition arrows o Usually FSM has more than one input and will trigger a transition based on certain input values but not others o Also might have input values that don’t cause a trandition, but keep the circuit in the same state  FSM Example #2: Alarm Clock o Internal state description  Starts in a neutral state, until timer signal goes off  Clock moves to alarm state  Alarm state continues until  A snooze button is pushed (move to snooze state) o 2. State table  Alarm is turned off (move to neutral state)  Make sure that the state table lists all the states in the state  Timer goes off again (move to neutral state) diagram, and all the possible inputs that can occur at that state  In snooze state, clock returns to alarm state when the timer State Prev. EN State Next signal goes off again 000 0 000  FSM Example #3: Traffic Light 000 1 001 001 0 010 001 1 011 010 0 100 010 1 101 011 0 110 011 1 111 100 0 000 100 1 001 101 0 010 101 1 011 110 0 100 110 1 101 111 0 110 111 1 111 o 3. Assign Flip-flops  Boolean equation for Z  The flip-flops are the circuit unit that are responsible for actually Z = F 2 F 1 F0 storing states  Two ways to derive the circuitry needed for the output values of the state  When deciding how many states are needed, remember that a machine single flip-flop can store two values (0 and 1), and thus two o More machine: states.  The output for the FSM depends solely on the current state  How many states can be stored with e
More Less

Related notes for CSC258H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.

Get notes from the top students in your class.

Request Course
Submit