Boolean Functions: Difference between revisions
Line 52: | Line 52: | ||
The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>. | The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>. | ||
Revision as of 15:07, 23 September 2019
Introduction
Let [math]\displaystyle{ \mathbb{F}_2^n }[/math] 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 [math]\displaystyle{ 2^n \mbox{ elements, }\mathbb{F}_{2^n} }[/math]. A function [math]\displaystyle{ f : \mathbb{F}_2^n\rightarrow\mathbb{F} }[/math] is called a Boolean function in dimenstion n (or n-variable Boolean function).
Given [math]\displaystyle{ x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n }[/math], the support of x is the set [math]\displaystyle{ supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \} }[/math]. The Hamming weight of x is the size of its support ([math]\displaystyle{ w_H(x)=|supp_x| }[/math]). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\ne0 \} }[/math]. The Hamming distance of two functions f,g is the size of the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g)) }[/math].
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.
x | f(x) | ||
---|---|---|---|
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 [math]\displaystyle{ \mathbb{F} }[/math] 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, [math]\displaystyle{ d^0f=\max \{ |I| : a_I\ne0 \} }[/math].