On the Numbers of Products in Prefix SOPs for Interval Functions

Infall SYAFALNI  Tsutomu SASAO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.5   pp.1086-1094
Publication Date: 2013/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1086
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
prefix sum-of-products,  number of products by PreSOP,  distribution of interval functions,  estimating the size of TCAM,  

Full Text: PDF>>
Buy this Article




Summary: 
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.