
For FullText 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.

HeadTail Expressions for Interval Functions
Infall SYAFALNI Tsutomu SASAO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.10
pp.20432054 Publication Date: 2014/10/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.2043
Type of Manuscript: PAPER Category: VLSI Design Technology and CAD Keyword: prefix sumofproducts, headtail expressions, TCAM,
Full Text: PDF>>
Summary:
This paper shows a method to represent interval functions by using headtail expressions. The headtail expressions represent greaterthan GT(X:A) functions, lessthan LT(X:B) functions, and interval functions IN_{0}(X:A,B) more efficiently than sumofproducts expressions. Let n be the number of bits to represent the largest value in the interval (A,B). This paper proves that a headtail 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 nvariable interval functions by HTs is at most 2/3n5/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.

