IEICE TRANSACTIONS on Fundamentals
Head-Tail Expressions for Interval Functions
Summary :
This paper shows a method to represent interval functions by using head-tail expressions. The head-tail expressions represent greater-than GT(X:A) functions, less-than LT(X:B) functions, and interval functions IN0(X:A,B) more efficiently than sum-of-products expressions. Let n be the number of bits to represent the largest value in the interval (A,B). This paper proves that a head-tail expression (HT) represents an interval function with at most n words in a ternary content addressable memory (TCAM) realization. It also shows the average numbers of factors to represent interval functions by HTs for up to n=16, which were obtained by a computer simulation. It also conjectures that, for sufficiently large n, the average number of factors to represent n-variable interval functions by HTs is at most 2/3n-5/9. Experimental results also show that, for n≥10, to represent interval functions, HTs require at least 20% fewer factors than MSOPs, on the average.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.10 pp.2043-2054
- Publication Date
- 2014/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.2043
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
Authors
Infall SYAFALNI
Kyushu Institute of Technology
Tsutomu SASAO
Meiji University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Infall SYAFALNI, Tsutomu SASAO, "Head-Tail Expressions for Interval Functions" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 10, pp. 2043-2054, October 2014, doi: 10.1587/transfun.E97.A.2043.
Abstract: This paper shows a method to represent interval functions by using head-tail expressions. The head-tail expressions represent greater-than GT(X:A) functions, less-than LT(X:B) functions, and interval functions IN0(X:A,B) more efficiently than sum-of-products expressions. Let n be the number of bits to represent the largest value in the interval (A,B). This paper proves that a head-tail expression (HT) represents an interval function with at most n words in a ternary content addressable memory (TCAM) realization. It also shows the average numbers of factors to represent interval functions by HTs for up to n=16, which were obtained by a computer simulation. It also conjectures that, for sufficiently large n, the average number of factors to represent n-variable interval functions by HTs is at most 2/3n-5/9. Experimental results also show that, for n≥10, to represent interval functions, HTs require at least 20% fewer factors than MSOPs, on the average.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.2043/_p
Copy
@ARTICLE{e97-a_10_2043,
author={Infall SYAFALNI, Tsutomu SASAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Head-Tail Expressions for Interval Functions},
year={2014},
volume={E97-A},
number={10},
pages={2043-2054},
abstract={This paper shows a method to represent interval functions by using head-tail expressions. The head-tail expressions represent greater-than GT(X:A) functions, less-than LT(X:B) functions, and interval functions IN0(X:A,B) more efficiently than sum-of-products expressions. Let n be the number of bits to represent the largest value in the interval (A,B). This paper proves that a head-tail expression (HT) represents an interval function with at most n words in a ternary content addressable memory (TCAM) realization. It also shows the average numbers of factors to represent interval functions by HTs for up to n=16, which were obtained by a computer simulation. It also conjectures that, for sufficiently large n, the average number of factors to represent n-variable interval functions by HTs is at most 2/3n-5/9. Experimental results also show that, for n≥10, to represent interval functions, HTs require at least 20% fewer factors than MSOPs, on the average.},
keywords={},
doi={10.1587/transfun.E97.A.2043},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - Head-Tail Expressions for Interval Functions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2043
EP - 2054
AU - Infall SYAFALNI
AU - Tsutomu SASAO
PY - 2014
DO - 10.1587/transfun.E97.A.2043
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2014
AB - This paper shows a method to represent interval functions by using head-tail expressions. The head-tail expressions represent greater-than GT(X:A) functions, less-than LT(X:B) functions, and interval functions IN0(X:A,B) more efficiently than sum-of-products expressions. Let n be the number of bits to represent the largest value in the interval (A,B). This paper proves that a head-tail expression (HT) represents an interval function with at most n words in a ternary content addressable memory (TCAM) realization. It also shows the average numbers of factors to represent interval functions by HTs for up to n=16, which were obtained by a computer simulation. It also conjectures that, for sufficiently large n, the average number of factors to represent n-variable interval functions by HTs is at most 2/3n-5/9. Experimental results also show that, for n≥10, to represent interval functions, HTs require at least 20% fewer factors than MSOPs, on the average.
ER -
English
