samsung galaxy v mod

in last class, we have introduced the datastructures called binary decision diagram and with the help of this binary decisiondiagram, we can represent any boolean function or expression. and we have seen, how to constructthis particular binary decision diagram. so construction can be done from your twotable, where we are going to get a binary decision tree or we can use the shannon expansionof your boolean expression to construct the b d d, binary decision diagram. and afterthat we have seen some reduction rule basically, we have 3 reduction rule; 1 elimination ofduplicate terminals removable of redundant nodes and margining of duplicate non-terminals.with the help of these 3 reduction rule, we can reduce the bdd and we get reduced binarydecision diagram. and in most of the cases,

we have seen that we are going to get a compactrepresentation of boolean function; if we use reduce b d d, reduce binary decision diagram. but, when you look into the construction ofour b d d, we will see that we are not putting any restriction on the ordering of variable,the way it may appear in our bdd and again we are not giving any restriction of the occurrenceof variables in a particular path. it may appear in many places, because if welook into the definition we are saying that a binary decision diagram is a finite dagwith an unique initial node. it is a finite dag directed as i click up with an initialunique node, where all terminals are labeled with 0 or 1; all non-terminal nodes are labeledwith boolean variable. so, if we are having

a boolean expression, we are having thoseparticular variable in the boolean expression and the term non-terminal nodes will be labelby this particular boolean variable and its non-terminal nodes are having two outgoingedges; one represent by dash line which specifically indicates, it is the valuation of that particularvariable is 0 and another one is given by solid line which says that, the valuationof this particular variable is 1. so this is the definition of binary decisiondiagram and we can construct binary decision diagram of any boolean expression and whilewe are talking about this or when you look into the definition of this particular b dd, it is not talking about any, not talking anything about your occurrence of that variables,how many times it should occurred? or it is

not keeping any particular ordering. so, if you look into this particular binarydecision definition of binary decision diagram, then will say that, this is a binary decisiondiagram. this is simple dag; we are having three variables say, it is a function of threevariable f x y z. so x i am having over here, then this is dash line indicate the valuationof this x is 0 and valuation of this particular x is 1. like that y z’s are another variableand these are the two terminals known one is 0 and second one is 1. so if you look intoit you see that, here in this particular case this particular x is appearing twice in thisparticular path because as per definition we do not have any restriction. similarly,we can say that y is also appeared in two

different position but if they are in a differentparts. now in this particular case if you look intoit, then by looking into this particular variable b d d, we are going to see some problems.we are talking in that particular case, we are going to have the notion of consistentevaluation path and inconsistent evaluation path. so when we draw this particular b dd, some of the path may be in consistent; i will say why it is inconsistent. so dievaluation of this boolean function will be done through consistent part only. now youjust see that, i am saying that this is x variable here i am talking x equal to 0 andin this particular part i am talking x equal to 1. when value of x equal to 0, i am goingto take decision of y, this is in this particular

part y equal to 0 and in this particular pointy equal to 1. after that when i come to this particularnode, then again i am going to take decision on x; then i am going to say that in if afollow this particular path, then x equal to 0 and if i follow this particular partthen x equal to 1. now this is the way that we can see an ultimately, we are going toget this functional value. now if i follow this particular path in this evaluation path,it is same for that value of x equal to 0 and value of y equal to 0 and we are goingto say that, the functional value is 0 if x equal to 0 and y equal to 0; it is independentobject in this particular evaluation path. now if i look into this particular evaluationpath, i am showing by double line. now what

happens? i am going to say that, x equal to0 and valuation of y equal to 0 and x equal to 1. now in this particular path you justsee that, value of x is taken as equal to 0 and it is also taken as x equal to 1. now,when we are going to look for a valuation of any particular function at any instant,we can have only one valuation for one variable; so just say that if i am randomly writingon function say f equal to x y plus x bar z.now in this particular case, when i am going to look for the valuation or evaluation ofthis particular boolean function, either i am going to say that, evaluate it either xequal to 0 or i am going to say that either x equal to 1. so for these two different combination,i am going to get two different valuations,

but in this particular path, what will happen?the value is treated as x equal to 0 as well as x equal to 1 which is not possible andwhich is not permitted. so in this case we are going to s ay that, this is an inconsistentpath. so that means, we are having the notion of inconsistent path in b d d, if we lookinto the basic definition of bdd that means; the valuation of the function or evaluationof the function has to be done through consistent path only that means; we should not look forthe inconsistent. now due to this particular problem, we aretrying to eliminate this particular problem and in this particular case, what we are goingto do; we are going to put some restrictions on the occurrence of the variables and inthat particular case, we are going to put

a particular ordering of that variables andafter putting this particular ordering of the variable, we are going to get orderedb d d; ordered binary decision diagram. so in case of ordered binary decision diagramthat means; variable will come in a particular order. let consider that, x 1, x 2, x n bean order list of variables without duplication and let b be a b d d, all of whose variablesoccurs somewhere in the list. now we are considering a bdd where, all the variables of this particularlist is occurring somewhere in this particular bdd and we are saying that, this is an orderlist where duplication is not allowed. we say that b has an ordering x 1, x 2, x n,if all variable of b occur in that list and for every occurrence of x i followed by xa along any path in b, where i is less than

