1
$\begingroup$

Let $p$ be the six-figure Boolean function with the following definition:

$p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{cases} true & \text{if } x_{0}=x_{5} \text{ and } x_{1}=x_{4} \text{ and } x_{2}=x_{3}, \\ false & \text{else.} \end{cases}$

This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a palindrome. Provide a BDD for $p$ relative to a variable ordering of your choice.

My problems begin when I try to define an appropriate variable ordering, so I am only able to guess it: $x_{0}=x_{5} < x_{1}=x_{4} < x_{2}=x_{3}$. I'm actually pretty lost with this exercise and any help is much appreciated (sorry for not being able to provide a better own approach).

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ In you answer you test whether all variables are true. Instead you should test $x_0=x_5$ etc. The order of variables seems sensible to me. $\endgroup$ – Hendrik Jan May 3 '13 at 8:58
  • $\begingroup$ @Hendrik: Thank you, Hendrik. Can you check my updated solution, please? $\endgroup$ – Uriel May 3 '13 at 13:26
  • 1
    $\begingroup$ Seems OK to me: the BSD closely follows the description of the formula. $\endgroup$ – Hendrik Jan May 3 '13 at 13:29
  • 1
    $\begingroup$ PS. Donald Knoth in his Volume 4 TAoCP on BDD's says it is sometimes convenient to allow repetitions of the T and F leaves "to avoid excessively long connecting lines". I do not whether you are allowed to have two F-nodes at the bottom, but it would remove some of the clutter. $\endgroup$ – Hendrik Jan May 3 '13 at 13:35
  • 1
    $\begingroup$ There is two spurious lines going out of x0. (BTW, you are allowed to anwer your question, I wonder if it wouldn't be better to do so and remove the answer from the question). $\endgroup$ – AProgrammer May 3 '13 at 13:47
2
$\begingroup$

So finally this should be the correct solution:

The variable ordering is $x_{0} < x_{5} < x_{1} < x_{4} < x_{2} < x_{3}$. The BDD is:

enter image description here

Improve this answer
$\endgroup$
1
$\begingroup$

The wikipedia article has a fairly good example in the "Variable Ordering" section. By carefully picking the order we evaluate the variables in, we can come to (at least some) decisions sooner.

In your case, if we know that for example $x_{0} = true$ and $x_{5}=false$, we can immediately answer $false$, regardless of the values of the other variables. You should be able to extend this to a full BDD of reasonably small size.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer, Luke. I've edited my question and it would be nice, if you could check it. BTW: Any help in my other BDD-related question would be much appreciated, too. $\endgroup$ – Uriel May 3 '13 at 7:53
  • 1
    $\begingroup$ @Uriel, that looks good to me. $\endgroup$ – Luke Mathieson May 4 '13 at 1:17
  • $\begingroup$ Thank you. May I ask you for some assistance with my other BDD-related question? I am sure only a few words would help a lot. $\endgroup$ – Uriel May 4 '13 at 7:33
0
$\begingroup$

Can you show us what you've tried so far? The problem says you can choose any variable ordering you want, so I'm a bit puzzled why you are trying to choose an "appropriate" variable ordering or guess a variable ordering. I suggest you choose any variable ordering you want (anything, really, it doesn't matter what you choose, just pick one), and then try to build the BDD. Why don't you try that, and then show us what you got? At that point we might be able to help you better.

P.S. When we say a variable ordering, we mean an ordering: a list of the variables in some order. An example of a variable ordering would be $x_0,x_5,x_1,x_4,x_2,x_3$. (I'm not sure what's going on with $x_0=x_5$; that's not a valid part of a variable ordering.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've now provided a solution in my question. Please check if it is correct. Could you also have a look into my other BDD-related thread, please? Thank you. $\endgroup$ – Uriel May 3 '13 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.