Hierarchical Segmentation for Hardware Function Evaluation
Authors:
- Ray C. C. CheungRCRay C. C. Cheung
- Wayne LukWLWayne Luk
- John D. VillasenorJVJohn D. Villasenor
- 25 November 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 17 (1) , 103-116
Abstract
This paper presents a method for evaluating functions based on piecewise polynomial approximations (splines) with a hierarchical segmentation scheme targeting hardware implementation. The methodology provides significant reduction in table size compared to traditional uniform segmentation approaches. The use of hierarchies involving uniform splines and splines with size varying by powers of two is particularly well suited for the coverage of nonlinear regions. The segmentation step is automated and supports user-supplied precision requirements and approximation method. Bit-widths of the coefficients and arithmetic operators are optimized to minimize circuit area and enable a guarantee of 1 unit in the last place (ulp) accuracy at the output. A coefficient transformation technique is also described, which significantly reduces the dynamic ranges of the fixed-point polynomial coefficients. The hierarchical segmentation method is illustrated using a set of functions including -(x/2) log2 x, cos-1(x), radic(-ln(x)) , a high-degree rational function, ln(1+x), and 1/(1+x). Various degree-1 and degree-2 approximation results for precisions between 8 to 24 bits are given. Hardware realizations are demonstrated on a Xilinx Virtex-4 field-programmable gate array (FPGA).Keywords
This publication has 19 references indexed in Scilit:
- Table-based polynomials for fast hardware function evaluation2006
- Programmable numerical function generators: architectures and synthesis method2005
- High-speed function approximation using a minimax quadratic interpolatorIEEE Transactions on Computers, 2005
- Arithmetic on the European logarithmic microprocessorIEEE Transactions on Computers, 2000
- Interleaved memory function interpolators with application to an accurate LNS arithmetic unitIEEE Transactions on Computers, 1994
- CORDIC-based VLSI architectures for digital signal processingIEEE Signal Processing Magazine, 1992
- An interpolating memory unit for function evaluation: analysis and designIEEE Transactions on Computers, 1989
- Uniform piecewise polynomial approximation with variable jointsJournal of Approximation Theory, 1974
- Computational methods for best spline function approximationJournal of Approximation Theory, 1969
- Characteristic properties of the segmented rational minmax approximation problemNumerische Mathematik, 1964