j that means; if we are going to fallow thisparticular ordering say x 1 to x n. so when we draw this particular b d d, then x 1 mustalways come before x 2 or may be x 1 always comes earlier point of x n; it should followthis particular ordering. so when we are following or practicing thisparticular ordering of b d d, then we will find that, one particular path only 1, thevariable will appear only once that means; since it is appends only once. so that multiplicityof valuation like, x equal to 0 and x equal to 1 that when the way we have seen in theearlier example we will not occur. so that means; in case of ordered b d d, we are goingto follow a particular ordering of the variable. just a simple example you see that, i am havingan bdd over here and we are saying that, we

are having five variables x 1 to x 5 and weare considering this particular ordering that means; x 1, x 2, x 3. x 4 and x 5, this isthe ordering of variable. when we mention this particular ordering, then what we haveto see that x 1 always must occur before x 2, x 3, x 4 and x 5. similarly, x 3 must alwaysoccur before x 5 in any path in this particular b d d. so if you look in any path, you willfind that this is x 1, x 2, x 4 then we are having evaluation values.so now where it is saying that, it is evaluate everything this particular ordering that means;x 3 is not coming before x 2 in any of path. similarly, x 5 is not coming before x 1 inany of the evaluation value. so in this particular case, we are going to said this is an orderedbinary decision diagram and that means the

variables are following a particular ordering.since they are following a particular ordering, duplication occurrence of a multiple timesof a variable in a particular path is not allowed. so this the way that we can say thisis ordered binary decision diagram. similarly, this is another binary decisiondiagram, ordered binary decision diagram and in this particular case, we have followingthese particular ordering say; x 5, x 4, x 3, x 2, x 1. that means when you look a nameevaluation path in this particular path the variable must occur in this particular orderingthat means; x 5 will come first then x 3, then x 2, then it is coming to the terminalnode 1 so it will follow this particular 1. now when we are using this particular orderedbinary decision diagram, then variable will

appear in a particular order in any execution,any evaluation path of this particular b d d. so appearing a particular variable multipletimes in a particular path is avoided that means; the notion of in consistent path isavoided over here that means; all evaluation paths are now consistent. so this is the notionabout ordered binary decision diagram, so we are going to pull a particular orderingof the variable. now if you consider this particular b d d,just say i am drawing a random bdd over here, i think in last class also i have drawn thisparticular b d d; now slickly sensed a level over here. so in this particular case, i amsaying that it is not an ordered b d d; why it is not a ordered b d d? it is not fallowingany particular order in an angle.

say, if i fallow this particular path, thenthe ordering is your a, b, c. this is the ordering of variable in this particular modelbut if i fallow this particular order path, evaluation path, then i am going to get theordering as your a, c, b. you now see that, a is appearing before b is all right but inthis particular path b is appearing before c and in this particular path c is appearingbefore b that means; it is note following any particular ordering of the variable, sothat is why it is not an ordered b d d. secondly, we are saying that, this is nota reduced bdd why? we can see some instances look into this particular node c, we are havinga retardant test over here. so c equal to 0 or c equal to 1 it is equal to 0 that means;this is retardant test; so this retardant

test can be removed. secondly if you lookinto this particular two nodes, b equal to 0 it is evaluated 0, here also b equal to0 evaluated 0; in this case b equal to 1 evaluated to 1 b equal to 1 evaluated to 1 that means;these are read you can say that duplicate non-terminals. so these non-terminals canbe merge to one non-terminal; so since we can apply the reduction rule to this particularb d d. so that is why it is not an reduced b d d, this is not ordered because we arenot having the similar order in out of it and it is not reduced; so this is simple examplethat i am giving. now we are having some impact of the chosenvariable. now we can say that i am going to say that we are going to put a variable ordering,say some x i am having some variable x 1,

x 2, x 3 like that say x n; this may be onevariable ordering. secondly i can say that; x n, x n minus 1, x n minus 2 like that upto x 1 this may be another variable ordering. so with a help of this particular variableordering, i can get an bdd i will say that, this is your bdd b 1 and with a help of thisvariable ordering, i can again have the bdd representation of the given function and isay that this is your b 2. now we are getting these two b d ds but these two b d ds arerepresenting the same boolean function. now after that will use the reduction of thesethings, so we are going to get reduce order binary decision diagram. now in this particularcase, we have to see what will be the size of b 1 and b 2, it may happen that the sizemay vary in both the cases; one may be bigger

one and one may be smaller one. so that meansthe ordering of variable is going to material doped for the size of our bdd; i will explainthis things with the help of one simple example. so just see that, consider this particularboolean function f, we are saying that x 1 plus x 2 x 3 plus x 4 x 5 plus x 6 like thatup to x twice n minus 1 plus x twice n that means; we are having twice n variables. sothis is a function of twice n variable and this is simple function. now in this particularcase, if we choose the variable ordering x 1 to x 2 up to x n x twice n say this is oneparticular variable ordering. then in that particular case what happens, we can drawthe bdd for this particular function and the ordered bdd will have twice n plus two nodes,we will see. so we can construct the bdd for

