Boolean Functions

From Boolean
Revision as of 14:27, 26 September 2019 by Ivi062 (talk | contribs)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

[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 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].

Trace representation

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

[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 Γn set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2n-1), o(j) size of the cyclotomic coset containing j, Aj ∈ 𝔽2o(j), Tr𝔽2o(j)/𝔽2 trace function from 𝔽2o(j) to 𝔽2.


Such representation is also called the univariate representation .

f can also be simply presented in the form [math]\displaystyle{ \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x)) }[/math] where P is a polynomial over the finite field F2n but such representation is not unique, unless o(j)=n for every j such that Aj≠0.