Linköping University , Department of Electronic Engineering , Division of Electronics Systems , Courses , PhD Courses .

---

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.
Literature: Papers.

Introduction Lecture

Date	Time	Room
2007-11-20	13-15	Nollstället

Seminars

Group 1		Group 2
Date	Time	Date	Time	Room	Subject	Student	Report	Generator
28/11	10-12	3/12	10-12	Nollstället	Range reduction	Rizwan
5/12	10-12	7/12	13-15	Nollstället	Polynomial approximation	Anton
12/12	10-12	17/12	10-12	Nollstället	Piecewise approximation	Amin
20/12	10-12	20/12	13-15	Nollstället	Multipartite tables	Ali
14/1	10-12	16/1	10-12	Nollstället	Sum of bit-products	Kenny
25/1	13-15	24/1	15-17	Nollstället	CORDIC	Amir
				Nollstället	Approximation in floating-point number systems and on processors	Di & Johan

Groups and numbers

Group 1

1. Rizwan
2. Amin
3. Di
4. Ali

Group 2

1. Johan
2. Kenny
3. Anton
4. Amir

Selected papers

Range reduction

1. 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
2. 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.
3. 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.
4. V. Lefevre and J.M. Muller, On-the-fly Range Reduction, Journal of VLSI Signal Processing 33, pages 31-35, Jan 2003.

Polynomial approximation

1. 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.
2. A. Tisserand. High-Performance Hardware Operators for Polynomial Evaluation. In Int. J. High Performance Systems Architecture, 2007.
3. N. Brisebarre, J.-M. Muller and A. Tisserand, Computing machine-efficient polynomial approximation, ACM Transactions on Mathematical Software, Vol. 32 No 2, june 2006.
4. 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.

Piecewise approximation

1. 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.
2. N. Takagi. Powering by a table look-up and a multiplication with operand modification. IEEE Transactions on Computers, 47(11):1216-1222, November 1998.
3. O. Gustafsson and K. Johansson, "Multiplierless piecewise linear approximation of elementary functions," in Proc. Asilomar Conf. Signals, Syst., Comp., Pacific Grove, CA, Oct. 29­Nov. 1, 2006, pp. 1678-1681.
4. 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

1. Section 4.4.4. "Bipartite and multipartite methods" from Jean-Michel Muller, Elementary Functions: Algorithms and Implementation, 2nd edition, Birkhäuser Boston, 2005.
2. D. DasSarma and D.W. Matula, "Faithful Bipartite ROM Reciprocal Tables," Proc. 12th Symp. Computer Arithmetic, pp. 17-28, July 1995.
3. 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.
4. F. de Dinechin and A. Tisserand. Multipartite Table Methods. IEEE Transactions on Computers, 54(3):319-330, March 2005.

Sum of bit-products

1. 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.
2. 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.
3. 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.
4. 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.

CORDIC

1. 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.
2. Y. Hu, "CORDIC-based VLSI architectures for digital signal pprocessing," IEEE Signal processing Magazine, vol. 9, no. 3, pp. 16-35, July 1992.
3. E Antelo, J Villalba, JD Bruguera, EL Zapata, "High performance rotation architectures based on the radix-4 CORDIC algorithm," IEEE Transactions on Computers, 1997.
4. 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 on processors

1. 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
2. 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.
3. Jean-Michel Muller, Generating functions at compile-time (invited talk), 40th Asilomar Conference on signals, systems and computers, Pacific Grove, California, Nov. 2006.
4. Lynch, T.; Ahmed, A.; Schulte, M.; Callaway, T.; Tisdale, R, "The K5 transcendental functions," Proceedings of the 12th Symposium on Computer Arithmetic, 19-21 July 1995 Page(s):163 - 170

General references

1. Jean-Michel Muller, Elementary Functions: Algorithms and Implementation, 2nd edition, Birkhäuser Boston, 2005.
2. 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.
3. N. H. F. Beebe, "A bibliography of publications about the computation of elementary functions in computer programming languagues"

Teacher: Oscar Gustafsson
Examination: 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 corresponding architecture(s).
Credits: 6 HP (+3 HP for optional research oriented project)