Skip to main content

Über dieses Buch

The discrete Fourier transform (DFT) is an extremely useful tool that finds application in many different disciplines. However, its use requires caution. The aim of this book is to explain the DFT and its various artifacts and pitfalls and to show how to avoid these (whenever possible), or at least how to recognize them in order to avoid misinterpretations. This concentrated treatment of the DFT artifacts and pitfalls in a single volume is, indeed, new, and it makes this book a valuable source of information for the widest possible range of DFT users. Special attention is given to the one and two dimensional cases due to their particular importance, but the discussion covers the general multidimensional case, too. The book favours a pictorial, intuitive approach which is supported by mathematics, and the discussion is accompanied by a large number of figures and illustrative examples, some of which are visually attractive and even spectacular.

Mastering the Discrete Fourier Transform in One, Two or Several Dimensions is intended for scientists, engineers, students and any readers who wish to widen their knowledge of the DFT and its practical use. This book will also be very useful for ‘naive’ users from various scientific or technical disciplines who have to use the DFT for their respective applications. The prerequisite mathematical background is limited to an elementary familiarity with calculus and with the continuous and discrete Fourier theory.



Chapter 1. Introduction

The discrete Fourier transform (DFT) is the discrete-world counterpart of the continuous Fourier transform (CFT). The DFT is widely used as a practical and efficient computing tool for calculating numerically the Fourier transform (i.e. the frequency spectrum) of functions or signals [Brigham88 pp. xiv, 1–3, 98]. In many circumstances the values of our given signal are only known on a discrete grid (for example, if the signal values have been measured at discrete intervals or obtained by a digital computer). In such cases using DFT is the natural way for computing the Fourier transform of the given data. But even when the given signal is a continuous function whose analytical expression is fully known, DFT often remains the most convenient way for getting a visual glimpse at its spectrum, especially when the analytic calculation of the continuous Fourier transform proves to be too laborious or impractical
Isaac Amidror

Chapter 2. Background and basic notions

In this chapter we review the main definitions and notations that are being used in the literature for the continuous Fourier transform and for its discrete counterpart. Unfortunately, no standard definition exists for the Fourier transform, and one may find in the literature several slightly different variants. Although these variants are essentially equivalent in terms of the Fourier theory, each of them gives slightly different results, and one should be aware of this fact to avoid any possible confusion, especially when working with several textbooks, references or Fourier software packages
Isaac Amidror

Chapter 3. Data reorganizations for the DFT and the IDFT

While the continuous Fourier transform takes as its input a function g(x) and returns as its output another function G(u), the discrete Fourier transform takes as its input a sequence of N values and returns as its output another sequence of N values. However, if we consider the input and output sequences of the DFT as a digital approximation to the continuous-world functions g(x) and G(u), we must be aware of an important difference between the continuous and discrete cases, which may be a source of many pitfalls and errors. While the continuous functions g(x) and G(u) are generally defined throughout a continuous domain along their x or u axes, the input and output sequences of the DFT are only defined on a discrete domain consisting of N consecutive points, and outside this domain they are considered to behave periodically. Furthermore, for reasons we will see below the discrete values which correspond to x = 0 or u = 0 are not necessarily located in the center of the input or output sequences of the DFT. Therefore, in order to present or plot these discrete sequences the way they would be presented in the continuous world, one may need to reorganize them, i.e. to reorder the sequence elements differently (or more precisely, to shift the N-element sequence along its periodic replications until the elements corresponding to x = 0 or u = 0 fall where they are expected to be with respect to their continuous-world counterparts). This is also true in the 2D and MD cases, where the same reasoning applies along each dimension individually.
Isaac Amidror

Chapter 4. True units along the axes when plotting the DFT

As already mentioned above, the DFT is often used as a tool for the numerical calculation of the Fourier transform (the frequency spectrum) of a given continuous function. For this end, the original continuous function in question must be sampled, and the resulting N-element array (or in the MD case, N N-element array) is fed as input to the DFT. The resulting N-element (or N N-element) output array contains the discrete counterpart of the desired frequency spectrum, and after the appropriate reorganization (see Chapter 3) it can be plotted to illustrate graphically the resulting spectrum.
Isaac Amidror

Chapter 5. Issues related to aliasing

When the DFT is used as a numerical approximation to the Fourier transform of an underlying continuous function, some differences can be expected between the two. For example, it is clear that the DFT can only give us the Fourier transform values at the N discrete points for which the computation is done. However, even at these points there may appear in some cases quite significant discrepancies, in spite of the adjustments and scalings discussed above in Chapters 3 and 4. This is not a result of rounding errors in the calculations, which are normally quite insignificant (see Sec. 8.8). The main reason for these discrepancies resides in the discrete and finite nature of the DFT, which implies that the underlying continuous function must be sampled, and that it can only be considered within a finite range.
Isaac Amidror

Chapter 6. Issues related to leakage

After having discussed in Chapter 5 the aliasing artifact, we arrive now to the second major source of discrepancy between the DFT results and the continuous Fourier transform, the leakage artifact. Once again we start with the 1D case, and only then we proceed to the more general multidimensional case.
Isaac Amidror