this particular boolean function and thatparticular boolean function will have 2 to the power twice n plus two nodes and we willsee that, no more deduction can be possible and we can said that, this is the reducedorder binary decision diagram. on the other hand, if we choose the variableordering something like that x 1, x 3, x 5 then up to x twice n minus 1 then x 2, x 4,x 6 up to twice n that means; all the odd subscription i am going to put first and theneven subscription i am going to put that all. so this is also possible variable ordering,so if we use this particular variable ordering, then will see that total number of nodes thatwill be having is your 2 to the power n plus 1. so, if we having n twice n variable thetotal number of your this things, that nodes

that will appear in this bdd is your 2 tothe power n plus 1 and the earlier case it is twice n plus 1. so you can see that theyhave considered difference of our size of the bdd and it basically depends on the variableordering. you just see, this is the bdd i have drawnthis is basically the same function x 1, x 2, x 3, x 4, x 5, x 6 and the variable orderingthat we are having is your x 1, x 2, x 3, x 4, x 5, x 6. so in this particular case,i am getting this particular bdd i am having six non-terminal nodes and two terminal nodes. now if i sends the variable ordering, thenwe are going to get this particular representation this bdd so here, the variable ordering basicallyi am taking x 1, x 3, x 5, x 2, x 4, x 6;

this is the variable ordering x 1, x 3, x5 then x 4, x 6, here x 3 separate like that. so in all the evaluation path, you will findthat it is following this particular variable ordering. now when i am having this particularvariable ordering, then you see that i am getting a b or b d d.so this is the same function i am representing with one ordered b d d, so we are orderingis this from x 1, x 2, to x 6 and the same boolean function i am representing with anotherorder bdd where the order is different and we have see that the size is more. so thesize basically, size of the ordered bdd depends on your the variable ordering and if you lookinto this particular things no more reduction rule is possible for this particular b d dsand on the other hand, for this bdd is also

no more reduction rule is possible. so theseare basically, reduce ordered binary decision diagram. so that is why you are saying that a bdd issaid to be reduced, if none of the reduction rule can be apply and similarly, for orderedbdd ordered binary decision diagram we are going to said that it is a reduce orderedbinary decision diagram robdd if none of the reduction rules can be apply in of order.so eventually you are coming to reduce order binary decision diagram. so by it is a binarydecision diagram so variable are having a particular ordering so we are going say thisis the ordered binary decision diagram. entirely, it is a reduced one no more reduction ruleis possible so we are going to say this is

reduced order binary decision diagram andeventually we are going to worked with robdd, which is having all the required propertiesfrom us. now in this particular case you just see that,already i have mention about this particular ordering of variables depending on the orderingof our variables, the size of our ordered bdd will vary. in some cases, we are goingto get a compact representation and in some cases, we are going to get slightly biggerrepresentation or bigger ordered bdd or bigger reduce ordered b d d.now, how to get the proper variable ordering? so, that we can get a compact representationof this particular boolean function, so that means we have to look for the proper variableordering but to get the proper variable ordering

to get a compact representation of the functionin bdd is a hard problem. we do not have any method or we do not have any algorithm tosay that, this particular variable ordering is the best variable ordering and it willgive us the compact representation of a given boolean function.so this is a hard problem, it is difficult to find out that particular based variableordering. so this is a open problem plus till working on it whether it can be solve or not.since it is an open problem, it is a hard problem. so currently, we are using some heuristicsand with the help of this heuristics method, we will try to find out some variable orderingwhich are going to give us some compact representations. it may not be the minimal one the bdd that,we are going to get may not be minimal one

but it is going to give us some compact representation.so we apply some heuristic and use by using this particular heuristic thing, we try tofind out some variable ordering and after that, we apply this particular variable orderingto construct the bdd and in most of a cases, we have found that we are getting a each andevery good size of bdd representation of any function. now, we have introduce a data structure callbdd binary decision diagram, which is use to represent any boolean function and lateron we have seen that; ordering of the variable and reduction of that particular ordered binarydecision diagram and eventually we are coming to ordered binary decision diagram and weuse this particular robdd to represent any

boolean function. now after that we now, since we are havingthis particular bdd representation of boolean function, we may need some algorithm or weneed some method to work with those particular bdds. now once you just see that i am givinga boolean function and you have come up with a variable ordering or you have chosen a particularvariable ordering, then we are going to construct the bdd, or ordered bdd for that particularfunction and you can very well constructed, with the help of shannon’s expansion ofthe boolean function. but eventually whatever you are getting it whether it will be a reducedone or not, you have to check it or if it is not reduced one, then you have to constructthe reduce bdd reduced ordered binary decision

