Sequential Synthesis 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 Representations of Sequential Circuits t s t u p n i y r a m i r P in 1 in 2 in 3 in 4 out 1 t u p t u O y r a m i r P 1 Present State Next State Latch Gates and Latches Netlist State Transition Graph STG 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 pi ps ns 1 ns 2 ns3 nsn ns 1 ns 2 ns 3 ns n Transition Relation cid 15 Transition relation is T pi ps ns or T pi ps ns po It is the characteristic function of all edges of the STG T pi ps ns Y nsi cid 8 fi pii psi cid 15 Each representation has its advantages and disad vantages STG is like a two level description can blow up Netlist only way for large circuits Transi tion T usually represented by BDD s Can blow up but can also express it as separate relations for each latch which are implicitly conjoined T Y Ti pii psi nsi 4 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 1gm and O f0 1gn 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 Transition and Output Relations R cid 26 I cid 2 S cid 2 S cid 2 O is the transition and output relation r in sps sns out 2 R if and only if input in causes a transition from sps to sns and produces output out Since R is a set it can be represented by its charac teristic function and hence as a BDD Depending on the application it may be preferable to keep the transition and output relation separate Transition Relation R cid 14 cid 26 I cid 2 S cid 2 S Output Relation R cid 21 cid 26 I cid 2 S cid 2 O 9 Non Determinism and Incomplete Speci cid 12 cation s0 a 0 a 1 s1 s2 cid …