3
$\begingroup$

Karnaugh map is a method to simplify Boolean algebra expressions in two different notations sum-of-products(DNF) and product-of-sums(CNF). I need to find a minimized boolean expression in algebraic normal form (ANF) for a truth table. Is there a solution?

A solution is simplifying the boolean algebra expression in CNF or DNF then converting it to ANF. But is it minimized?

Is there a software to convert CNF boolean algebra expressions to ANF?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Why is this tagged linear algebra? $\endgroup$ – Doug Spoonwood Feb 14 '12 at 21:53
  • 2
    $\begingroup$ @Doug: Probably because the ANF can be understood by viewing the set of Boolean functions of $n$ variables as a vector space over $\mathbb F_2$ considering the basis consisting of all conjunctions of (not negated) variables. $\endgroup$ – Henning Makholm Feb 15 '12 at 1:11
6
$\begingroup$

As Henning Makholm pointed out, the ANF is unique. I will illustrate how you determine the ANF given the truth table for the function for the case of three variables.

The ANF of $f(x_1,x_2,x_3)$ is $$\begin{align*} f(x_1,x_2,x_3) &= a_0\\ &\quad \oplus a_1x_1 \oplus a_2x_2 \oplus a_3x_3\\ &\quad \oplus a_{12}x_1x_2 \oplus a_{13}x_1x_3 \oplus a_{23}x_2x_3\\ &\quad \oplus a_{123}x_1x_2x_3 \end{align*}$$ and we need to determine the $a$'s. We proceed as follows (working exactly in reverse order of the method outlined by Henning) by determining $a_{123}$, the coefficient of highest degree term, first and working our way downwards.

  • $a_{123}$ equals the parity of the Hamming weight of the function. That is, $a_{123}=1$ if the column labeled $f$ in the truth table has an odd number of $1$s in it, and $a_{123}=0$ if the column labeled $f$ in the truth table has an even number of $1$s in it.

  • We obtain $a_{12}$ by considering the four rows corresponding to $x_3=0$ as the truth table of a function $$\begin{align*}f_{12}(x_1,x_2) &= f(x_1,x_2,0)\\ &= a_0\\ &\quad \oplus a_1x_1 \oplus a_2x_2\\ &\quad \oplus a_{12}x_1x_2 \end{align*}$$ and applying the same technique as in the previous step. $a_{12}$ is the parity of the Hamming weight of the column labeled $f_{12}$ in this shorter truth table.

  • Similarly, we obtain $a_{13}$ and $a_{23}$ by considering truth tables for $f_{13}(x_1,x_3) = f(x_1,0,x_3)$ and $f_{23}(x_2,x_3) = f(0,x_2,x_3)$ respectively and finding the parity of the Hamming weights of the reduced functions.

  • Similarly, we obtain $a_{1}$, $a_{2}$, and $a_3$ by considering truth tables for $f_{1}(x_1) = f(x_1,0,0)$,
    $f_{2}(x_2) = f(0,x_2,0)$, and $f_{3}(x_3) = f(0,0,x_3)$ respectively and finding the parity of the Hamming weights of the reduced functions

  • Finally, $a_0 = f(0,0,0)$ can be just read off the truth table.

It is, of course possible to proceed in opposite order, but the method outlined above is related to Reed-Muller decoding for which you might find software available. Look also for canonical ring sum expansion.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

The algebraic normal form is unique (which follows from a simple counting argument), so minimality is not an issue.

You can construct an ANF directly from a truth table by finding the coefficients for the terms of low degree first. The constant coefficient is just the value in the 000..0 line in the truth table, and once you know what that is you can find the coefficients for all of the lines with a single 1, and so forth until everything is filled out.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ ANF itself isn't minimal though right? You'd have to factor out common ANDs from terms to make it minimal if i understand correctly. $\endgroup$ – Alan Wolfe Apr 8 '16 at 14:24
  • 1
    $\begingroup$ @AlanWolfe: Depends on what you mean by "minimal". For sure it is not necessarily the smallest expression built from $\oplus$ and $\land$ that computes a given Boolean function, if $\oplus$ is allowed to appear below a $\land$ in the expression tree. $\endgroup$ – Henning Makholm Apr 8 '16 at 14:34
1
$\begingroup$

Mathematica command :

BooleanConvert[expr,form] converts the Boolean expression expr to the specified form.

For example :

input : BooleanConvert[(! x || y) && (x || ! y), "ANF"]

output : ! (x $\veebar$ y)

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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