Fast transforms. Algorithms, analyses, applications.

*(English)*Zbl 0562.65097
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.

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 |