Algebraic normal form

From Wikipedia, the free encyclopedia

In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula is considered to be in ANF if and only if it is a single algebraic sum (XOR) of a constant $a 0$ and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomials" (Russian: полиномы Жегалкина) and as "Positive Polarity (or Parity) Reed-Muller" expression.

Putting a formula into ANF makes it easy to identify linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.

The general ANF can be written as:

$f(x_1, x_2, \ldots, x_n) = \!$	$a_0 + \!$
	$a_1x_1 + a_2x_2 + \cdots + a_nx_n + \!$
	$a_{1,2}x_1x_2 + \cdots + a_{n-1,n}x_{n-1}x_n + \!$
	$\cdots + \!$
	$a_{1,2,\ldots,n}x_1x_2\ldots x_n \!$

where $a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*$ fully describes $f$ .

For each function $f$ there is a unique ANF. There are only four functions with one argument: $f (x) = 0$ , $f (x) = 1$ , $f (x) = x$ , $f (x) = 1 + x$ (all of them are given in the ANF). To represent a function with multiple arguments one can use the following equality: $f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) + x_1 h(x_2,\ldots,x_n)$ , where $g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n)$ and $h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) + f(1,x_2,\ldots,x_n)$ . Indeed, if $x 1 = 0$ then $x 1 h = 0$ and so $f(0,\ldots) = f(0,\ldots)$ ; if $x 1 = 1$ then $x 1 h = h$ and so $f(1,\ldots) = f(0,\ldots) + f(0,\ldots) + f(1,\ldots)$ . Since both $g$ and $h$ have less arguments than $f$ it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of $f(x,y)= x \lor y$ (logical or): $f (x, y) = f (0, y) + x (f (0, y) + f (1, y))$ ; since $f(0,y)=0 \lor y = y$ and $f(1,y)=1 \lor y = 1$ , it follows that $f (x, y) = y + x (y + 1)$ ; by opening the parentheses we get the final ANF: $f (x, y) = y + x y + x = x + y + x y$ .