Class Note for ENGIN 112 at UMass(23)
Class Note for ENGIN 112 at UMass(23)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for ENGIN 112 at UMass(23)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
University of Massachusetts Amherst Engin112 Lecture 26 Sequential Circuit Design FSM l Maciej Ciesielski Department of Electrical and Computer Engineering 11032008 Recap from last lecture Sequential circuit analysis 0 State equations 0 State table 0 State diagram Today s lecture 0 Finite state machines FSM gtgt Mealy gtgt Moore 0 Sequential circuit design procedure 11032008 Engin 112 Intro to ECE 2 Finite State Machines State diagrams are representations of Finite State Machines 0 0 on 110 Two flavors of FSMs 4 7 gtgt Mealy FSM gtgt Moore FSM l or 1K 01 gt 10 I Difference I 0 How output is determined 39 10 39 Mealy FSM o 0 0 Output depends on input and state 0 Output is not synchronized with clock gtgt can have temporarily unstable output Moore FSM 0 Output depends only on state 11032008 Engin 112 Intro to ECE 3 Two Flavors of FSM Mealy vs Moore machine Mam Mud in 1 rapuu bs Next State State amp amp Cami q onal Regmer Combination ai Meagan e gt gn Logic Clock Manny Had it Inputs 0 Ngn Stare Combinations Logic 0111p I Combina onal Logic Outputs Manurefwd State Register Chick 11032008 Engin 112 Intro to ECE 4 Mealy Machine Output based on state and present input 0 Output changes durin transition inout inputs I Houtputs CL present state next state FFs 11032008 Engin 112 Intro to ECE 5 Moore Machine Output based on state only 0 Output is associated with state in inputs I CL present stat FFs next state CL Hquotoutputs 11032008 Engin 112 Intro to ECE 6 Design of Sequential Circuits How can we design a sequential circuit 0 Eg circuit that detects 3 or more consecutive 1 s in input Desiqn procedure Derive state diagram from description Reduce number of states if necessary Assign binary values to states Obtain binary coded state table transition table Choose type of flipflops Derive flipflop input equations and output equations Draw logic diagram NQFNPWNT Steps 1 amp 3 require insight Steps 2 4 7 can be automated 0 Design that follows welldefined procedure called synthesis 11032008 Engin 112 Intro to ECE 7 Canonical form of Sequential Circuits Graphs are hard to compare 0 Arbitrary state names 0 Arbitrary coding Graphs are generally very difficult to deal with 0 Determining if two graphs are identical is the graph isomorphism problem gtgt No known algorithm exists that can determine isomorphism in polynomial time for arbitrary graphs gtgt Problem reduces to trying every possible matching gtgt Requires exponential time very very long for large graphs Canonical form of sequential circuit would require solution to graph isomorphism problem No canonical form for sequential circuits exists 11032008 Engin 112 Intro to ECE 8 State Assignment States are represented by flipflop values in circuit 0 Need to encode state in binary What is the minimum number of flipflops that are necessary to encode m states 0 Need at least l log2m bits I is ceiling function 39 Many possible encodings State Binary Gray Onehot a 000 000 00001 Terminology b 001 001 00010 0 State table uses C O10 011 00100 uncoded states d 011 010 01000 0 Transition table uses 6 100 110 10000 coded states 11032008 Engin 112 Intro to ECE 9 Example 1 Sequence Detector Circuit specification 0 Design a circuit that outputs a 1 when three consecutive 1s have been applied to input and 0 othenvise Step 1 derive state diagram 0 What should a state represent gtgt Eg number of 1 s seen so far 0 Moore or Mealy FSM gtgt Both possible gtgt Chose Moore to simplify diagram 0 State diagram gtgt State SO zero 1s detected gtgt State S1 one 1 detected gtgt State 82 two 1s detected gtgt State SS three 1s detected 11032008 Engin 112 Intro to ECE 10 Example 1 Sequence Detector Step 2 reduce number of states 0 State table current next state output state x0 x1 0 82 SO SB 83 So 83 0 0 Which states are equivalent gtgt None no state reduction possible l 40 D o D l OOO Step 3 state assignment 0 Two flipflops 0 Binary state coding 11032008 Engin 112 Intro to ECE 11 Example 1 Sequence Detector Step 4 Binary coded state table 0 Name flipflops A and B current state next state output x0 x1 A B A B A B 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 Step 5 Choose type of flipflops 0 Eg Dflipflop 0 Characteristic equation Qz 1DQ 11032008 Engin 112 Intro to ECE 12 Example 1 Sequence Detector Step 6 derive flipflop input equations and output equation 0 Use state table oAmnmmaw zman eanmaw amen yABX 26 7 oryAB 23 11032008 current state input next state output A B x A B y 0 O O O O O O O 1 O 1 O O 1 O O O O O 1 1 1 O O 1 O O O O O 1 O 1 1 1 O 1 1 O O O 1 1 1 1 1 1 1 Engin 112 Intro to ECE 13 Example 1 Sequence Detector Step 6b minimize equations Az 12357 Bz 12157 yAB 23 easy y AB Karnaugh maps forA and B Bx B 0 0 0 1 l t quot10 39l l x DAAxBx D3AxB39x 11032008 Engin 112 Intro to ECE 14 Example 1 Sequence Detector Step 7 Circuit diagram 0 DA AXBX DB AXB X gtClk YAB Va l 2 D B l gtm H ock 7 11032008 Engin 112 Intro to ECE 15 Terminology D W 39 x gtka Next state f L logic I D o 5 1 f gt cm 5 Clock i Output logic l l I y KJ 11032008 Engin 112 Intro to ECE 16 Summary Finite state machines form the basis of many digital systems Designs often start from clear specifications Develop state diagram and state table Optimize using combinational design techniques 0 Output logic 0 Next state logic Mealy or Moore implementations possible 11032008 Engin 112 Intro to ECE 17 Homework Read Mano 57 state reduction and 56 Verilog Midterm 2 exam Wed Nov 12 at 630 pm 0 Material Chapters 4 and 5 gtgt No Verilog HDL QampA session on Monday Nov 10 2008 11032008 Engin 112 Intro to ECE 18
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'