Let be the vector space of dimension n over the finite field with two elements.
The vector space can also be endowed with the structure of the field, the finite field with .
A function is called a Boolean function in dimenstion n (or n-variable Boolean function).
Given , the support of x is the set .
The Hamming weight of x is the size of its support ().
Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set .
The Hamming distance of two functions f,g is the size of the set .
Representation of a Boolean function
There exist different ways to represent a Boolean function.
A simple, but often not efficient, one is by its truth-table.
For example consider the following truth-table for a 3-variable Boolean function f.
|0 ||0 ||0 ||0
|0 ||0 ||1 ||1
|0 ||1 ||0 ||0
|0 ||1 ||1 ||0
|1 ||0 ||0 ||0
|1 ||0 ||1 ||1
|1 ||1 ||0 ||0
|1 ||1 ||1 ||1
Algebraic normal form
An n-variable Boolean function can be represented by a multivariate polynomial over of the form
Such representation is unique and it is the algebraic normal form of f (shortly ANF).
The degree of the ANF is called the algebraic degree of the function, .
We identify the vector space with the finite field and we consider f an n-variable Boolean function of even weight (hence of algebraic degree at most n-1).
The map admits a uinque representation as a univariate polynomial of the form
Such representation is also called the univariate representation .
f can also be simply presented in the form but such representation is not unique, unless o(j)=n for every j such that Aj≠0.