Chapter 7. Issues related to resolution and range

In this chapter we explain how to choose optimal values for the various parameters that are related to the resolution and the range of the DFT data, both in the signal and in the spectral domains. We discuss the significance of these parameters, and show the interconnections between them. Although the discussion is provided here for the 1D case, it can be readily extended to any multidimensional case, too.
Isaac Amidror

Chapter 8. Miscellaneous issues

In this chapter we group together some further questions and potential pitfalls that may await the unaware DFT users, but which do not fit into any of the previous chapters. In Sec. 8.2 we discuss the representation of discontinuities in the discrete world, in the input and output arrays of the DFT. In Sec. 8.3 we briefly review issues and artifacts that are related to the phase when using the polar (i.e. magnitude and phase) representation of the complex-valued spectrum. Then, in Sec. 8.4 we discuss symmetry related issues and the DFT artifacts that may result thereof. In Sec. 8.5 and 8.6 we discuss two artifacts that may occur due to sampling and reconstruction of continuous-world signals, namely, jaggies and sub-Nyquist artifacts, respectively. These two discrete-world artifacts are not specific to DFT, but they do occur in DFT applications, too, and we seize the opportunity offered by their explanation here to illustrate some questions related to DFT spectra and their continuous-world counterparts. Then, in Sec. 8.7 we review the main displaying considerations that should be taken into account in order to obtain a correct graphic representation of the DFT results, and finally in Sec. 8.8 we review very briefly some numeric precision considerations.
Isaac Amidror

Appendix A. Impulses in the continuous and discrete worlds

The mathematical concept of an impulse is widely utilized in many disciplines, including physics, electricity, optics, etc. It is used to represent entities that are concentrated in a single point, such as a point mass, a point charge, etc. Although such entities do not exist in the real world, this theoretical concept is very useful since it may considerably simplify derivations [Bracewell86 Chapter 5; Brigham88 Appendix A].
Isaac Amidror

Appendix B. Data extensions and their effects on the DFT results

1D DFT algorithms receive as input a 1D array of N complex numbers (say, samples of a given continuous complex- or real-valued function y = g(x)), and return as their output a 1D array of N complex numbers which contains the discrete frequency spectrum. However, when the result obtained by DFT with N data values is not yet satisfactory, one may wonder if a larger number of data values could improve the results. In fact, there exist several possible ways to extend the input data for the DFT, each of which yields quite different results. In this appendix we examine 6 of the most simple ways of extending the input data, and explain how they influence the DFT results (including the possible effects on the DFT artifacts). As we will see, some of these 6 methods are indeed useful and advantageous, depending on one’s aims and also on the nature of the data, while others are rather misleading and may introduce significant artifacts. Note that although the discussion in this appendix is presented for the 1D case, its generalization to 2D or MD DFT is straightforward.
Isaac Amidror

Appendix C. The roles of p and q and their interconnections

As we have seen throughout this book, and in particular in Chapters 5 and 6, cases in which the original input function is periodic are particularly interesting, among other reasons due to the impulsive nature of their spectra. In this appendix we study in more detail some properties of such periodic cases in the discrete world, and provide their multidimensional generalization.
Isaac Amidror

Appendix D. Miscellaneous remarks and derivations

As we have seen in Sec. 2.5, the DFT imposes a cyclic behaviour on both of its input and output data sequences, in the sense that each of them should be understood as a single N-element period (or “truncation window”) from a periodic sequence which repeatedly extends to both directions ad infinitum (even if the underlying continuous data before sampling was not periodic). In the informal graphical development of the DFT, as presented in Sec. 2.5, this periodicity is explained by the fact that sampling (i.e. multiplication with an infinite impulse train) in one domain is equivalent to a convolution with the reciprocal infinite impulse train in the other domain. Thus, sampling in the signal domain results in a periodic behaviour in the frequency domain, and sampling in the frequency domain results in a periodic behaviour in the signal domain (see Fig. 2.1).
Isaac Amidror

Appendix E. Glossary of the main terms

Because the DFT has a very wide range of applications in many different fields of science and technology (see end of Sec. 1.2), it is not surprising that the terminology used in the vast DFT literature is far from being consistent and uniform. In many cases different authors use different terms for the same entities, and what is even worse, the same terms are often used in different meanings by different authors. As a few examples among many others, let us mention here the various Fourier theorems (or “rules”; see Sec. 2.4), whose names greatly vary between different sources. For instance, the inversion rule [Kammler07 p. 199] is called symmetry rule in [Brigham88 p. 107], while in [Bracewell86 pp. 364–365] it is called reciprocity and the term symmetry is reserved to properties related to oddness and evenness [Bracewell86 p. 366]. Similarly, the reflection rule [Kammler07 p. 199] is called in [Bracewell86 p. 366] reversal while in [Nussbaumer82 p. 82] the term being used is symmetry (again!). Even the aliasing artifact is often called foldover, and the leakage artifact is sometimes called ringing [Brigham88 pp. 94, 106].
Isaac Amidror


Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!