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 Ψ(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「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.