Department of Electronic Engineering
Division of Electronics Systems
APPROXIMATION OF ELEMENTARY FUNCTIONS IN HARDWARE
Recommended for: Graduate students in computer science and electrical engineering.
Goals: Provide in-depth knowledge in computer arithmetic algorithms for realization of elementary function approximation in hardware. The course will focus on different ways of replacing look-up tables to efficiently compute values of elementary functions such as sin, cos, log, reciprocals etc. The scope will be fixed-point functions with reasonable wordlengths suitable for direct digital frequency synthesis, filtering in logarithmic number systems, Givens rotations, and seed values for Newton-Raphson division/square rooting among others. Floating-point issues will be mentioned briefly.
Prerequisites: Computer Arithmetic Algorithms or corresponding knowledge.
Organization: Self study with seminars following each subject.
|Group 1||Group 2
|14/1||10-12||16/1||10-12||Nollstället||Sum of bit-products||Kenny
|Nollstället||Approximation in floating-point number systems and
on processors||Di & Johan
Groups and numbers
- M. Daumas, C. Mazenc, X. Merrheim and J.M. Muller, Modular Range
Reduction: a New Algorithm for Fast and Accurate Computation of the
Elementary Functions, Journal of Universal Computer Science, Vol. 1 No
3, pages 162-175, March 1995. PDF
- N. Brisebarre, D. Defour, P. Kornerup, J.M. Muller and N. Revol, A
New Range-Reduction Algorithm, IEEE Transactions on Computers,
Vol. 54 no 3, pages 331-339, march 2005.
- Dong-U Lee; Gaffar, A.A.; Mencer, O.; Luk, W., "Adaptive range
reduction for hardware function evaluation," Field-Programmable
Technology, 2004. Proceedings. 2004 IEEE International Conference on ,
vol., no., pp. 169-176, 6-8 Dec. 2004.
- V. Lefevre and J.M. Muller, On-the-fly Range Reduction, Journal of VLSI Signal Processing 33, pages 31-35, Jan 2003.
- Milos Ercegovac, Tomas Lang, Jean-Michel Muller and Arnaud Tisserand, Reciprocation, Square root, Inverse Square Root,
and some Elementary Functions using Small Multipliers , IEEE Transactions on Computers, Vol. 49, No. 7, July 2000.
- A. Tisserand. High-Performance Hardware Operators for Polynomial
Evaluation. In Int. J. High Performance Systems Architecture, 2007.
- N. Brisebarre, J.-M. Muller and A. Tisserand, Computing
machine-efficient polynomial approximation, ACM Transactions on
Mathematical Software, Vol. 32 No 2, june 2006.
- W. Fraser, "A survey of methods for computing minimax and nearminimax
polynomial approximations for functions of a single independent
variable," J. ACM, vol. 12, no. 3, pp. 295-314, July 1965.
- A.S. Noetzel, "An Interpolating Memory Unit for Function
Evaluation: Analysis and Design," IEEE Trans. Computers, vol. 38,
no. 3, pp. 377-384, Mar. 1989.
- N. Takagi. Powering by a table look-up and a multiplication with operand modification. IEEE
Transactions on Computers, 47(11):1216-1222, November 1998.
- O. Gustafsson and K. Johansson, "Multiplierless piecewise linear approximation of elementary functions," in Proc. Asilomar Conf. Signals, Syst., Comp., Pacific Grove, CA, Oct. 29Nov. 1, 2006, pp. 1678-1681.
- J.A. Pineiro, S.F. Oberman, J.-M. Muller and J.D. Bruguera, High-Speed Function Approximation using a Minimax Quadratic Interpolator, IEEE Transactions on Computers, Vol. 54 no 3, pages 304-318, March 2005.
Bi- and multipartite tables
- Section 4.4.4. "Bipartite and multipartite methods" from Jean-Michel Muller, Elementary Functions: Algorithms and
Implementation, 2nd edition, Birkhäuser Boston, 2005.
- D. DasSarma and D.W. Matula, "Faithful Bipartite ROM Reciprocal
Tables," Proc. 12th Symp. Computer Arithmetic, pp. 17-28, July
- J. E. Stine and M. J. Schulte, "The symmetric table addition method for accurate function approximation," J. VLSI Signal Processing, vol. 21, pp. 167-177, 1999.
- F. de Dinechin and A. Tisserand. Multipartite Table Methods. IEEE Transactions on Computers, 54(3):319-330, March 2005.
Sum of bit-products
- D. M. Mandelbaum and S. G. Mandelbaum, " A fast, efficient
parallel-acting method of generating functionsdefined by power series,
including logarithm, exponential, and sine, cosine," IEEE
Trans. Parallel and Dist. Systems, vol. 7, no. 1, pp. 33-45, Jan. 1996.
- E.M. Schwarz and M. J. Flynn, "Hardware Starting Approximation
Method and Its Application to the Square Root Operation," IEEE
Trans. on Comp., vol. 45, no. 12, Dec. 1996.
- D. De Caro, E. Nappli, and A.G.M. Strollo, "Direct Digital
Frequency Synthesizers with Polynomial Hyperfolding
Technique,", IEEE Trans. Circuit & Syst. Part-II, Vol.51,
pp 337-344, July 2004.
- K. Johansson, O. Gustafsson, and L. Wanhammar, "Approximation of elementary functions using a weighted sum of bit-products," IEEE Int. Symp. Circuits Syst., Kos Island, Greece, May 21-24, 2006.
- R. Andraka, "A survey of CORDIC algorithms for FPGAs,"
Proceedings of the 1998 ACM/SIGDA sixth international symposium on
Field programmable gate arrays, Feb. 22-24, 1998, Monterey,
CA. pp. 191-200.
- Y. Hu, "CORDIC-based VLSI architectures for digital signal
pprocessing," IEEE Signal processing Magazine, vol. 9, no. 3,
pp. 16-35, July 1992.
- E Antelo, J Villalba, JD Bruguera, EL Zapata, "High performance
rotation architectures based on the radix-4 CORDIC algorithm," IEEE
Transactions on Computers, 1997.
- K. Kota and J. R. Cavallaro, "Numerical accuracy and hardware
tradeoffs for CORDIC arithmetic for special-purpose processors," IEEE
Transactions on Computers, 1993
Approximation in floating-point number systems and
- I. Koren , O. Zinaty, Evaluating Elementary Functions in a
Numerical Coprocessor Based on Rational Approximations, IEEE
Transactions on Computers, v.39 n.8, p.1030-1037, August 1990
- R. C. C. Cheung et al, "Automating custom-precision function
evaluation for embedded processors," Proc. Int. Conf. on Compilers,
Architectures and Synthesis for Embedded Systems, San Francisco, CA,
2005, pp. 22-31.
- Jean-Michel Muller, Generating functions at compile-time (invited
talk), 40th Asilomar Conference on signals, systems and computers,
Pacific Grove, California, Nov. 2006.
- Lynch, T.; Ahmed, A.; Schulte, M.; Callaway, T.; Tisdale, R, "The
K5 transcendental functions," Proceedings of the 12th Symposium on
19-21 July 1995 Page(s):163 - 170
- Jean-Michel Muller, Elementary Functions: Algorithms and
Implementation, 2nd edition, Birkhäuser Boston, 2005.
- J.M.P. Langlois and D. Al-Khalili, "Phase to Sinusoid Amplitude
Conversion Techniques for Direct Digital Frequency Synthesis," IEE
Proceedings on Circuits, Devices and Systems.
- N. H. F. Beebe, "A bibliography of publications about the
computation of elementary functions in computer programming languagues"
: Oscar Gustafsson
: Active participation in seminars where each
student is responsible for one paper. Written summary
of methods covered in one seminar and implementation of VHDL-generator for the
: 6 HP (+3 HP for optional research