Difference between revisions of "Boolean Functions"

From Boolean Functions
Jump to: navigation, search
Line 1: Line 1:
 
=Introduction=
 
=Introduction=
  
βˆ’
Let <math>\mathbb{F}_2^n</math> be the vector space of dimension <i>n</i> over the finite field with two elements.
+
Let 𝔽<sub>2</sub><sup>𝑛</sup> be the vector space of dimension 𝑛 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>2^n \mbox{ elements, }\mathbb{F}_{2^n}</math>.
+
The vector space can also be endowed with the structure of the field, the finite field with 2<sup>𝑛</sup> elements, 𝔽<sub>2<sup>𝑛</sup></sub>.
βˆ’
A function <math>f : \mathbb{F}_2^n\rightarrow\mathbb{F}</math> is called a <i>Boolean function</i> in dimenstion <i>n</i> (or <i>n-variable Boolean function</i>).
+
A function <math>f : \mathbb{F}_2^n\rightarrow\mathbb{F}</math> is called a <i>Boolean function</i> in dimenstion 𝑛 (or <i>𝑛-variable Boolean function</i>).
  
 
Given <math>x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n</math>, the support of <i>x</i> is the set <math>supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}</math>.
 
Given <math>x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n</math>, the support of <i>x</i> is the set <math>supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \}</math>.
βˆ’
The Hamming weight of <i>x</i> is the size of its support (<math>w_H(x)=|supp_x|</math>).
+
The Hamming weight of π‘₯ is the size of its support (<math>w_H(x)=|supp_x|</math>).
βˆ’
Similarly the Hamming weight of a Boolean function <i>f</i> is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.
+
Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.
βˆ’
The Hamming distance of two functions <i>f,g</i> is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.
+
The Hamming distance of two functions 𝑓,𝑔 is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.
  
 
=Representation of a Boolean function=
 
=Representation of a Boolean function=
Line 14: Line 14:
 
There exist different ways to represent a Boolean function.
 
There exist different ways to represent a Boolean function.
 
A simple, but often not efficient, one is by its truth-table.
 
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 <i>f</i>.
+
For example consider the following truth-table for a 3-variable Boolean function 𝑓.
 
<center> <table style="width:14%">
 
<center> <table style="width:14%">
 
   <tr>
 
   <tr>
βˆ’
     <th colspan="3"><i>x</i></th>
+
     <th colspan="3">π‘₯</th>
βˆ’
     <th><i>f(x)</i></th>
+
     <th>𝑓(π‘₯)</th>
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
Line 47: Line 47:
  
 
==Algebraic normal form==
 
==Algebraic normal form==
βˆ’
An <i>n</i>-variable Boolean function can be represented by a multivariate polynomial over <math>\mathbb{F}</math> of the form
+
An 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽<sub>2</sub> of the form
 
<center><math> f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). </math></center>
 
<center><math> f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). </math></center>
βˆ’
Such representation is unique and it is the <em> algebraic normal form</em> of <i>f</i> (shortly ANF).
+
Such representation is unique and it is the <em> algebraic normal form</em> of 𝑓 (shortly ANF).
  
βˆ’
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, 𝑑°𝑓=max { |𝐼| : π‘Ž<sub>𝐼</sub>&ne;0 }.
  
 
==Trace representation==
 
==Trace representation==
βˆ’
We identify the vector space with the finite field and we consider <i>f</i> an <i>n</i>-variable Boolean function of even weight (hence of algebraic degree at most <i>n</i>-1).
+
We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1).
 
The map admits a uinque representation as a univariate polynomial of the form
 
The map admits a uinque representation as a univariate polynomial of the form
 
<center><math>  f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n},
 
<center><math>  f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n},
 
</math></center>
 