diagram and already we have mention that,we are having three rules to go for a reduce bdd and we can apply this particular threerules to the initial b d d. now we will going to see an algorithm, weare going to put this particular rule in an algorithm form and we will say or we willget an algorithm call the algorithm reduce and we will apply this particular algorithmreduce to reduce any bdd. so basically, what will happen in this particular algorithm reduce,we are going to give a bdd or basically we are going to give a ordered bdd as an inputand the output, that we are going to get a reduce order bdd and the variable orderingof the output b d ds will be same as with the input bdd. so we will look into this particularalgorithm.

so, if we are going look an ordering of somevariable say x 1 to x l that means; we are having l variables, then we can have at mostl plus 1 layer in our bdd. so we are going to have l plus 1 layer at most, but in somecases in some part it may be less also because that particular function may be independentof that variable. now algorithm traverse this particular, thatalgorithm reducible traverse that b, that final decision diagram b layer by layer ina bottom-up fashion. so we are going to have a representation of our boolean function bddrepresentation and this algorithm reduce is going to traverses it from the bottom layerto the top layer. so that means we will start form the terminal nodes and after that, wewill traverse it back to the root nodes and

eventually, we are trying going to apply somerules; so that we can get the reduce bdd. now here in this particular case we are goingto an assign an integer label to each node, so first one is the labeling after node. sosay if i am having some bdd something like that, say this is your x, this is variabley we are going to have some ordering. so in this particular case, we are going to assignsome integer label to each node, i can say that i am not assigning that integer label3 to 8 and i am assigning that integer label 2 to 8 and i am going to said that, integerlabel 4 assign to this particular reduce. so this is an integer label of these particularnodes and we are going to say that, this is basically the id of this particular node,id of the node.

so basically we are going to give an id andid is nothing but the integer label of its node and we can say that id of a particularb d node and will be equal to id of m if the sub robdds with root nodes n and m denotethe same boolean function. so basically if sub bdd denotes the same boolean function,then we are going to give them the same your this thing, so recall integer label just iwill say that this is one node say labeled with your x and say this is y. so with evaluation0, we are going to same node and with evaluation 1, we are coming to same node say this isz and z. now in this particular case, what will happen?you just see that and after that we may have this particular bdd. now for is particularnode, say this is n i am talking about and

say this is m. so once we take the value ofx equal to 0, it is going to look for this particular sub bdd. similarly, for this particularnode also say y is equal to 0, then sorry if they are having the same. so in this particularcase, it is also x is equal to 0, they are going to have the some sub bdd. similarly,for 1 both are having the same sub bdd that means; both this particular nodes are evaluatingthe same sub formula for value x equal to 0 and x equal to 1. so in that particularcase, we are to give the same label to this node n and m so we are going to give somelabel or id and this label will be same for this particular this nodes. so if they aregoing to have the same sub b d ds, then their label will be same; this is in the rule throughassign the label to each and every node.

and another one we are going to define whichis basically two function; one is your low and one is your high. so for every non-terminalnodes we define a functional call lo n, so this is basically low to be the node pointingto via the dashed line from n and similarly, we can have hi of n which is basically high.so if i am having any node say on over here, so i can have the dash line and solid line.so in this particular case, are the label of this particular node is a 3 and label ofthis particular node is say 4. so in this particular low of n, it is goingto written this particular label 3 because it is low to be the node pointed to via thedash line; so it is pointing this particular case. similarly, high will written the value4, because it is pointing to this particular

node whose label is 4. so basically low allow,low and high it say are two function, it is going to give me the nodes pointed by dashline and node pointed by solid line respectively. so we are defining these two functions, saywhen with the help of this thing, we are going to construct this particular reduce algorithm;so first task is to label each and every node. now next task is to label the nodes, so howwe are going to label the nodes? so label the first label say 0 to the first 0-nodeit encounters. so for basically say, we are going to follow from the terminal nodes andfollowing in the bottom of expose approach. so first we are going to get some node 0-node,we may have one 0-node and more 0-node label by 0. then we are going to assign a label0 to those particular 0-nodes and similarly,

we are having some nodes which are label terminalnodes, which are labeled with 1 and we are going to assign label 1 to those particularnode. so if we are having more 0-nodes, we are going to give the same label to thoseparticular 0-nodes and we are going to give a 0, label 0 and we may have more 1-nodesto all the 1-nodes, we are going to get label s 1. so basically this is the starting ofour labeling algorithm and we are starting from the terminal nodes and we are going tofollow the bottom of approach. now what we can say, now in this particularcase, we are giving that label 0 and 1 now. later on what we are going to do, the nodeswhich are having the same label will be merge together basically, this is a second phaseof our reduce algorithm first we are going

to label each and every node and next phase,we are going to merge the nodes which are having the similar label. so in this particularcase, all 0-nodes will be label merge to 1-node then 1-node will be merge to 1-node labelby 1. so this is nothing but the reduction rule 1, that we have elimination of duplicateterminals so that means; we are going to take care of this duplicate terminals one, sayremoval of duplicate terminals so all zero node will be merge to one 0-node and all onenodes will be merge to 1 1. now secondly if we are having now, once welabel those particular terminal nodes, next we are going to follow the bottom of approach.then we are going to get some non-terminal nodes, labeling of non-terminal nodes givenan x i node n and already assign integer label

