共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Partitioning 1-variable Boolean functions for various classification of n-variable Boolean functions
Ranjeet Kumar Rout Pabitra Pal Choudhury Sudhakar Sahoo Camellia Ray 《国际计算机数学杂志》2015,92(10):2066-2090
This paper addresses all possible equivalence classes of 1-variable Boolean functions and from these classes using recursion and Cartesian product of sets, 15 different ways of classifications of n-variable Boolean functions are obtained. The properties with regard to the size and the number of classes for these 15 different ways are also elaborated. 相似文献
3.
Jawahar Jain Jacob A. Abraham James Bitner Donald S. Fussell 《Formal Methods in System Design》1992,1(1):61-115
We present a novel method for verifying the equivalence of two Boolean functions. Each function is hashed to an integer code by assigning random integer values to the input variables and evaluating an integer-valued transformation of the original function. The hash codes for two equivalent functions are always equal. Thus the equivalence of two functions can be verified with a very low probability of error, which arises from unlikely collisions between inequivalent functions. An upper bound, , on the probability of error is known a priori. The bound can be decreased exponentially by making multiple runs. Results indicate significant time and space advantages for this method over techniques that represent each function as a single OBDD. Some functions known to require space (and time) exponential in the number of input variables for these techniques require only polynomial resources using our method. Experimental results indicate that probabilistic verification can provide an attractive alternative for verifying functions too large to be handled using these OBDD-based techniques. 相似文献
4.
Ondřej Čepek David Kronus Petr Kučera 《Annals of Mathematics and Artificial Intelligence》2008,52(1):1-24
Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional
value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function
and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard.
In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a
Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time,
we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their
variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined
Boolean functions. We also study some other properties of interval functions.
相似文献
5.
6.
7.
8.
9.
10.
Addresses the problem of estimating the parameters of stochastic linear systems when the measurements of the system input as well as the system output are noise contaminated. It is assumed that the input is non-Gaussian and the noises are Gaussian. The square root of the magnitude of the fourth cumulant of a generalized error signal is proposed as a performance criterion for parameter estimation. An optimization algorithm is presented. Strong consistency of the proposed parameter estimators is proved under certain sufficient conditions. Both single-input single-output and multiple-input multiple-output cases are investigated. Finally, simulation results are presented to illustrate the proposed approach 相似文献
11.
State estimation problems for linear time-invariant systems with noisy inputs and outputs are considered. An efficient recursive algorithm for the smoothing problem is presented. The equivalence between the optimal filter and an appropriately modified Kalman filter is established. The optimal estimate of the input signal is derived from the optimal state estimate. The result shows that the noisy input/output filtering problem is not fundamentally different from the classical Kalman filtering problem. 相似文献
12.
William F. McColl 《Acta Informatica》1978,11(1):71-77
Summary Circuit size and depth are two important complexity measures for a Boolean function. Uniform hierarchies are shown to exist with respect to each of these measures. 相似文献
13.
Wolfgang J. Paul 《Theoretical computer science》1976,2(3):383-396
For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f:{0,1}n→{0,1}n such that C(f×f)? (1+ε)C(f) and arbitrarily complex functions f:{0,1}n→{0,1} such that C(v°(fxf)? (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size. 相似文献
14.
Suresh C. Gupta 《Computers & Electrical Engineering》1981,8(4):267-276
A method is proposed to determine various symmetries of a completely or incompletly specified Boolean function. Equivalence, nonequivalence and single-variable symmetries are detected from their respective symmetry tables. A symmetry table of n variables can be used to detect symmetries of functions of n, or less, variables. A procedure is given for obtaining total or partial symmetries, with all primed (or all unprimed), mixed or multiform variables of symmetry, from equivalence and nonequivalence symmetries of the function. 相似文献
15.
Wei Xing Zheng 《International journal of systems science》2013,44(3):185-190
This paper addresses the problem of parameter estimation of stochastic liner systems with noisy input–output measurements. A new and simple estimation scheme for the variances of the white input and output measurement noises is presented, which is only based on expanding the denominator polynomial of the system transfer function and makes no use of the average least-squares errors. The attractive feature of the iterative least-square based parametric algorithm thus developed is its improved convergence property. The effectiveness of the developed identification algorithm is demonstrated through numerical illustrations. 相似文献
16.
《国际计算机数学杂志》2012,89(4):415-420
Boolean functions are widely used because they can be used to precisely describe logical circuits. Properties of Boolean functions with respect to their applications to cryptography have been studied, but relationship between Boolean functions are rarely studied. This paper studies the independence of Boolean functions, gives necessary and sufficient conditions for judging whether two given Boolean functions are independent. Some enumeration formulae are given. 相似文献
17.
Suresh C. Gupta 《Computers & Electrical Engineering》1981,8(1):41-48
All the decompositions of a Boolean function of four variables can be determined directly from its prime implicants if it is decomposable with one free variable. Decompositions of functions of three variables can be obtained from the column ratio of the variables. 相似文献
18.
19.
《国际计算机数学杂志》2012,89(10):2035-2041
The relationship among cross-correlation of arbitrary four Boolean functions is presented. Several known cross-correlation properties of Boolean functions are generalized. Based on them, a lower bound for the maximal cross-correlation (in absolute value) of two Boolean functions (if one of the functions is bent) is obtained. 相似文献
20.
Analysis of affinely equivalent Boolean functions 总被引:1,自引:0,他引:1
By some basic transforms and invariant theory, we give two results: 1) an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2) Reed-Muller codes R(4,6)/R(1,6), R(3,7)/R(1,7) are classified efficiently. 相似文献