scientific article; zbMATH DE number 3896264
bibliographydiscrete Fourier transformfast Fourier transformfast transformsFermat number transformHaar transformMersenne number transformnumber theoretic transformssignal filteringsignal processingspectral analysisWalsh functionsWalsh-Hadamard transforms
Arithmetic and combinatorial problems involving abstract finite groups (20D60) Trigonometric interpolation (42A15) Signal detection and filtering (aspects of stochastic processes) (60G35) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
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.
- Transform decomposition in two-dimensional digital filter realization
- The decimation-in-frequency algorithms for a family of discrete sine and cosine transforms
- Index transforms for multidimensional DFT's and convolutions
- Iterative methods for ill-conditioned Toeplitz matrices
- An analytic approach to practical state space reconstruction
- Rapid solution of integral equations of scattering theory in two dimensions
- Discrepancy-based error estimates for quasi-Monte Carlo. III: Error distributions and central limits
- Non-Gaussian distributions
- Probabilistic analysis on the splitting-shooting method for image transformations
- In-place self-sorting fast Fourier transform algorithm with local memory references
- Fast progressive reconstruction of images using the DCT
- Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation
- Semi-analytic time-marching algorithms for semilinear parabolic equations
- Discrete Fourier transform computation using prime Ramanujan numbers
- Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems
- Non-Gaussian distributions.
- Double coset decompositions and computational harmonic analysis on groups
- Algorithms for fast convolutions on motion groups
- Interactions and stability of solitary waves in shallow water.
- Separation of variables and the computation of Fourier transforms on finite groups. II
- Nonlinear \(q\)-ary codes with large code distance
- The efficient computation of Fourier transforms on semisimple algebras
- Fast W transform. Algorithms and programs
- Generalised intermediate transforms: Methods of computation and potential applications
- A fast algorithm for expansion over spherical harmonics
- Fast transforms of Toeplitz matrices
- Characteristic vector and weight distribution of a linear code
- A new class of quaternary codes
- Orthogonal transforms in bases of slant step functions. II: Methods of generating orthogonal slant transforms with fast algorithms for image coding and compression
- Exploiting compression in solving discretized linear systems
- Fast algorithm for transformation of lattices
- A signal theory approach to support vector classification: the sinc kernel
- Advances on random sequence generation by uniform cellular automata
- Numerical transforms
- Fundamental solutions for singularities within a layered solid
- scientific article; zbMATH DE number 4155738 (Why is no real title available?)
- Efficient Computation of the Fourier Transform on Finite Groups
- scientific article; zbMATH DE number 3917667 (Why is no real title available?)
- scientific article; zbMATH DE number 3926790 (Why is no real title available?)
- scientific article; zbMATH DE number 3932301 (Why is no real title available?)
- scientific article; zbMATH DE number 1134974 (Why is no real title available?)
- The efficient computation of Fourier transforms on the symmetric group
- A generalized reverse jacket transform
- scientific article; zbMATH DE number 790342 (Why is no real title available?)
- scientific article; zbMATH DE number 922651 (Why is no real title available?)
- On some properties of Toeplitz matrices
- Quantum mechanics on ${\mathbb Q}/{\mathbb Z}$Q/Z
- Number theoretic fast algorithms for bilinear and other generalized transformations
- Constructive universal algebra: An introduction
- scientific article; zbMATH DE number 7590336 (Why is no real title available?)
- Fast algorithms for Walsh transform in bit-reversed sequency order
- Symmetry-based matrix factorization
- Computation of approximate optimal policies in a partially observed inventory model with rain checks
- Evolving generation and fast algorithms of slantlet transform and slantlet-Walsh transform
- The smoothing properties of variational schemes for surface design
- Transforms and fast algorithms for signal analysis and representations.
- Improved upper complexity bounds for the discrete Fourier transform
- Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3675490)