CAD Algorithms and Tools课件.ppt

Fanin/Fanout of a Node Node has only one output. Node can have any number of inputs (fanins) and can be an input to any number of nodes (fanouts) N FO1 FO2 FO3 FI1 FI2 FI3 Fanouts Node Fanins Transitive Fanin/Fanout of a Node N Transitive fanin Transitive fanout Factoring F = a’c + a’d + bc + bd + e ? F = (a’+b)(c+d) + e Optimizing Transformations on Boolean Networks Common logic extraction F = (a + b)cd + e F = XY + e G = (a + b)e’ ? G = Xe’ H = cde H = Ye X = a + b Y = cd F G H F G H X Y Resubstitution G = a + b + c G = a + b + c F = a + bd + cd ? F = G(a+d) F G F G Elimination G = a + b + c G = a + b + c F = G(a+d) ? F = a + bd + cd F G F G Sweep Removes nodes that do not fanout Eliminates constant nodes and single-input nodes (buffers, inverters) full_simplify Simplifies each node in the network using don’t-cares Don’t-cares for Nodes in the Network External don’t-cares Some input combinations never occur (unused codes, unreachable states) Internal don’t-cares Satisfiability don’t-cares Some input combinations never occur at a node Observability don’t-cares Under some input combinations, the value produced at the output of the node does not matter Satisfiability Don’t-cares (x,y)=(1,0) is a don’t-care for node F a b c F z1 x y Observability Don’t-Cares (a,c)=(1,1) is a don’t-care for node F a b c F z1 z2 node_struct struct node_struct { char *name; /* name of the output signal */ char *short_name; /* short name for interactive use */ node_type_t type; /* type of the node */ int sis_id; /* unique id (used to sort fanin) */ unsigned fanin_changed:1; /* flag to catch fanin generation errors */ unsigned fanout_changed:1; /* flag to catch fanout generation errors */ unsigned is_dup