On the numbers of variables to represent sparse logic functions

ABSTRACT

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[log₂(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[log₂(k+1)] -1 variables. Experimental data is shown to support this. Because of this property, an IP address table can be realized with a small amount of memory.

REFERENCES

• 1: F. M. Brown, Boolean Reasoning: The logic of Boolean Equations, Kluwer Academic Publishers, Boston, 1990.
• 2: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 3: Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
• 4: M. Fujita and Y. Matsunaga, "Multi-level logic minimization based on minimal support and its application to the minimization of look-up table type FPGAs," ICCAD-91, pp. 560--563, 1991.
• 5: C. Halatsis , N. Gaitanis, Irredundant Normal Forms and Minimal Dependence Sets of a Boolean Function, IEEE Transactions on Computers, v.27 n.11, p.1064-1068, November 1978 [doi>10.1109/TC.1978.1674997]
• 6: Y. Kambayashi, Logic Design of Programmable Logic Arrays, IEEE Transactions on Computers, v.28 n.9, p.609-617, September 1979 [doi>10.1109/TC.1979.1675428]
• 7: Tsutomu Sasao, On the Number of Dependent Variables for Incompletely Specified Multiple-Valued Functions, Proceedings of the 30th IEEE International Symposium on Multiple-Valued Logic, p.91, May 23-25, 2000
• 8: Tsutomu Sasao, Design Methods for Multiple-Valued Input Address Generators, Proceedings of the 36th International Symposium on Multiple-Valued Logic, p.1, May 17-20, 2006 [doi>10.1109/ISMVL.2006.17]
• 9: T. Sasao, "A Design method of address generators using hash memories," IWLS-2006, pp. 102--109, Vail, Colorado, U.S.A, June 7--9, 2006.
• 10: Tsutomu , Munehiro Matsuura, An Implementation of an Address Generator Using Hash Memories, Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, p.69-76, August 29-31, 2007 [doi>10.1109/DSD.2007.29]
• 11: David E. Taylor, Survey and taxonomy of packet classification techniques, ACM Computing Surveys (CSUR), v.37 n.3, p.238-275, September 2005 [doi>10.1145/1108956.1108958]
• 12: Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high speed IP routing lookups, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.25-36, Oct. 1997
• 13: S. Yang, "Logic synthesis and optimization benchmark user guide, Version 3.0," MCNC, Jan. 1991.