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.
Head-Tail Expressions for Interval Functions
Infall SYAFALNI Tsutomu SASAO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/10/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
prefix sum-of-products, head-tail expressions, TCAM,
Full Text: PDF>>
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.