Head-Tail Expressions for Interval Functions

Infall SYAFALNI  Tsutomu SASAO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.10   pp.2043-2054
Publication Date: 2014/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.2043
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
Keyword: 
prefix sum-of-products,  head-tail expressions,  TCAM,  

Full Text: PDF>>
Buy this Article




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.