On the Numbers of Products in Prefix SOPs for Interval Functions
Infall Syafalni, Tsutomu Sasao · IEICE Transactions on Information and Systems · 2013
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 Ψ(n,τp), the number of n-variable interval functions that can be represented with τp products. Finally, it shows that more than 99.9% of the n-variable interval functions can be represented with $\lceil \frac{3}{2}n - 1 \rceil$ 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.