On the numbers of variables to represent sparse logic functions
Tsutomu Sasao · 2008
In an incompletely specified function f, don’t care values can be chosen to minimize the number of variables to represent f. It is shown that, in incompletely specified functions with k 0’s and k 1’s, the probability that f can be represented with only p = 2[log2(k + 1)] variables is greater than e−1= 0.36788. In the case of multiple-output functions, where only the outputs for k input combinations are specified, most functions can be represented with at most p = 2[log2(k+1)]−1variables. Experimental data is shown to support this. Because of this property, an IP address table can be realized with a small amount of memory.