|
|
Library for Boolean Functions in Algebraic Normal Form
Vasilišin, Maroš ; Mrázek, Vojtěch (referee) ; Dobai, Roland (advisor)
This bachelor thesis focuses on design and implementation of library in C language for manipulation od Boolean functions in Algebraic Normal Form. Majority of existing libraries for representation of Boolean functions is based on binary decision diagrams. Algebraic Normal Form presents several advantages over binary decision diagrams, for example Boolean value of function can be determined in linear time. Implemented library uses simple structures to effectively represent Boolean function in program. After experiments we determined that representation in Algebraic Normal Form has its applications, and in some cases it provides better results than representation in binary decision diagrams.
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Title: A construction of minimum DNF representations of 2-interval functions Author: Jakub Dubovský Department: Dep. of Theoretical Computer Science and Mathematical Logic Supervisor: doc.RNDr.Ondřej Čepek, Ph.D. Abstract: The thesis is devoted to interval boolean functions. It is focused on construction of their representation by disjunctive normal forms with minimum number of terms. Summary of known results in this field for 1-interval functions is presented. It shows that method used to prove those results cannot be in general used for two or more interval functions. It tries to extend those results to 2-interval functions. An optimization algorithm for special subclass of them is constructed. Exact error estimation for approximation algorithm is proven. A command line software for experimentation with interval function is part of the thesis. Keywords: boolean function, interval function, representation construction, ap- proximation 1
|
|
|
Generalized integral property
Hrúzová, Jana ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis is based on an article C. Boura and A. Canteaut, Another View of the Division Property, which is focused on division property of sets from Fn 2 . In this thesis we introduce important definitions and propositions about boolean function, polynomials and Reed-Muller codes at the beginning. Then we define parity set of a set from Fn 2 , which helps us to simplify the division property. We also show how sets, which satisfy division property of certain order, look like. From that we could follow how the division property propagate through the substitution-permutation network. 1
|
|
|
APN functions with non-classical Walsh spectra
Maršálek, Michal ; Göloglu, Faruk (advisor) ; Drápal, Aleš (referee)
An interesting class of Boolean functions are APN functions - these func- tions are "as far" from linear functions as possible. Most of the quadratic APN functions have the same (=classical) Walsh spectrum - a sort of footprint of the function. The aim of this thesis is to describe a method which might lead to a generalisation of a sporadic example of a quadratic APN function with non-classical Walsh spectrum. Up until recently, it was believed that no such function exists. This was proven to be false in 2009, as an example of such func- tion in dimension 6 was introduced. In this thesis, we describe the construction and then deduce necessary conditions for some free coefficients in order to reduce the search space to a level which enables a computer search. 1
|
|
|
Library for Boolean Functions in Algebraic Normal Form
Vasilišin, Maroš ; Mrázek, Vojtěch (referee) ; Dobai, Roland (advisor)
This bachelor thesis focuses on design and implementation of library in C language for manipulation od Boolean functions in Algebraic Normal Form. Majority of existing libraries for representation of Boolean functions is based on binary decision diagrams. Algebraic Normal Form presents several advantages over binary decision diagrams, for example Boolean value of function can be determined in linear time. Implemented library uses simple structures to effectively represent Boolean function in program. After experiments we determined that representation in Algebraic Normal Form has its applications, and in some cases it provides better results than representation in binary decision diagrams.
|
|
|
Cryptographic criteria for Boolean functions
Luňáčková, Radka ; Hojsík, Michal (advisor) ; Tůma, Jiří (referee)
The work is focused on Boolean functions. At first, it describes the ways Boolean functions are represented. Besides the representation using truth- table, vector of values and algebraic normal form which are usually shown we also show some other representations like univariate representation and trace repre- sentation. Moreover, we explain the relations among these representations. Then summary of the theory of Boolean functions is given, in order to understand important properties of Boolean functions corectly. Finally, these properties are studied, their interconnection is explained and the following cryptographic cri- teria of Boolean functions are describe: the algebraic degree, the nonlinearity, balancedness, resiliency and correlation immunity. 1
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Title: A construction of minimum DNF representations of 2-interval functions Author: Jakub Dubovský Department: Dep. of Theoretical Computer Science and Mathematical Logic Supervisor: doc.RNDr.Ondřej Čepek, Ph.D. Abstract: The thesis is devoted to interval boolean functions. It is focused on construction of their representation by disjunctive normal forms with minimum number of terms. Summary of known results in this field for 1-interval functions is presented. It shows that method used to prove those results cannot be in general used for two or more interval functions. It tries to extend those results to 2-interval functions. An optimization algorithm for special subclass of them is constructed. Exact error estimation for approximation algorithm is proven. A command line software for experimentation with interval function is part of the thesis. Keywords: boolean function, interval function, representation construction, ap- proximation 1
|
|
| |
guest ::