to all nodes of layer i is, layer is greaterthan i that means; when we follow this particular labeling. so this is i am coming label i,then i plus 1, then i plus 2 like that up to terminal labeling. when we come to labelthis particular node, then what it will happen? all the nodes below this particular labelparticular label must be marked, we should have all the integer labeling of all thoseparticular node below this particular then only we can label.since we are following the bottom up approach so when we reach this particular node, thenall the nodes below this particular node will be all ready label. if the label l id lo nis same as id hi n, then we said id n to be that node, of that label that means; you cansay that, if i am having a particular node

n over here and say low and high both arecoming to one particular node say m. so in that particular case say, id of low n saythis is say i can have say some label 3, so id of low of n is equal to 3 similarly, idof i of n is equal to 3. so if both are same then what will happen?we are going to give the same label to this particular node, so i can say that this isalso labeled with 3. so what basically it means, that now in the next page we are goingto merge them together, so these will be merged together because they are having the samelabel and you said that this is nothing but the reduction rule of redundant nodes speciallyremoval of redundant node because here i am having some redundant test for both 0 and1, it is going to give the same sub bdd. so

if the id of low n and id of high n is same,then n will get the label of this particular n only. so this is basically we are labelingputting an integer label and basically, it is going to help us to use this particularreduction rule removal of redundant nodes. next we are going to say that, already i havesay that if i am coming to x i node, then all the nodes below that label is alreadymarked. now if there is another node m such that m and n have the same variable x i thatmeans; i am having a node n and i am having a node m and both both are labeled with samevariable say x i. now what will happen in this particular case, if id lo n is equalto id lo m that means; this is low and this is low some label we having sorry this islow.

similarly, i and i coming to the same nodesor it may cover to the define node but both are having the same label. so in this particularcase, say low and low n and low m is coming to the same sub bdd and similarly, high nand high m are coming to the same sub bdd then id of n will be equal to id of m. soif i am having a already say, id of this particular nodes say m say is equal to 5, then i am goingto assign the same label to this particular node also and it is 5. so if you see thisthings later on we are going to merged them together that means; we are this is basicallycorresponds to the rule of removal of your duplicate nodes. basically these two are duplicatesbecause; they are having the same sub bdd below that they are going to evaluate thesame sub function so we can merge them together.

so this is basically nothing but the removalof these particular duplicate nodes. so in this particular case, if it is not gettingthis to two nodes say i am coming to your particular node x i and all the node belowthis particular node is label and if it is not following these particular nodes say,this is the first one and this is the second one; it is not following this particular twocases, then what will happen? otherwise we set id of n to be the next unused integerlabel. so here starting with integer 0 for the 0-node, then we are starting with integer1, then if they are not equal then i will go to next unused number 2; then go to nextunused number 3 like that. so if it is not following these two particular rules thatwe have already mentioned, then set id of

n to be the next unused number.so next unused number will be given me that means; it is an new node we are getting andit will be appeared or it will be present in r it will present in our reduced bdd. soonce we are having these things, then what we have going to do then already i have mentionedthat. the next phase what we have going to do? we are going to merge the nodes whichare having similar label that means; that can be removed. so just we are going to look an example say,this is an bdd we are constructing x y z and this is basically bdd also. so if you lookinto it how we are going to start it? first we are going to start the terminal nodes.so in this particular case, we are going to

give 0 to all 0-node and assign 1 label 1to all 1-nodes; this is the first two labeling the terminal nodes 0 and 1. then we are goingto look for this particular thing say, in this particular case z 0 is going to 0-nodeand 1 is going to 1-node. so since these two are define so it is going to get a new label.now when we are coming to this node, say these two are having define so it should get a anew level but secondly already we are having a z-nodes so we will compared these two nodesand the low of this particular z is same with low this particular one and high of this particularz is high of this one. so this node will get the same label over here because there theyare having the same some bdd for 0 and 1. and similarly, when i come to this particularnode z label by z, i can we find that they

are having two deferent nodes 0 and 1; soit should be at a defined label but if i consider about these nodes, then what will happen thebehavior is same so it is going to get this particular label 2. so now, first we are labelingthe terminal nodes, then we are coming one label up of after label this particular node;then will go to the next label. so since i am having three variables, so total we arehaving four labels you are distinct what we called non-terminal nodes for three variablesand one label is the terminal nodes. now similarly, now when we come to this particularnode, you just see that low of your this particular node is pointing to that label two nodes andhigh of these particular node is label 2 this particular label 2-nodes. so that means inlow of your this nodes is same with the high

of this nodes that means; this is removalof your redundant node. so since they are same this particular node is going to getthis particular label so it will be labeled with 2.now, when we come to this particular node, then we will find that low is coming to labeled1 and high is coming to label 2 that means; low and high is not giving the same representation,we are having the deferent representation, deferent sub b d ds, different function soit is bond to get a new label. similarly, again behavior of these two nodes are notsame, second third condition will also clear so it is going to get a new label and we areall going to labeled it by 3 so it is assigning a label 3.now when i am coming to these particular things,

