Difference between revisions of "Boolean Functions"

From Boolean Functions
Jump to: navigation, search
(Created page with "=Introduction= Let <math>\mathbb{F}_2^n</math> be the vector space of dimension <i>n</i> over the finite field with two elements. The vector space can also be endowed with th...")
 
(Algebraic normal form)
Line 51: Line 51:
 
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 <i>f</i> (shortly ANF).
  
The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0 f=\max \{ |I| : a_I\ne0 \}.
+
The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>.
  
 
==Trace representation==
 
==Trace representation==
 
In this case we identify the vector space with the finite field.
 
In this case we identify the vector space with the finite field.

Revision as of 15:58, 23 September 2019

Introduction

Let 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 . A function is called a Boolean function in dimenstion n (or n-variable Boolean function).

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

Trace representation

In this case we identify the vector space with the finite field.