On the Numbers of Products in Prefix SOPs for Interval Functions
First, this paper derives the prefix sum-of-products expression (PreSOP) and the number of products in a PreSOP for an interval function. Second, it derives Psi(n, tau(p)), the number of n-variable interval functions that can be represented with tau(p) products. Finally, it shows that more than 99.9% of the n-variable interval functions can be represented with [3/2n - 1] products, when n is sufficiently large. These results are useful for a fast PreSOP generator and for estimating the size of ternary content addressable memories (TCAMs) for packet classification.
prefix sum-of-products number of products by presop distribution of interval functions estimating the size of tcam