HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Converting truth table to algebraic normal form

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
normalformtruthconvertingalgebraictable

Problem

Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?

I have seen that Sage has one implementation (official documentation):

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("12fe342a")
sage: B.algebraic_normal_form()
x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x3*x4 + x0*x1*x3 + x0*x1*x4 + x0*x2*x3*x4 + x0*x2*x4 + x0*x3*x4 + x0*x3 + x0 + x1*x2*x4 + x1*x3 + x1*x4 + x2*x3*x4 + x2*x3 + x2*x4


But, nowhere I could find the algorithm.

It would be helpful if someone kindly explains with a suitable example.

UPDATE The answer can be found here. It is copied below.

Solution

The sage source code implies that algebraic normal form is the same as the Fourier expansion of the function (over the group $\mathbb{Z}_2^n$, where $n$ is the number of input bits). You can compute the Fourier transform using the well-known FFT algorithm(s).

Context

StackExchange Computer Science Q#30165, answer score: 2

Revisions (0)

No revisions yet.