Class Notes (810,860)
Canada (494,337)
CSC258H1 (46)


2 Pages
Unlock Document

University of Toronto St. George
Computer Science
Steve Engels

 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
More Less

Related notes for CSC258H1

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.