patternMinor
Converting truth table to algebraic normal form
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):
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.
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*x4But, 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.