FSM Introduction History Combinational Logic single FSM Hier archy of FSM s VIS handles hierarchy Facilities for managing networks of FSMs Sequential Circuit Optimization single machine SIS MISII Sequential Circuit Partitioning Facilities for handling latches Original Verify Final Partition Combine Flatten partition for layout Sub ckt 1 Sub ckt N Optimize Interface logic asynchronous 1 What are Combinational Circuits De cid 12 nition A circuit is combinational if it computes a function which depends only on the inputs applied to the circuit for every input value there is a unique output value cid 15 cid 15 cid 15 Circuits with an acyclic underlying topology are combinational Cyclic circuits can be combinational in fact there are combinational circuits whose minimal form must have cycles Kautz 1970 Recent work on checking if circuit combinational Malik 94 Shiple 95 These are based on X valued simulation 2 What are Sequential Circuits cid 15 cid 15 cid 15 Some sequential circuits have memory elements Synchronous circuits have clocked latches Asyn chronous circuits may or may not have latches e g C elements but these are not clocked Feedback cyclic is a necessary but not su cid 14 cient condition for a circuit to be sequential Synthesis of sequential circuits is not as well devel oped as combinational Sequential synthesis tech niques not really used in commercial software t u p n I y r a m i r P in 1 in 2 in 3 in 4 t u p t u O y r a m i r P out 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 Present State Next State Latch Registers and Latches Netlist State Transition Graph STG The above circuit is sequential since output depends on the state and input 3 Example Highway Light Verilog module hwy control clk car present enable hwy short timer long timer hwy light hwy start timer enable farm input clk car present enable hwy short timer long timer output hwy light hwy start timer enable farm boolean wire car present wire short timer long timer hwy start timer enable farm enable hwy color reg hwy light initial hwy light GREEN assign hwy start timer hwy light GREEN car present YES long timer hwy light RED enable hwy assign enable farm hwy light YELLOW short timer always posedge clk begin case hwy light GREEN if car present YES long timer hwy light YELLOW YELLOW if short timer hwy light RED RED if enable hwy hwy light GREEN endcase end endmodule 5 Finite State Machines Finite State Machines in STG or transition relation form are a behavioral view of sequential circuits They describe the transitional behavior of these circuits They can distinguish among a cid 12 nite number of classes of in put histories these classes are the internal states of the machine Moore Machine is a quintuple M S I O cid 14 cid 21 S cid 12 nite non empty set of states I cid 12 nite non empty set of inputs O cid 12 nite non empty set of outputs cid 14 S cid 2 I 7 S transition or next state function cid 21 S 7 O output function Mealy Machine M S I O cid 14 cid 21 but cid 21 S cid 2 I 7 O For digital circuits typically I f0 1g f0 1g n m and O In addition certain states may be classi cid 12 ed as reset or initial states Automata are similar to FSM s however they do not produce any outputs they just accept input sequences accepting set of states is given 6 Representing State Machines State Transition Graphs and Tables Example Tra cid 14 c Light Controller Mealy machine not c and t1 hl GREEN fl RED st 0 ts hl RED fl YELLOW st 0 HG c and t1 hl GREEN fl RED st 1 not ts hl RED fl YELLOW st 0 FY HY not ts hl YELLOW fl RED st 0 not c or t1 hl RED fl GREEN st 1 ts hl YELLOW fl RED st 1 FG not not c or t1 hl RED fl GREEN st 0 State Transition Graph Example PS HG HG HY HY FG FG FY FY IN not c and t1 c and t1 not ts ts not not c or t1 not c or t1 not ts ts NS HG HY HY FG FG FY FY HG OUT hl GREEN fl RED st 0 hl GREEN fl RED st 1 hl YELLOW fl RED st 0 hl YELLOW fl RED st 1 hl RED fl GREEN st 0 hl RED fl GREEN st 1 hl RED fl YELLOW st 0 hl RED fl YELLOW st 1 State Transition Table Example 7 Representing State Machines cid 15 cid 15 cid 15 State Transition Graphs and State Transition Ta bles are similar the cid 12 rst is graphical the second is tabular In this example the edges transitions are labeled with general logic functions predicates of the in puts Traditionally minterms or cubes have been used for the transitions e g KISS format especially for tables since used as input to two level minimizers Minterms need the most edges and arbitrary logic functions predicates the least 8 Non Determinism and Incomplete Speci cid 12 cation s0 a 0 a 1 s1 s2 cid 15 cid 15 In automata theory non determinism is associ ated with many transitions from a given current state and under the same input conditions we may go to di cid 11 erent states and have di cid 11 erent outputs Each behavior is considered valid Nondetermin ism provides a compact way to describe a set of valid behaviors In classical sequential function theory transition functions and output functions can be incompletely speci cid 12 ed i e the functions can have don t cares i e de cid 12 ned only on a proper subset of their input space Where it is unde cid 12 ned we consider it to allow any behavior This also describes a set of valid behaviors 10 Non Determinism and Incomplete Speci cid 12 cation Given an input and present state Nondeterminism some next states and outputs are ruled out Result is subset of next states and outputs admissible for a transition cid 15 Don t cares all next states and outputs are al lowed These may be because the given state can t be reached so will never occur or the state is a binary code not used during state assignment cid 15 cid 15 Incomplete transition structure It may be that no next state is allowed If this is because that input will never occur at that state we need to complete the description by adding transitions to all states and allowing all outputs On the other hand we may want the machine to do nothing e g as an automaton Sometimes we com plete the transition structure by adding a dummy state and calling it a non accepting state All describe a set of behaviors These are used to de scribe cid 13 exibility for the implementation during …