State & Finite State Machines!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)See)P&H)Appendix)C.7.)C.8,)C.10,)C.11))2)Announcements!Make)sure)you)are)Registered)for)class)Can)access)CMS)Have)a)SecFon)you)can)go)to)Have)a)project)partner))SecFons)are)on)this)week))HW)1)out)later)today)Due)in)one)week,)start)early)Work)alone)Use)your)resources)• Class)notes,)book,)SecFons,)office)hours,)newsgroup,)CSUGLab))3)Announcements!Check)online)syllabus/schedule))Slides)and)Reading)for)lectures)Office)Hours)Homework)and)Programming)Assignments)Prelims:)Evening)of)Thursday,)March)10)and)April)28th))Schedule)is)subject)to)change)HW1)CorrecFon:)Hint)1:)Your)ALU)should)use)your)adder)and)leW)shiWer)as)components.)But,)as)in)class,)your)ALU)should)only)use)a)single)adder)component))to)implement)both)addiFon)and)subtracFon.)Similarly,)your)ALU)should)use)only)a)single)leW)shiWer)component)to)implement)all)of)the)shiW))operaFons.)For)instance,)leW)right)shiWing)can)be)accomplished)by)transforming)the)inputs)and)outputs)to)your)leW)shiWer.)You))will)be)penalized)if)your)final)ALU)circuit)uses)more)than)one)adder)or)leW)shiWer.)Of)course,)always)strive)to)make)your)implementaFon)clear,)but)do)not)duplicate)components)in)an)effort)to)do)so.)4)Goals for Today: Stateful Components!UnFl)now)is)combinatorial)logic)• Output)is)computed)when)inputs)are)present)• System)has)no)internal)state)• Nothing)computed)in)the)present)can)depend)on)what)happened)in)the)past!)))Need)a)way)to)record)data)Need)a)way)to)build)stateful)circuits)Need)a)state`holding)device))Finite)State)Machines)Inputs)CombinaFonal)circuit)Outputs)N)M)5)Unstable Devices!BACBistable Devices!A B A Simple Device • Stable and unstable equilibria?!Bistable Devices!• In stable state, A = B!• How do we change the state?!A B A B 1 A B 1 0 0 A Simple Device • Stable and unstable equilibria?!8)SR Latch!Set`Reset)(SR))Latch))Stores)a)value)Q)and)its)complement)Q))S) R) Q) Q)0) 0)0) 1)1) 0)1) 1)S)R)Q)Q)S)R)Q)Q)9)Unclocked D Latch!Data)(D))Latch)D) Q) Q)0)1)S)R)D)Q)Q)10)Unclocked D Latch!Data)(D))Latch)D) Q) Q)0) 0)1)1) 1)0)S)R)D)Q)Q)Data)Latch)• Easier)to)use)than)an)SR)latch)• No)possibility)of)entering)an)undefined)state)When)D)changes,)Q)changes)– …)immediately)(aWer)a)delay)of)2)Ors)and)2)NOTs))Need)to)control)when)the)output)changes)11)D Latch with Clock!S)R)D)clk)Q)Q)clk)D)Q)Level)SensiFve)D)Latch)Clock)high:))))set/reset)(according)to)D))Clock)low:))))keep)state)(ignore)D))12)Clocks!Clock)helps)coordinate)state)changes)• Usually)generated)by)an)oscillaFng)crystal)• Fixed)period;)frequency)=)1/period)1)0)Edge-triggering!• Can design circuits to change on the rising or falling edge!• Trigger on rising edge = positive edge-triggered!• Trigger on falling edge = negative edge-triggered!• Inputs must be stable just before the triggering edge!input clock14)Edge-Triggered D Flip-Flop!D)Flip`Flop)• Edge`Triggered)• Data)is)captured)when)clock)is)high)• Outputs)change)only)on)falling)edges)D) Q)Q)D) Q)Q)c)F)L) L)clk)D)F)Q)c)Q)Q)D)clk)15)Clock Disciplines!Level)sensiFve)• State)changes)when)clock)is)high)(or)low))Edge)triggered)• State)changes)at)clock)edge)posiFve)edge`triggered)negaFve)edge`triggered)16)Registers!Register)• D)flip`flops)in)parallel))• shared)clock)• extra)clocked)inputs:)write_enable,)reset,)…)clk)D0)D3)D1)D2)4)4)4`bit)reg)17)Metastability and Asynchronous Inputs!)1`bit)reg)Clk)18)Metastability and Asynchronous Inputs!Q:)What)happens)if)input)changes)near)clock)edge?))A:)Google)“Buridan’s)Principle”)by)Leslie)Lamport))1`bit)reg)Clk)0)1)19)An Example!32`bit)reg)Clk)+1)Run)WE) R)Reset)20)Clock Methodology!Clock)Methodology)• NegaFve)edge,)synchronous)– Signals)must)be)stable)near)falling)clock)edge)• PosiFve)edge)s yn chronous)• Asynchronous ,) )mulFple)clo cks,).).).)clk)compute& save&tsetup&thold&compute& save& compute&tcombina?onal&Finite State Machines22)Finite State Machines!An)electronic)machine)which)has)• external)inputs)• externally)visible)outputs)• internal)state))Output)and)next)state)depend)on)• inputs)• current)state)23)Abstract Model of FSM!Machine)is)! ! !M)=)())S,!!I,!!O,!δ)))S:)Finite)set)of)states)I:) )Finite)set)of)inputs)O: )Finite)set)of)outputs)δ:) )State)transiFon)funcFon)Next)state)depends)on)present)input)and)present)state)24)Voting Machine!mux)32)...®)detect)enc)3decoder)(3`to`8))32) 32)32)LED)dec)3WE)+1)reg)WE)reg)WE)reg)WE)mux)D)V)25)Automata Model!Finite)State)Machine)• inputs)from)external)world)• outputs)to)external)world)• internal)state)• combinaFonal)logic))))Next&State&Current&State&Input&Output&Registers)Comb.)Logic)26)FSM Example!Legend&state&input/output&start&state&A&B&C& D&down/on&up/off&down/on&down/off&up/off&down/off&up/off&up/off&Input:)up)or)down&Output:)on)or)off&States:)A,)B,)C,)or)D&27)FSM Example Details!Legend&S1S0&i0i1i2…/o0o1o2…&S1S0&00&01&10& 11&1/1&0/0&1/1&1/0&0/0&1/0&0/0&0/0&Input:)0=up)or)1=down)Output:)1=on)or)0=off)States:)00=A,)01=B,)10=C,)or)11=D)28)General)Case:)Mealy)Machine)))))))))Outputs)and)next)state)depend)on)both)current)state)and)input)Mealy Machine!Next&State&&Current&State&Input&Output&Registers)Comb.)Logic)29)Moore Machine!)Special)Case:)Moore)Machine))))))))Outputs)depend)only)on)current)state)Next&State&Current&State&Input&Output&Registers)Comb.)Logic)Comb.)Logic)30)Moore Machine Example!Legend&state&out&input&startout&A&off&B&on&C&off&D&on&down&up&down&down&up&down&up&up&Input:)up)or)down&Output:)on)or)off&States:)A,)B,)C,)or)D&31)Digital Door Lock!Digital)Door)Lock)Inputs:))• keycodes)from)keypad)• clock)Outputs:))• “unlock”)signal)• display)how)many)keys)pressed)so)far)32)Door Lock: Inputs!AssumpFons :)• signals)are)synchronized)to)clock)• Password)is)B`A`B)KABK& A& B& Meaning&0) 0) 0) Ø))(no)key))1) 1) 0) ‘A’)pressed)1) 0) 1) ‘B’)pressed)33)Door Lock: Outputs!AssumpFons :)• High)pulse)on)U)unlocks)door)UD3D2D1D0)4)LED)dec)8)34)Door Lock: Simplified State Diagram!Idle&G1&”0”&Ø&G2&G3&B1& B2&”1”& ”2”&”3”,&U&”1”& ”2”&Ø& Ø&Ø& Ø&“B”&“A”& “B”&else&else&any&any&else&else&B3&”3”&else&35)Door Lock: Simplified State Diagram!Idle&G1&”0”&Ø&G2&G3&B1& B2&”1”& ”2”&”3”,&U&”1”& ”2”&Ø& Ø&Ø& Ø&“B”&“A”&
View Full Document
Unlocking...