On the Numbers of Products in Prefix SOPs for Interval Functions

Infall SYAFALNI; Tsutomu SASAO

doi:10.1587/transinf.E96.D.1086

On the Numbers of Products in Prefix SOPs for Interval Functions

Infall SYAFALNI, Tsutomu SASAO

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.5 pp.1086-1094

Publication Date: 2013/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1086

Type of Manuscript: PAPER

Category: Computer System

Cite this

Copy

Infall SYAFALNI, Tsutomu SASAO, "On the Numbers of Products in Prefix SOPs for Interval Functions" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 5, pp. 1086-1094, May 2013, doi: 10.1587/transinf.E96.D.1086.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1086/_p

Copy

@ARTICLE{e96-d_5_1086,
author={Infall SYAFALNI, Tsutomu SASAO, },
journal={IEICE TRANSACTIONS on Information},
title={On the Numbers of Products in Prefix SOPs for Interval Functions},
year={2013},
volume={E96-D},
number={5},
pages={1086-1094},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.1086},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - On the Numbers of Products in Prefix SOPs for Interval Functions
T2 - IEICE TRANSACTIONS on Information
SP - 1086
EP - 1094
AU - Infall SYAFALNI
AU - Tsutomu SASAO
PY - 2013
DO - 10.1587/transinf.E96.D.1086
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2013
AB - 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.
ER -