5 Assessing Discrete Fourier Transform

Question 1

Why DFT?

Answer 1

The Discrete Fourier Transform (DFT) calculates all the allowed
spectral coefficients c_k from any time series x_n

Question 2

Equation for spectral coefficient and time series?

Answer 2

Question 3

What is FFT?

Answer 3

• The Fast Fourier Transform (FFT) is the numerical implementation of the Discrete Fourier Transform (DFT) on a computer
• The FFT identifies repetitive numerical operations (additions and multiplications) during the calculation of the DFT

Question 4

FFT and recursive schemes?

Answer 4

• Repetitive calculations are avoided by using a recursive scheme where the current calculations are based on previous calculations
• The numerical accuracy/stability of the recursive scheme is the key to a successful recursive numerical calculation of the DFT
• The FFT starts with a one point transform and extends the length of the transform by a factor of 2 during each step of the recursion

Question 5

The number of arithmetic operations required for an FFT?

Answer 5

The computation of the FFT requires ~N log2 (N) arithmetic
operations (additions/multiplications) on a computer,

Question 6

The number of arithmetic operations required by a DFT?

Answer 6

the DFT requires ~N².

Question 7

Calculation difference between FFT and DFT?

Answer 7

For example, N = 1024 -\> N2 = 1048576,
N log2 (N) = 1024 x 10 = 10240 -\> ~99 % savings

Question 8

FFT pros and cons?

Answer 8

• The FFT is relatively fast if the number of time series samples is an integer multiple of 2, such as 2, 4, 8, 16, 32, … or 2ⁿ
• The FFT is relatively slow if the number of time series samples is a prime number, such as 3, 5, 7, 11, 13, …
• An FFT with ~10⁶ samples takes ~10 ms on a normal computer

Question 9

Why is it important to have a few arithmetic operations?

Answer 9

Each arithmetic operation consumes a small amount of electrical power such that devices with limited power supply (e.g., mobile phones, GPS navigation devices, satellites…) require the most efficient numerical algorithm to analyze time series.

Question 10

Harmonic frequency?

Answer 10

Each spectral coefficient c_k is uniquely associated with one harmonic frequency f_k f = k/T

Question 11

Amplitude spectrum?

Answer 11

The graphical display of all absolute values c_k versus their
harmonic frequencies f_k is called the amplitude spectrum

Question 12

Phase spectrum?

Answer 12

The graphical display of all the phases Φ_k versus their harmonic
frequencies f_k is called the phase spectrum

Question 13

The frequency resolution?

Answer 13

The frequency resolution of the amplitude spectrum and the phase spectrum is given by the difference between two adjacent frequencies which corresponds to the fundamental frequency

Question 14

Equation for frequency resolution?

Answer 14

Question 15

What is used to check the correctness of the spectral coefficients?

Answer 15

Parseval’s law states that the sum of squared samples should be the same as the sum of squared amplitudes of the spectral coefficients, including a scaling factor.

Question 16

The equation for Parseval’s Law

Answer 16

Question 17

Energy conservation within Parseval’s theorem?

Answer 17

The sum of squared samples is called the total energy of the time series. In this sense, Parseval’s law is somehow equivalent to a statement of energy conservation.

Question 18

Three key applications of DFT?

Answer 18

First, the DFT can calculate a signal’s frequency spectrum. This is a direct examination of information encoded in the frequency, phase, and amplitude of the component sinusoids. For example, human speech and hearing use signals with this type of encoding.

Second, the DFT can find a system’s frequency response from the system’s impulse response, and vice versa. This allows systems to be analyzed in the frequency domain, just as convolution allows systems to be analyzed in the time domain.

Third, the DFT can be used as an intermediate step in more elaborate signal processing techniques. The classic example of this is FFT convolution, an algorithm for convolving signals that is hundreds of times faster than conventional methods.

Question 19

Specific applications of the DFT

Answer 19

The Fourier Transform is an important image processing tool which is used to decompose an image into its sine and cosine components. The output of the transformation represents the image in the Fourier or frequency domain, while the input image is the spatial domain equivalent.