Class Note for ECE 474A with Professor Lysecky at UA
Class Note for ECE 474A with Professor Lysecky at UA
Popular in Course
Popular in Department
This 15 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for ECE 474A with Professor Lysecky at UA
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
Binary Decision Diagrams BDDs Boolean Logic Functions Representations 0 Function can be represented in different ways 39 Truth table equation Krnap circuit etc 39 Some representations not unique not canonical F b a u i u i i E r 1F b 39b39 39b a qualon a a a 1 D D Equation 2 Fab a39 b F Circuit1 Truth table a D F Circuitz Thequ sea 47mm 2 an Sum Lyszcky An Efficient Representation 0 Synthesis optimization veri cation and testing algorithmstools manipulate large Boolean functions 39 Important to have efficient way to represent these functions 39 Binary Decision Diagrams BDDs have emerged as apopular choice for representing these functions BDDS 39 Graph representation similar to abinary tree ie decision trees from previous lectures 39 Able to efficiently represent large functions 39 Some representations are canonical unique ECE 67425751 3 an Susan Lyszcky Binary Decision Diagram BDD Example 1 MUX circuit to implement 1 S xi x2 x3 5 ogic function E D D 1 u u i u lt u i u i lt u i i i i u u i i u i i i i u u i i i u lt sixix2x3i 1 n xarm my 1 1 n x21 V W X1 rm m Sininini1 Si111in srn1m1 srnn1in ECE 67625751 3 an Susan Lyszcky Binary Decision Diagram BDD Example 1 0 Corresponding BDD to implement function S S 39 Onetoone correspondence to ihe MUX gates in E E 239 2 ihe ipped circuit n i n i n i i i i n n i i n i i i i n n i i i n 51x1 x2 5 51x1 x2 xsi xi x2 x3 51x1 x2 xsi V Same mum inst ipped m mmsz 5mme Corresponding EDD gang Binary Decision Diagram BDD Example 1 0 How does it work 5 X1szvx3 xi x2 x3 39 Line wiih bubble represent Value 0 39 Lines wiihout bubble represent Value 1 mannnngn m Ecn 67625751 Sum Lyszcky Binary Decision Diagram BDD Notations 0 Several ways to represent value 1 and value O 39 Bubble Vs Nonbubble line 39 Dashed Vs Solid line 39 T then Vs E else labels We will adopt T vs E labels consistent with most of the book Hatchel examples 51x1 x2 xsi 51x1 x2 xsi 51x1 gt2 xsi ECE maisvsa 7 an Susan Lyszcky Binary Decision Diagram BDD Example 2 0 Let s consider another function fabcd abc b d c d What is the value of r1o107 What is the value of r11o17 Notice that if 51 and b0 the function does not depend on a value for c ECE maisvsa 3 an Susan Lyszcky Ordered Binary Decision Diagram OBDD 0 This BDD is an ordered binary decision diagram because the variables appear in the same order along all paths from the root to the leaves 39 OrderingisaSbSch 39 We assume all BDDs considered are ordered This one is an optimal ordering because there is exactly one node for each variable OrderaSbSch OrderanSbSc OrderbScSa d ECE maisvsa 9 am Susan Lyszcky BDDs for Basic Logic Functions AND OR NAND NOT a b F a b F a b F a F n n n n n n n n i n i n n i i n i i U l i n n i n i i n i i D i i i i i i i i n ECE maisvsa in am Susan Lyszcky Formal Definition of BDDs A BDD is a direct acyclic graph representing a multipleoutput switching function F Nodes are partitioned into three subsets I Function node lt Function node internal Representstheftmaionsymbola quot 5 indegree o outdegree 1 39 Internal node Represents variable in fmethn a b c d indegree 2 1 39 meme 2 4 Terminal nodes I Terminal node Represents avalue 1 or 0 indegree 2 1 outdegree o ECE 67425752 ii em Suszn Lyszcky Formal Definition of BDDs A BDD de nition cont Three types of edges Incoming edge From the ftmction node and defines ftmction T edge From an internal node and represents when the corresponding variable is 1 E edge From an internal node and represents when the corresponding variable is o ECE milsvsa Suszn Lyszcky i am Formal Definition of BDDs 0 A BDD de nition cont Function ortne function node istherunction of it39s outgoing edge 39 The function frepresented by a BDD is defined as follows The function of the terminal node is a constant value 1 or o The function of a T edge is the function of the head node The function of a E edge is the complement of the function of the node Function ortnis E edge is a39 Function of this The function of a node v is given byva v fE T edge is a when fT is the function of the T edge ande is the function of the E edge 39 The function of the function node is the function I Ofil s outgoing edge Function ortnis terminal node is n F unction ofthis terminal node is 1 race maisvsz 13 em sum Lysecty BDD Canonical Form BDDs are canonical unique for a representation of F given a variable ordering if 39 All internal nodes are descendants of some node 39 There are no isomorphic sub graphs 39 For every node f1 75 fE Isomorphic subgraphs isomomnio Two grapns are isornorpnic iftnere is a onestosone correspondence between theirvertices and tnere is an edge between two vertices of one grapn it and only ittnere is an edge between tne two corresponding vertices in tne otner grapn Engisn 7 Same subgrapn r a verices the Same a edges between vemces the same race 67625751 N am sum Lysecty Building BDDs For a Function F 0 How do I build a BDD given a F a b abc a b c quCUOH F 7 F abc a bb c Recursive use of Shannon s Expansion Theorem I FaFaaTav Far bb c 39 We cankeep applying expansion Fa be theorem eventually we reach the F3 also called the cofactor of F wrt unique canonical form whichuses with respect to a only minteims F 3b abc a b c F a b abc a b c F beb Fbi F ch c Fci F ba ac b a c F Ca b a b c a b ab J K J Y Y F expanded wrt to b F expanded wrt to c m 67425752 15am Susiquot Lyszcky Building BDDs Exercise 1 0 Build a BDD for f abc ab c a bc a b c 0 Use the variable ordering a s b s c pamai Expansiun With respect in 3 Compute cofactors offwith respect to a rst variable in ordering f abc ab c a bc a b c a bc b c rat bc b c ECE 67625751 16 am Susiquot Lyszcky Building BDDs Exercise 1 0 Build aBDD for f abc ab c a bc a b c Use the variable ordering a s b s c pamai Expansiun With respect in n Compute cofactors of f3 and far with respect to b second variable in ordering r3 bc b c fan fab 0 EN fab 39 0 rel bc b c fair far c fa b fair 6 213235le quotmg Building BDDs Exercise 1 0 Build a BDD for f abc ab c a bc a b c 0 Use the variable ordering a s b s c Compute cofactors of fab few few few with respect to c third variable in ordering fab c Expansiun Wim respectm finai EDD ECE 67625751 ix am Susan Lyszcky Building BDDs Exercise 1 0 f abc ab c a bc a b c Does it work Ecn 67425752 19 am Susiquot Lyszcky Building BDDs Exercise 2 0 Build aBDD for f abc b d c d 0 Use the variable orde ngb s c s d s a pamai Expansiun wrm respect in n Compute cofactors offwith respect to b rst variable in ordering r abc b d c d Y 0 E b ac c d f f bi d c d b b m mm m m Susiquot Lyszcky 1O Building BDDs Exercise 2 0 Build aBDD for f abc b d c d Use the variable orde ngb s c s d s a partiai Expansiun fD fD With respectm Compute cofactors of fb and W with respect to c second variable in ordering b ac c d equivaient f a Emacturs we can E create a sin i g e nude reduced fm d bi d c d rm d w d ECE 67425752 1 am Susan Lystcky Building BDDs Exercise 2 BuildaBDD for f abc b d c d 0 Use the variable orde ngb s c s d s a 0 E partiai Expansiun Wim respecttu u Compute cofactors of by fm and W with respect to d third variable in ordering f no id he d he d fb c d 1 fbc d fbc d fnw 0 ECE 67625751 22 a 29 Susan Lystcky Building BDDs Exercise 2 0 Build aBDD for f abc b d c d Use the variable orde ngb s c s d s 3 Compute cofactors of fm with respect to a fourth variable in ordering fun a apansiun With respect in a finai EDD boa 39 bca 39 Ecn 67425751 73 am Susiquot Lyszcky Building BDDs Exercise 2 BuildaBDDforfabcb dc d a 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a x x xaoao x x x xaooou39 aaco x xoo x xco x xooo Aoioaoao odoaoaon Addoaoaoooaoooao Does work Ecn 67625751 2o am Susiquot Lyszcky 12 BDD to Boolean Function Exercise 1 0 Can we go from a BDD to a Boolean function 39 Sum all paths from function node to terminal nodes be b Fb bca c d b d bca bc d b d F bca bc d b d cFE c FE 03 c d ca c d aFa a Fa 31 a0 a0 a Ecn 67425752 75 am Susiquot Lyszcky BDD to Boolean Function Exercise 2 0 Another Example F abc39 ab39 a be b Fb bc b 1 bc b aFa a Fa abc b a 1 abc ab a Ecn 67625751 25 am Susiquot Lyszcky 13 Reduced BDDs BDD resulting Building BDDs Example I slide 19 39 We have isomorphic subgraphs potential for reduction Reduced BDD is unique for a given an ordering To obtain ROBDD Reduced Ordered BDD iterative apply 39 Identify isomorphic subgraphs 39 Remove redundant nodes isomorphic subgraphs Ecn 67425752 7 am Susan Lyszcky Reduced BDDs To obtain ROBDD iterative apply CONT I Identify isomorphic subgraphs I Remove redundant nodes Isomorphlc subgraphs Ecn 67625751 2x am Susan Lyszcky 14 Conclusion Binary Decision Diagrams BDDs 39 Representation of Boolean functions 39 Function to BDD Constmction 39 BDD to Function deconstmction 39 Reduced BDDs ECE 67425752 9 am Susan Lyszcky 15
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'