then low of this particular node is 2 andhigh of this particular node is your 3. so id of low is 2 and id of high is 3 that means;they are having different sub function so it is going to get a new label 4. so we arestarting from this particular terminal nodes and we are following the bottom of approachand coming to this particular root nodes and we have label all this particular nodes. nowin this particular case, now next one is your merging of our duplicates nodes. so, if itis id of low of n is equal to id of low m and id of high n is equal to id of high mso which is the senior, then we have going to merged. so merging of duplicate nodes inthis particular case, these three nodes will be merged together.and secondly, we are having another one removal

of redundant nodes so if id of low of p issame as id of high of p. so this is say you have just saying that, this is labeled withp and this is a label n and m so that is why i am saying that n and m so that can be merged.hence similarly, it can be merged and now since for this particular node p low and highas same so you can remove these things. so basically these are the rules that we aregoing to apply so in this particular case, now we can merge these particular nodes whichare having the same label and eventually, we are going to get this particular reducebdd. so this is the reduced ordered binary decisiondiagram of the bdd that we have studied. so now with the help of this reduce algorithm,we can use we can reduce the b d ds and eventually

we are going to get a reduced ordered binarydecision diagram that means; we are having an algorithm called reduce where we are goingto give an bdd b. so that means; input is your ordered bdd and what output we are goingto get the output of this algorithm is your robdd, reduced ordered binary decision diagramand the variable ordering of the output bdd same with the variable ordering of that inputbdd. so now you just see that, we can construct a bdd for given any boolean function and afterthat after construction, we can use this particular reduced algorithm to get the reduce orderbinary decision diagram. now this is some properties you can see, nowreduced ordered binary diagram, binary decision diagram so the reduced ordered binary decisiondiagram representing a given function f is

unique. so if you are going to look a particularfunction f and we are going to construct the reduced ordered binary decision diagram ofthat particular function. then this particular binary reduced ordered binary decision diagramwill be unique with respect to that particular variable ordering because if you sense thevariable ordering then size will very because already we have seen that means you we aregoing to get that deferent representation deferent bdd. so with a particular variableordering we are going to get an unique representation. secondly, we are having a notion of, notionof compatible variable ordering. so if you conceder two bdds b 1 and b 2, if they arehaving a same variable ordering then we say that, they are having the compatible variableordering. and and this two bdds say b 1 and

b 2, if they are having the compatible variableordering and if they are representing the same boolean function, then their structureis same. you just see that we are going to get a unique representation with a particularvariable ordering so if two bdds are having compatible variable ordering and secondly,if they are representing in a same boolean function then these two bdds will be identical.so again that is why your are saying that for a particular variable ordering we aregoing to get an unique bdd, robdd representation. so that is why we are saying that robdd representationof any function is going to give us the canonical representation of that particular functionand secondly, already you have seen that how to apply this particular reduce algorithm,we are going to get the reduced bdd.

on the other hand, you can apply this particularreduction rule also and the order in which you are applying this particular reductionrule is immaterial, we are going to, always going to get the same reduced ordered binarydecision diagram. so this is the unique property, that we are having, that we are going to getan unique representation of a boolean function with respect to a particular variable ordering;that is why we say that robdd gives as the canonical representation of boolean functionso this is the main picture of robdd and you can use this particular bdd. now similarly, reduced ordered binary decisiondiagram we are saying that, if we are having two b d ds b 1 and b 2 and this b 1and b 2are representing say two boolean function

f 1 and f 2, say we are having one booleanfunction f 1 and we are saying that this is the bdd representation b 1 and we are havinganother boolean function f 2 and bdd representation b 2.now ordering of b 1 and b 2 are said to be compatible, if there are low variable x andy such that; x comes before y in the ordering of b 1and y comes before x in the orderingof b 2. so we do not have such type of scenario, then we can say that this is the compatiblevariable ordering that means; in b 1 if say x is coming before y, then in b 2 also x mustcome before y. so if y comes before x in b 2, then we are not going to say that thesetwo are having the compatible variable ordering. so now you can look for any variable orderingand we can look for two bdds, we will say

that these two bdds will have compatible variableordering, if they are having the same variable ordering. now, we can have any boolean function say,if i am having a function x, y, z say some random function i am going to say that, xbar y plus x z plus y z. now if we are having such type of function, that i can always keepsome chose some variable ordering say i am going to chose a variable ordering x, y, zand i can represent this particular function with the help of bdd b and if we apply thereduction rule or we apply the reduced algorithm to this particular b, we are going to geta robdd. so once we are getting this robdd, then whathappens? it is basically nothing but we are

representing this particular boolean function,we representing this particular boolean function with the help of robdds. now once we havethis particular robdd representation of this boolean function, now what we can do? alreadywe have mention that, most of the cases we are going to get the compact representationof our boolean function and after that we can do some operation, we can do some manipulationon this particular bdds also so for any function we are going to have the bdd representation.now this bdd representation is going to help us to take some decision very quickly so whatare those particular decisions? so first one is i am talking about test forabsence of redundant variables, say if say i am giving one particular function, can yousay that whether this function is redundant

