Design method for numerical function generators using recursive segmentation and EVBDDs
Authors
Nagayama, Shinobu
Sasao, Tsutomu
Butler, Jon T.
Subjects
edge-valued binary decision diagrams (EVBDDs)
recursive segmentation
piecewise polynomial approximation
numerical function generators (NFGs)
programmable architecture
recursive segmentation
piecewise polynomial approximation
numerical function generators (NFGs)
programmable architecture
Advisors
Date of Issue
2007-12
Date
2007-12
Publisher
Language
Abstract
Numerical function generators (NPGs) realize arithmetic functions, such as ex, sin p(piex), and the square root of x, in hardware. They are used in applications where high-speed is essential, such as 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 fuction 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 reduceing delay. We compare our results to NFGs designed and 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.
Type
Article
Description
IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E90-A, No.12, Dec. 2007, pp.2752-2761.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.
Series/Report No
Department
Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
This research is partly supported by the Grant in Aid for Scientific Research of the Japan Society for the Promotion of Science (JSPS), funds from Ministry of Education, Culture, Sports, Science, and Technology (MEXT) via Kitakyushu innovative cluster project, a contract with the National Security Agency, the MEXT Grant-in-Aid for Young Scientists (B), 18700048, 2007 and Hiroshima City University Grant for Special Academic Research (General Studies), 6101, 2007.
Funder
Format
Citation
S. Nagayama, T. Sasao, and J. T. Butler, "Design method for numerical function generators using recursive segmentation and EVBDDs," IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E90-A, No.12, Dec. 2007, pp.2752-2761.