</math></center>
βˆ’
with &Gamma;<sub><i>n</i></sub>  set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2<sup><i>n</i></sup>-1), <i>o(j)</i> size of the cyclotomic coset containing <i>j</i>, <i>A<sub>j</sub> &isin; 𝔽<sub>2<sup><i>o(j)</i></sup></sub>,  Tr<sub>𝔽<sub>2<sup><i>o(j)</i></sup>/𝔽<sub>2</sub></sub></sub> trace function from 𝔽<sub>2<sup><i>o(j)</i></sup> to 𝔽<sub>2</sub>.
+
with Ξ“<sub>𝑛</sub>  set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2<sup>𝑛</sup>-1), 𝘰(𝘫)  size of the cyclotomic coset containing 𝘫, 𝘈<sub>𝘫</sub> &isin; 𝔽<sub>2<sup>𝘰(𝘫)</sup></sub>,  Tr<sub>𝔽<sub>2<sup>𝘰(𝘫)</sup>/𝔽<sub>2</sub></sub></sub> trace function from 𝔽<sub>2<sup>𝘰(𝘫)</sup> to 𝔽<sub>2</sub>.
  
 +
Such representation is also called the univariate representation .
  
βˆ’
Such representation is also called the univariate representation .
+
𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math>  where π˜— is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>&ne;0.
 +
 
 +
=The Walsh transform=
 +
The <i>Walsh transform</i> π‘Š<sub>𝑓</sub> is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)<sup>𝑓(π‘₯)</sup>.
 +
With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> π‘₯·𝑦, the value of π‘Š<sub>𝑓</sub> at π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers)
 +
<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center>
 +
The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}</math> is the <i>Walsh support</i> of 𝑓.
  
βˆ’
<i>f</i> can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math> where <I>P</i> is a polynomial over the finite field F<sub>2<sup>n</sup></sub> but such representation is not unique, unless <i>o(j)=n</i> for every <i>j</i> such that <i>A<sub>j</sub></i>&ne;0.
+
==Properties of the Walsh transform==
 +
For every 𝑛-variable Boolean function 𝑓 we have the following relations.
 +
* Inverse Walsh transform:  for any element π‘₯ of 𝔽<sub>2</sub><sup>𝑛</sup> we have <center><math> \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)};</math></center>
 +
* Parseval's relation: <center><math>\sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n};</math></center>
 +
* Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements π‘Ž,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = |E^\perp|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center> for 𝐸<sup>βŸ‚</sup> the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.

Revision as of 10:21, 27 September 2019

Introduction

Let 𝔽2𝑛 be the vector space of dimension 𝑛 over the finite field with two elements. The vector space can also be endowed with the structure of the field, the finite field with 2𝑛 elements, 𝔽2𝑛. A function is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given , the support of x is the set . The Hamming weight of π‘₯ is the size of its support (). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set . The Hamming distance of two functions 𝑓,𝑔 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 𝑓.

π‘₯ 𝑓(π‘₯)
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 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽2 of the form

Such representation is unique and it is the algebraic normal form of 𝑓 (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, 𝑑°𝑓=max { |𝐼| : π‘ŽπΌ≠0 }.

Trace representation

We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1). The map admits a uinque representation as a univariate polynomial of the form

with Γ𝑛 set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2𝑛-1), 𝘰(𝘫) size of the cyclotomic coset containing 𝘫, 𝘈𝘫 ∈ 𝔽2𝘰(𝘫), Tr𝔽2𝘰(𝘫)/𝔽2 trace function from 𝔽2𝘰(𝘫) to 𝔽2.

Such representation is also called the univariate representation .

𝑓 can also be simply presented in the form where π˜— is a polynomial over the finite field F2𝑛 but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈𝘫≠0.

The Walsh transform

The Walsh transform π‘Šπ‘“ is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)𝑓(π‘₯). With an innner product in 𝔽2𝑛 π‘₯·𝑦, the value of π‘Šπ‘“ at π‘’βˆˆπ”½2𝑛 is the following sum (over the integers)

The set is the Walsh support of 𝑓.

Properties of the Walsh transform

For every 𝑛-variable Boolean function 𝑓 we have the following relations.

  • Inverse Walsh transform: for any element π‘₯ of 𝔽2𝑛 we have
  • Parseval's relation:
  • Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements π‘Ž,𝑏 in 𝔽2𝑛
    for πΈβŸ‚ the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½2𝑛 : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.