of a this is independent of some variables.say i am giving this particular function x bar y plus x z plus y z can you see tell mewhat are independent of some variables? this is small function, we can see it and you cansay that it may be independent it may not be independent but if we are having a bddrepresentation then by looking into a structure of bdd, easily we can say that whether itis independent of some variable or not. so how we can say that? if the value of aboolean function say f x 1 to x n does not depends on a particular variable say x i,then any robdd which represent f does not contain any x i node. so if i am having abdd representation of a function say x is coming something like that, say this is y,say this is 0, 0 and say this is 1 so this

is a function f x, y, z. if i look into thebdd, in this particular bdd we have found that this particular b d ds not having thisparticular variable z. so we can very well say that this function is independent of thisparticular variable z. so test for absence of redundant variableis easily check by looking in the structure of this particular robdd because robdd isgoing to give us a unique representation with respect to particular variable ordering, soyou are not going to get any other representation for that particular variable ordering. soif one particular variable is not appearing in this particular structure; very well youcan say that, it is independent this particular variable.

similarly, we can say that test for semanticequivalence because with respect to particular variable ordering; it is going to give mea unique bdd representation. now if i am giving two function, say f 1 and f 2 and i am askingwhether f 1 is equivalent to f 2 or not, whether they are representing the same boolean functionor not. then what will happen? we are going to do some boolean manipulation on this particularf 1 and we try to say whether we can get the f 2 or not. now, if we construct now bdd b1 for f 1 and bdd b 2 for f 2, with a particular variable ordering that means; they shouldhave a compatible variable ordering. now once we construct this particular b dds for function f 1 and f 2; and eventually if we find that, both are having the identicallystructure. then we can say that both f 1 and

f 2 are representing the same boolean functionthat means; f 1 and f 2 equivalent. so the semantic equivalence can be check very easilyonce we construct or once have the bdd for these two functions, if they are having theidentical bdd representation with respect to a compatible variable ordering, then wecan say that these two functions are equivalent. similarly, we can say that, test for validitywe know when we say that, a particular variable boolean function is valid or not. for allvaluation of this particular variable it is evaluate to 1, then we can say that this isa valid function. so in this particular case, now if we construct a bdd and if your bddis your b 1, then we can always say that it is a valid function. so, basically we cansay that bdd b 1 if it is on the terminal

node, then we are going to say this is yourbdd b 1. so if i am giving any function f, now construct the robdd and with respect toparticular variable ordering and if this robdds happen to be your the bdd b 1, then we cansay that this is a valid function. so you just see that, if i am giving a long expressionto check whether it is a valid or not it is a the but if i am having a bdd representationand if bdd representation is b 1, then we can very well say that this is a valid function. similarly, test for implication, whether fimplies g or not so f implies g so this is something like that; f implies g is equivalentor knot of f or g. so in this particular case what i am going to do? i am going to havea take the negation of this thing so negation

of f implies g. so if i take the negationthat means what happens? i am going to get the knot of f or g applying de morgan’slaw, what i am going to get? this is your f and g that means; if i am going to constructthe bdd b f and knot of sorry, this is knot of this knot of b g and if this particularbdd is your b 0 because i am taking the negation you just see. so that that means the negationis an contradiction that means; your negation is a contradiction that possibility givesa satisfaction. so in that particular case, if this is equal to your b 0, that you cansay that, f implies g. so these is also but how to do this operation we are going to checkmay be discuss this things in our next class. similarly, we can say that test for satisfiability,when we say that a function is satisfiable

if for at least one valuation or even oneevaluation it gives the value as 1, then we can say that it is satisfiable that means;if i am having a function say f x, y, z then at least for one valuation it should be madeof functional value as 1. then in the particular case, we are going to say that this functionis satisfiable. now how to check it? now we have to look for all will be valuation orif we having a truth able representation and we are having ending one entry as 1, thenwe can say that it is satisfiable. so if i am having a bdd representation ofthis particular function and if this bdd representation is not equal to your b 0, if it is not b 0,then we can say that this is a satisfiable function that means; if it is b 0 for allvaluation it will go to b 0 that means, for

all valuation we are going to get 0. so ifthe resultant bdd is not equal to b 0, i can say that it is your satisfiable because forsome valuation it is going to get the terminal node 1.so by looking into the structure, looking into the resultant robdd because robdd isyour a unique representation of the function and which is the canonical representationof the function. if the robdd is not equal to your b 0, then you can say that the functionis satisfiable you just see that, now if we are having a boolean function and if we canrepresent this boolean function with the help of robdd with respect to a particular variableagain, then some decision can be taken very quickly like; whether it is valid or not?whether it is your satisfiable or not? whether

this function is independent of some variablesor not? whether two functions are equivalent or not? so such type of decision can be takenvery quickly. so, these are the advantage of using robdd. now as a one question, i am saying that applythe algorithm reduce to reduce this particular bdd. so i am giving in your obdd, orderedbinary decision diagram and you apply the algorithm reduce to it. so it is having threevariable x 1 and x 2, x 3 and the ordering is your x 1, x 2, x 3 so this is the orderingthat we are having and this is the given bdd. now apply the algorithm reduce to reduce thisparticular b d d. so in this particular case what will happen? first i am going to labelthese particular nodes.

