For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Numbers of Products in Prefix SOPs for Interval Functions
Infall SYAFALNI Tsutomu SASAO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/05/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer System
prefix sum-of-products, number of products by PreSOP, distribution of interval functions, estimating the size of TCAM,
Full Text: PDF>>
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 ⌈ n - 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.