# Difference between revisions of "Boolean Functions"

Line 75: | Line 75: | ||

* Parseval's relation: <center><math>\sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n};</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 π₯βπΈ}. | * 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 π₯βπΈ}. | ||

+ | |||

+ | =Equivalence of Boolean functions= | ||

+ | Two π-variable Boolean functions π,π are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism πΏ, an affine Boolean function π and a vecor π such that π(π₯) = π(πΏ(π₯)+π)+π(π₯). | ||

+ | A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>. |

## Revision as of 10:29, 27 September 2019

## Contents

# 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 F_{2π} 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 π₯βπΈ}.

# Equivalence of Boolean functions

Two π-variable Boolean functions π,π are called *extended-affine equivalent* (shortly EA-equivalent) if there exists a linear automorphism πΏ, an affine Boolean function π and a vecor π such that π(π₯) = π(πΏ(π₯)+π)+π(π₯).
A parameter that is preserved by EA-equivalence is called *EA-invariant*.