Boolean Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
No edit summary
No edit summary
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 09: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 [math]\displaystyle{ f : \mathbb{F}_2^n\rightarrow\mathbb{F} }[/math] is called a Boolean function in dimenstion ๐‘› (or ๐‘›-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 ๐‘ฅ is the size of its support ([math]\displaystyle{ w_H(x)=|supp_x| }[/math]). Similarly the Hamming weight of a Boolean function ๐‘“ 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 ๐‘“,๐‘” 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 ๐‘“.

๐‘ฅ ๐‘“(๐‘ฅ)
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

[math]\displaystyle{ 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]

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

[math]\displaystyle{ 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]

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 [math]\displaystyle{ \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x)) }[/math] 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)

[math]\displaystyle{ W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u}, }[/math]

The set [math]\displaystyle{ \{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \} }[/math] 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
    [math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)}; }[/math]
  • Parseval's relation:
    [math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n}; }[/math]
  • Poisson summation formula: for any vector subspace ๐ธ of ๐”ฝ2๐‘› and for any elements ๐‘Ž,๐‘ in ๐”ฝ2๐‘›
    [math]\displaystyle{ \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]
    for ๐ธโŸ‚ the orthogonal subspace of ๐ธ,{๐‘ขโˆˆ๐”ฝ2๐‘› : ๐‘ขยท๐‘ฅ=0, for all ๐‘ฅโˆˆ๐ธ}.