Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 21

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
w słowach kluczowych:  Boolean function
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
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.
Content available remote A Note on the Higher-order Nonlinearity of Niho Function
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).
Content available remote On the Multiplicative Complexity of Boolean Functions
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].
Content available remote Higher Order Nonlinearity of Niho Functions
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]
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.
Content available remote A Lower Bound of the Second-order Nonlinearities of Boolean Bent Functions
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 ( /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.
Content available remote Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates
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.
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.
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.
Content available remote Functional Decomposition System Dedicated to Multi-Output Boolean Functions
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.
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.
Content available remote Creating and Application of Maps of Concepts for DL Ontologies
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.
In this paper, we mainly address the problem of loading transaction datasets into main memory and estimating the density of such datasets. We propose BoolLoader, an algorithm dedicated to these tasks; it relies on a compressed representation of all the transactions of the dataset. For sake of efficiency, we have chosen Decision Diagrams as the main data structure to the representation of datasets into memory. We give an experimental evaluation of our algorithm on both dense and sparse datasets. Experiments have shown that BoolLoader is efficient for loading some dense datasets and gives a partial answer about the nature of the dataset before time-consuming pattern extraction tasks. We further investigate the use of Algebraic Decision Diagrams by studying the feasibility of current Data Mining operations, as for instance computing the support of an itemset and even mining frequent itemsets.
Content available remote Dedicated spectral method of Boolean function decomposition
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.
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ą.
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.
Content available remote Zastosowanie funkcji boolowskich w kryptografii
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.
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.
Content available remote www-Based Boolean Function Minimization
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 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.
Content available remote The Spectral Test of the Boolean Function Linearity
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.
Content available remote Efficient Calculation of the Reed-Muller Form by Means of the Walsh Transform
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.
Content available remote On Average Depth of Decision Trees Implementing Boolean Functions
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.
first rewind previous Strona / 2 next fast forward last
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ć.