Digital Alias-free Signal Processing

16

Complexity-reduced DFT

As the regularity of signal sample value positioning in time is a crucial precondition for operation of the fast signal processing algorithms, these types of algorithms, in general, are inappropriate for processing the digital signals obtained as a result of deliberate randomization of the sampling process. There are, however, exceptions, some of which are described in Section 15.3. These exceptions actually prove the rule as the applicability of the FFT in those cases is based on the rarely usable regularization of the randomized sampling procedure. Thus the fact remains that the strategy for rationalizing the nonuniform sampled signal processing cannot be based on application of the popular fast DSP algorithms. Other approaches to the algorithm complexity reduction have to be found and exploited. Some useful techniques for that are suggested and discussed in this chapter.

The possibility of reducing the computational burden for the DFT, achieved by applying the methods for complexity-reduced spectral analysis, while attractive, is always especially interesting for increasing the speed of on-line estimations of Fourier coefficients, which often have to be carried out using various types of signal preprocessing operations. An example illustrating this kind of signal preprocessing and the benefits that can be obtained is described in Section 19.6.

16.1 Potential Gains from Application of Rectangular Function Sets

The number of multiplication operations ...