Ograniczanie wyników
Czasopisma
Autorzy
Lata
Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 21

Liczba wyników na stronie
Strona / 2
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  Boolean function
Sortuj według:

Ogranicz wyniki do:
Strona / 2
EN
In this paper, a class of linear Boolean functions is analyzed. The Boolean function can be represented as disjoint cubes or in the form of a truth vector. The primary purpose of this analysis is to decide whether an incompletely defined function can be extended to a complete linear form. A simple algorithm for generating all states of this function has been proposed if the Boolean function can have a full representation. The algorithm is beneficial for large functions. The proposed approach can be applied to completely and incompletely defined Boolean functions.
2
A Note on the Higher-order Nonlinearity of Niho Function
EN
Sun and Wu investigated the lower bound of higher-order nonlinearity of the niho Boolean function f(x)=Trn1n(λxd) over F*2ⁿ; where λ∈F*2ⁿ,[formula] when n ≡ 3 mod 4 in second case of Theorem 3.6 of the paper titled higher-order nonlinearity of niho functions published in Fundamenta Informaticae 137 (2015) 403–412. Unfortunately, the proof of finding the lower bound of higher-order nonlinearities of the niho Boolean function f(x) is not correct in the above mentioned paper. In this paper the author gives the correct proof of lower bound of higher-order nonlinearities of the niho Boolean function f(x).
3
On the Multiplicative Complexity of Boolean Functions
EN
The multiplicative complexity µ(f) of a Boolean function f is the smallest number of & (of AND gates) in circuits in the basis {x&y, x⊕y, 1} such that each circuit implements the function f. By µ(S) we denote the number of & (of AND gates) in a circuit S in the basis {x&y, x ⊕ y, 1}. We present a method to construct circuits in the basis {x&y, x ⊕ y, 1} for Boolean functions. By this method, for an arbitrary function f(x1, ..., xn), we can construct a circuit Sf implementing the function f such that µ(Sf) ≤ (3/2 + o(1)) · 2n/2, if n is even, and µ(Sf) ≤ (v2 + o(1))2n/2, if n is odd. These evaluations improve estimations from [1].
4
Higher Order Nonlinearity of Niho Functions
EN
The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. In this paper we investigate the lower bound of the higher-order nonlinearity of Niho Boolean functions f(x) = tr(λxd) over F2n, where... [formula]
EN
Present work considers the neural elements (NE) with generalized threshold activation function and represents iterative method of their synthesis. Algorithm of vectors finding for structures of the neural elements with generalized threshold activation function was developed, and the sufficient condition of Boolean function unreliazability on such neural elements was discovered.
6
A Lower Bound of the Second-order Nonlinearities of Boolean Bent Functions
EN
In this paper we find a lower bound of the second-order nonlinearities of Boolean bent functions of the form f(x) = [formula], where d1 and d2 are Niho exponents. A lower bound of the second-order nonlinearities of these Boolean functions can also be obtained by using a recent result of Li, Hu and Gao (eprint.iacr.org/2010 /009.pdf). It is shown in Section 3, by a direct computation, that for large values of n, the lower bound obtained in this paper are better than the lower bound obtained by Li, Hu and Gao.
7
Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates
EN
We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε(ε∈(0,1/2). We describe a set Mk (k≥3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε→0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0.
EN
In this paper a creation of new numerical set-theoretical constructions of Boolean functions with their properties has been presented. The parted conjuncterms and decomposition clones which can be used for realization of different optimization logic synthesis of digital devices and systems have been proposed. Set theoretical operations and procedures with these constructions have been considered. Examples which illustrate simplicity of their practical realization have been presented. Moreover, the paper includes the comparison of new results obtained on the basis of the proposed approach with the results obtained by means of commercial software Quartus II of Altera.
9
EN
In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight WBDD(n) and the size LBDD(n, t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we are able to prove tight upper and lower asymptotic bounds: [formula] which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds.
10
Functional Decomposition System Dedicated to Multi-Output Boolean Functions
EN
The functional decomposition has important applications in many fields of modern engineering and science (FPGA synthesis, information systems, neural networks and many others). In this paper, a new method for functional decomposition is presented. The proposed approach is dedicated to the multi-output boolean functions. It uses the concept of dividing the complex function into single-output functions and utilizing common information between these functions. Additionally, it allows the multi-output function to be represented as a set of separate truth tables for each output, which might be very beneficial for time and memory usage of the system. To test the proposed solutions, a prototype tool was implemented and the results are presented in the paper.
EN
In this paper, nonlinear multi parameter binary difference equation system (MPBDS) and optimal piecewise process are analyzed. Since such difference equation system is over-determined, a theorem similar to Frobenius's theorem is proved on Galois field. An illustrative example, which can be solved by applying terminal control problem is given. Then, terminal control problem is examined and it is shown that the principle of optimality is satisfied.
12
Creating and Application of Maps of Concepts for DL Ontologies
EN
n previous work a novel knowledge representation, called Knowledge Cartography, was introduced. The method allows for description, in the form of a map of concepts, of interrelationships among concepts distinguished in a terminology and for gradual (with growth of our knowledge) assignment of individual objects to those concepts. Effectiveness of the process of building map of concepts is a key factor influencing usability of the method. This paper presents a new map creating algorithm called TreeFusion that uses binary decision diagrams originally developed for supporting VLSI circuits design. The paper presents also some current applications of Knowledge Cartography.
EN
14
Dedicated spectral method of Boolean function decomposition
EN
Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform and autocorrelation characteristics.
PL
W artykule przedstawiono porównanie metody zmodyfikowanych drzew logicznych funkcji boolowskich i jednoczynnikowej analizy wariancji do klasyfikacji parametrów układu maszynowego. Do ilustracji zagadnienia wykorzystano pompę wirowo-śmigłową.
EN
In this elaboration comparison of method of modified logical trees of Boolean functions and one-factor analysis of variance for classification of parameter of engine match has been presented. It take advantage while-flow pump for illustration of question.
16
Zastosowanie funkcji boolowskich w kryptografii
PL
Artykuł przedstawia zastosowanie funkcji boolowskich w kryptografii, a w szczególności w szyfrach strumieniowych. Przedstawione są w nim podstawowe informacje jak i najważniejsze z punktu widzenia kryptologii własności tych funkcji. W pracy podane są twierdzenia pozwalające na efektywne wyznaczanie parametrów kryptograficznych. Artykuł zawiera także opisy dwóch ataków na szyfry strumieniowe: ataku korelacyjnego wykorzystującego niską odporność korelacyjną zastosowanej w szyfrze funkcji boolowskiej i ataku opierającego się na niskiej nieliniowości tej funkcji.
EN
In this paper, we present applications of the boolean functions in cryptography, particullary in the stream ciphers. The paper provides basic informations about boolean functions and also the most important cryptologic properties of these functions. We present theorems useful for efective counting the cryptographic parameters of the boolean functions. The article contains descriptions of two cryptoanalitic attacks on the stream ciphers: a correlation attack based on a low correlation immunity of used the boolean function and an attack based on low nonlinearity of the function.
17
www-Based Boolean Function Minimization
EN
In this paper a Boolean minimization algorithm is considered and implemented as an applet in Java. The application is based on the Quine-McCluskey simplification technique with some modifications. The given application can be accessed on line since it is posted on the World Wide Web (WWW), with up to four variables, at the URL http://www.csam.montclair.edu/~antoniou/bs. After extensive testing, the performance of the algorithm has been found to be excellent. The proposed application is a useful aid for students and professors in the fields of electrical and computer engineering and computer science as well as a valuable tool for digital designers.
18
The Spectral Test of the Boolean Function Linearity
EN
The paper discusses the problem of recognizing the Boolean function linearity. A spectral method of the analysis of Boolean functions using the Walsh transform is described. Linearity and nonlinearity play important roles in the design of digital circuits. The analysis of the distribution of spectral coefficients allows us to determine various combinatorial properties of Boolean functions, such as redundancy, monotonicity, self-duality, correcting capability, etc., which seems more difficult be performed by means of other methods. In particular, the basic synthesis method described in the paper allows us to compute the spectral coefficients in an iterative manner. The method can be easily used in investigations of large Boolean functions (of many variables), which seems very attractive for modern digital technologies. Experimental results demonstrate the efficiency of the approach.
19
Efficient Calculation of the Reed-Muller Form by Means of the Walsh Transform
EN
The paper describes a spectral method for combinational logic synthesis using the Walsh transform and the Reed-Muller form. A new algorithm is presented that allows us to obtain the mixed polarity Reed-Muller expansion of Boolean functions. The most popular minimisation (sub-minimisation) criterion of the Reed-Muller form is obtained by the exhaustive search of all the polarity vectors. This paper presents a non-exhaustive method for Reed-Muller expansions. The new method allows us to build the Reed-Muller form based on the analysis of Walsh-Hadamard coefficients. The presented method has much less complexity than the procedures which have been applied until now. Both the transforms and the presented Walsh-Hadamard spectral characterization of the Reed-Muller expansion are compared. An analysis of the properties of the spectra obtained from these transforms is made.
20
On Average Depth of Decision Trees Implementing Boolean Functions
EN
The article considers the representation of Boolean functions in the form of decision trees. It presents the bounds on average time complexity of decision trees for all classes of Boolean functions that are closed over substitution, and the insertion and deletion of unessential variables (the structure of these classes is described in the book by Jablonsky, Gavrilov and Kudriavtzev [5]). The obtained results are compared with the results developed by Moshkov in [6] that describe the worst case time complexity of decision trees.
Strona / 2
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.