Design Method for Numerical Function Generators Using Recursive Segmentation and EVBDDs

Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER

Summary :

Numerical function generators (NFGs) realize arithmetic functions, such as e^x,sin(πx), and , in hardware. They are used in applications where high-speed is essential, such as in digital signal or graphics applications. We introduce the edge-valued binary decision diagram (EVBDD) as a means of reducing the delay and memory requirements in NFGs. We also introduce a recursive segmentation algorithm, which divides the domain of the function to be realized into segments, where the given function is realized as a polynomial. This design reduces the size of the multiplier needed and thus reduces delay. It is also shown that an adder can be replaced by a set of 2-input AND gates, further reducing delay. We compare our results to NFGs designed with multi-terminal BDDs (MTBDDs). We show that EVBDDs yield a design that has, on the average, only 39% of the memory and 58% of the delay of NFGs designed using MTBDDs.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.12 pp.2752-2761
• Publication Date: 2007/12/01
• Online ISSN: 1745-1337
• DOI: 10.1093/ietfec/e90-a.12.2752
• Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
• Category: Logic Synthesis and Verification

Authors

Shinobu NAGAYAMA
Tsutomu SASAO
Jon T. BUTLER

Keyword

edge-valued binary decision diagrams (EVBDDs),  recursive segmentation,  piecewise polynomial approximation,  numerical function generators (NFGs),  programmable architecture