Fast transforms. Algorithms, analyses, applications. (English) Zbl 0562.65097

Elliott, Douglas F.; Rao, K. Ramamohan

Orlando etc.: Academic Press, Inc. (Harcourt Brace Jovanovich, Publishers). XXII, 488 p. (1982).

This book presents fast transforms used presently in applications (spectral analysis, signal filtering etc.). The transforms include the fast Fourier transform (FFT) and its variants (due to Winograd, Nussbaumer and Quandalle), the Walsh-Hadamard transforms (WHT), the Haar transform, number theoretic and many other transforms. The book is addressed to beginning graduate students and practising engineers. Much attention is paid to various applications. The bibliography is extensive (nearly 742 entries on 30 pp.). There are many problems which partly give some new results and partly are exercises for students.
The book consists of 11 chapters, an appendix, a bibliography, an index, a (quite long) list of acronyms, and a list of notations. Chapter 1, Introduction, explains the plan of the book. The next 6 chapters deal with the Fourier transform (FT), discrete Fourier transform (DFT), FFT, and their applications. Chapter 8 deals with WHT. There are several WHT transforms which differ by the ordering of the system of the Walsh functions. Chapter 9 and 10 deal with generalized transforms. These are less familiar than the FT and WHT. Let \(\alpha\) and r be integers, f be the frequency of the generalized transform basis functions, \(s=\alpha^{r+1}f\). Define \(s=\sum^{\infty}_{k=-\infty}s_ k\alpha^ k,\) \(t=\sum^{\infty}_{k=-\infty}t_ k\alpha^ k,\) where the coefficients \(s_ k\) and \(t_ k\) are integers in the representations of s and t in a number system with base \(\alpha\), i.e. in the \(\alpha\)-ary system. The basis functions of the generalized transform are given by \(\exp \{-i2\pi \alpha^{-(r+1)}<ft>\}\) where \(<ft>\) is defined as a certain (complicated) inner product.
Finally, Chapter 11 deals with many number theoretic transforms (NTT). For example, the Fermat number transform (FNT) is defined as follows. Let \(F_ t=2^{2^ t}+1\), where \(t=0,1,2,...\), be the Fermat numbers then the FNT is defined to be the sequence \(X(k)=[\sum^{N- 1}_{n=0}x(n)\alpha^{nk}]mod\quad F_ t,\) where \(k=0,1,...N-1\), and \(N>0\) is defined by \(\alpha^ N\equiv 1(mod\) \(F_ t)\). The other NTT is the Mersenne number transform (MNT). Properties of these transforms and their applications are discussed. The book contains much material not previously available in book form. It can be used for references and for a number of courses in fast transforms and signal processing.

Reviewer: A.G.Ramm

MSC:

65T40	Numerical methods for trigonometric approximation and interpolation
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
65F30	Other matrix algorithms (MSC2010)
20D60	Arithmetic and combinatorial problems involving abstract finite groups
42A15	Trigonometric interpolation
60G35	Signal detection and filtering (aspects of stochastic processes)
94A12	Signal theory (characterization, reconstruction, filtering, etc.)
68W99	Algorithms in computer science
68Q25	Analysis of algorithms and problem complexity

Keywords:

fast transforms; spectral analysis; signal filtering; fast Fourier transform; Walsh-Hadamard transforms; Haar transform; bibliography; discrete Fourier transform; Walsh functions; number theoretic transforms; Fermat number transform; Mersenne number transform; signal processing