so, in this particular case what will happen?all 0-node will be labeled with 0 and all 1-node will be labeled with 1 now, where labeledis particular terminal nodes, then we go up. now in this particular case, when i come tothis particular label x 3 so it is 1-node is coming to 1 and 0-node is coming to 0 thatmeans; your sub bdd is not same so we are going to have a order is s 2. and similarly,this is also in x 3,0 is going to 0 and 1 is going to 1. so, these are not same with0 and 1and secondly these two are having the same label x 2 same variable x 3 and x 3.so sub bdds are 0 for both the 0, it is going to one terminals for both 1, it is going tozero terminals. so, it will also going to get, going to get the same label with thisparticular x 3 so both are label with your

x 2.similarly, if i am coming to this particular node then if 0 is going to label 0 and 1 isgoing to label to that means; their sub bdds are not same so it is going to get a definelabel so i am going to label it which tree. when i come to this particular label with0, we are going to this particular label 2 with 1 also we are coming to this particularlabel 2. so in this particular case, it is going to get the same label with these twonodes, it is going to get x 2. now when i come to this particular node, 0is coming to your tree and 1 is coming to your label 2 so these are different. so inthat particular it is going to get a new label and we are going to say that, going to givea label 4. now this is, now we are starting

from the terminal nodes going in a bottomoperation and coming to the terminal nodes, this is root nodes and all labeling is over.so in that particular case, now next page is your merging. so, these three nodes are having the samelabel so we can merge together and ultimately we are going to get this particular reducedbdd. so merge all the nodes which have the same label so these tree are having the samelabel, we are going to reduce it to 1-nodes and accordingly; we are redirecting this particularin inputs and output edge. so, ultimately we are going to get this particular reducedb d d. so another question you just see that, considerthis particular boolean function x z plus

x z dash plus x dash y, is it independentof any variable? so this is a function x, y, z and it is having involved this particularx, y, z now you have to see whether it is independent of any variable or not. i thinkwe can simply construct this particular bdd so; this is your x if i am having a ordering.so x equal to 0, i have to take decision on y, if x equal to 1, then i have to take decisionon z. now if it is y is equal to 0, then my it is 0 and if y is equal to 1, then i amhaving 1. now similarly, if it is x z then if z is equalto 1 and then what will happen? x equal to 1, z equal to 1. so in this particular case,my functional value is 1 and if x equal to 0 1 and z equal to 0, then one functionalvalue is your 0 sorry, x equal to 1 and z

equal to 0 sorry, this is not. so in boththe cases, it will be one only because x equal to 1, z equal to 1; it is going to give me1, x equal to 1, z equal to 0, it is going to be 1.so in this particular case, i am having this particular redundant test so i can removethis one. so, in this particular case, eventually this is come to these particular points sothis is the resultant bdd and in this particular resultant bdd, z is not appearing over hereso we can say that, this particular function is independent of set. so this is small functioni can, we can do the boolean manipulation also what i am going to get from this functionx z plus z bar plus x bar y that means; what i am going to get? x z plus z bar is equalto 1, so this is x plus x bar y which input

also we can say that, this function is independentof the variable z but if i give a bigger expression, such type of manipulation may not be thatsimple. so if you have that bdd representation, from this bdd representation we can say that,this function is independent of variable z. similarly, you just look into this particularfunction very small function and simple function i am giving x z plus x z bar plus x bar, isit independent of any variables? is it test for validity? can you look for the validity?when i can say that it is valid, if the resultant validity is your 0s, just try to constructit again. again i can say that i am going to take decision of your so this is a verysimple it is from this equation itself, i can say that it is y is not there so it isindependent of y. so i am going to take x x may take value as

0 and x may take value as 1. so when i amgoing to construct it, when x bar equal to 0, then my functional value is 1. now whenx equal to 1, then we have to take decision on this particular z. now when z is 1, thenx z is going to give me 1 and when z is 0, x 1 z 0 is going to give me 0 so in this particularcase i am going to have this thing. now eventually what will happen you just seethat, now this is a redundant test so i can remove it. so what i am going to get? thisis x sorry, this is terminal so i am removing it so 1 is come over here. now see that xis again this redundant test x is equal to 0 is 1, x equal to 1 so what happen? fromhere i can say that, i am going to get this particular bdd 1. so what are the bdd i amgetting? this is the bdd b 1 that means; for

all valuation the function is going to giveme 1. so since my resultant bdd is b 1 so what ican say that, this is a valid function. secondly, by looking into this particular function,i have said this is independent of y. now after looking into this particular bdd, whati can say that? it is independent of x, y and z that means; this function is independentof this all these particular three variables. so just see that, by looking into this particularbdd, we can take the decision very easily. so this is a small function i am giving butif i am going to give a bigger expression by inspecting this function, it would be difficultto say whether it is valid? whether it independent of some variables? but, once we get robddby looking into the structure of this particular

robdd, we can take many more decision quicklywith this i end of my lecture today. thank you.

Share this post