[Solved]: Binary decision diagram for a six-figure Boolean function

Problem Detail: 

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).

Asked By : Uriel

Answered By : Uriel

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:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11741

3.2K people like this

 Download Related Notes/Documents