5. Discrete Fourier Transform and Fast Algorithms

Introduction and Context

The Fourier transform provides a means of viewing a signal in terms of frequency rather than time. For continuous-time signals, the continuous-time Fourier transform is fundamental; for discrete-time sequences, the discrete-time Fourier transform (DTFT) provides an analogous description. The DTFT, however, is generally a continuous function of frequency and is not directly suited to finite numerical computation. The discrete Fourier transform (DFT) resolves this difficulty by representing a finite sequence through a finite set of equally spaced frequency samples.

The DFT is central to digital signal processing because it connects theoretical frequency analysis with implementable computation. It is used in spectrum analysis, filtering, audio and image processing, communications, radar, biomedical instrumentation, vibration monitoring, and control. Its principal limitation is computational cost: direct evaluation of an N-point DFT requires order N² operations. Fast Fourier transform (FFT) algorithms reduce this cost to order N log₂N by exploiting the algebraic structure of the DFT. The inverse FFT (IFFT) reconstructs time-domain samples from frequency-domain data.

A rigorous use of the DFT requires more than memorizing its formula. The analyst must understand periodicity, circular convolution, leakage, windowing, frequency resolution, zero padding, aliasing, and the distinction between computational frequency spacing and true resolving capability.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Derive the DFT and inverse DFT from finite-length sequence representations.

2. Interpret DFT samples as frequency samples of a periodically extended sequence.

3. Explain leakage, window effects, resolution, zero padding, and spectral estimation choices.

4. Derive the radix-2 decimation-in-time FFT and describe decimation-in-frequency processing.

5. Implement and assess DFT, FFT, and IFFT computations.

6. Relate circular convolution to multiplication in the DFT domain and obtain linear convolution through zero padding.

7. Compare the computational complexity, numerical behavior, and practical suitability of alternative methods.

8. Apply these ideas to engineering measurement and signal-processing problems.

From Finite Sequences to the DFT

For an N-point sequence x[n], defined for 0 ≤ n ≤ N−1, the N-point DFT is

X[k] = Σ from n=0 to N−1 x[n] exp(−j2πkn/N), k = 0, 1, …, N−1.

Defining the twiddle factor W_N = exp(−j2π/N), the expression becomes

X[k] = Σ x[n]W_N^(kn).

The inverse DFT is

x[n] = (1/N) Σ from k=0 to N−1 X[k] exp(j2πkn/N).

The factor 1/N may instead be divided symmetrically between the forward and inverse transforms in some software libraries, but the pair must remain mutually consistent.

The DFT samples the DTFT at frequencies ω_k = 2πk/N. In physical frequency, for a sampling frequency f_s, the kth bin corresponds to

f_k = kf_s/N.

Bins above N/2 are commonly interpreted as negative frequencies for real-valued signals: bin k corresponds to (k−N)f_s/N when k > N/2. Thus, the DFT does not create arbitrary new frequency information; it samples a periodic spectrum at equally spaced points.

A useful interpretation is obtained by imagining that the given N samples are one period of an indefinitely repeated sequence. The DFT is precisely the Fourier-series coefficient representation of this periodic sequence, with a scaling convention. This interpretation explains why the DFT naturally produces circular rather than ordinary linear convolution.

For real x[n], the spectrum has conjugate symmetry:

X[N−k] = X*[k].

Consequently, only approximately half the DFT bins contain independent information. The DC component is X[0]. If N is even, the bin at N/2 is the Nyquist-frequency component and is also real-valued for a real input.

Important Properties and Terminology

Linearity follows immediately from the summation definition. If y[n] = ax[n] + bz[n], then Y[k] = aX[k] + bZ[k]. A circular time shift introduces a phase factor, while multiplication by a complex exponential shifts the spectrum circularly. Parseval’s relation connects energy in the time and frequency domains:

Σ |x[n]|² = (1/N) Σ |X[k]|².

The magnitude spectrum |X[k]| indicates the strength of frequency components, while the phase spectrum ∠X[k] records their relative timing. A power spectrum is proportional to |X[k]|², although normalization depends on whether the objective is energy measurement, power spectral density estimation, or amplitude recovery.

The bin spacing is Δf = f_s/N = 1/T, where T = N/f_s is the observation duration. Increasing N by recording more samples increases the observation time and improves the ability to distinguish nearby tones. It is therefore important to distinguish bin spacing from resolution. Zero padding increases the number of displayed frequency samples and reduces the spacing between plotted points, but it does not increase the information contained in the original record or automatically separate closely spaced tones.

Leakage, Windows, and Spectral Interpretation

Suppose a sinusoid completes an integer number of cycles in the observation interval. Its frequency coincides with a DFT bin, and, under ideal conditions, its energy is concentrated in the corresponding positive- and negative-frequency bins. If the sinusoid does not complete an integer number of cycles, truncation by the finite observation window causes its energy to spread among many bins. This phenomenon is spectral leakage.

Leakage is not an error in the DFT algorithm. It results from multiplying the infinite-duration signal by a finite rectangular window. In frequency, multiplication in time corresponds to convolution with the transform of the window. The rectangular window has a narrow main lobe but relatively high sidelobes, so it offers good nominal separation but can allow a strong tone to obscure a weak nearby tone.

A window function changes this trade-off. Common choices include Hann, Hamming, Blackman, and flat-top windows. Tapered windows reduce sidelobes but widen the main lobe. A Hann window is often a sound general-purpose choice; a flat-top window is useful when accurate amplitude estimation is more important than frequency separation. Window selection must follow the measurement objective rather than habit.

Windowed amplitude estimates require correction because the window changes coherent gain. If a sinusoid is bin-centred and the window samples are w[n], the coherent gain is approximately (1/N)Σw[n]. Dividing the measured component by this gain compensates for amplitude reduction, subject to the assumptions of the measurement. For noise and power spectral density estimation, equivalent noise bandwidth and appropriate normalization are also important.

Leakage should not be confused with spectral smearing caused by noise, oscillator instability, modulation, or changing frequency. In practical systems, a spectrum may contain all of these effects simultaneously.

Circular Convolution and Linear Convolution

The circular convolution of two N-point sequences x[n] and h[n] is

y[n] = Σ from m=0 to N−1 x[m]h[(n−m) mod N].

The DFT convolution theorem states that

DFT{x circular-convolved h} = X[k]H[k].

Therefore circular convolution can be performed by taking two DFTs, multiplying corresponding bins, and applying an IFFT. This is the basis of frequency-domain filtering.

Linear convolution is different. If x[n] has length L and h[n] has length M, the linear convolution has length L+M−1. To obtain it using an N-point DFT, choose N ≥ L+M−1 and append zeros to both sequences until length N. The resulting circular convolution then equals the desired linear convolution over the valid output interval. If insufficient zero padding is used, the tail of the linear convolution wraps around and contaminates the beginning; this is called time aliasing.

For long signals, overlap-add and overlap-save methods divide the signal into blocks. In overlap-add, blocks are zero padded, convolved using FFTs, and overlapping output sections are added. In overlap-save, overlapping input blocks are processed and corrupted initial samples are discarded. These methods make FFT-based filtering practical for streaming systems while controlling memory and latency.

Deriving the Radix-2 FFT

The direct DFT evaluates N² complex multiply-accumulate terms. The FFT does not approximate the DFT; it computes exactly the same mathematical transform, apart from finite-precision effects, but avoids repeated computation.

For an even N, separate the input into even and odd indices:

X[k] = Σ x[2r]W_N^(2rk) + Σ x[2r+1]W_N^((2r+1)k).

Because W_N² = W_{N/2}, define

E[k] = Σ from r=0 to N/2−1 x[2r]W_{N/2}^(rk),

O[k] = Σ from r=0 to N/2−1 x[2r+1]W_{N/2}^(rk).

Then

X[k] = E[k] + W_N^kO[k],

and

X[k+N/2] = E[k] − W_N^kO[k],

for 0 ≤ k < N/2. The pair of equations is the radix-2 butterfly. Each N-point transform is reduced to two N/2-point transforms plus N/2 butterflies. Repeating the decomposition until two-point transforms are reached gives log₂N stages when N is a power of two.

The butterfly requires one addition and one subtraction, together with multiplication by a twiddle factor. Some twiddle factors are trivial, such as 1, −1, j, and −j, and can be implemented with little or no general multiplication.

In decimation-in-time (DIT), the input is recursively split by even and odd time indices. Iterative radix-2 DIT implementations generally require bit-reversed input ordering and produce naturally ordered output. Decimation-in-frequency (DIF) begins by splitting the output frequency indices and commonly produces bit-reversed output from naturally ordered input. These are alternative factorizations of the same DFT, not different transforms.

For N that is not a power of two, mixed-radix algorithms use factors such as 2, 3, and 5; prime-length transforms use methods such as Bluestein’s or Rader’s algorithm. Modern libraries select algorithms according to length, hardware, data type, and transform direction. Hence, padding to the next power of two is not always the most efficient choice.

Complexity and Numerical Considerations

The direct DFT requires O(N²) operations. A radix-2 FFT requires O(N log₂N) operations. For N = 1024, the conceptual scaling changes from roughly one million pairwise terms to a few thousand butterfly operations. Actual run time also depends on memory access, vectorization, cache behavior, parallelism, processor architecture, and library implementation.

The IFFT has the same asymptotic complexity as the FFT. It can be computed using a forward FFT and conjugation:

IFFT{X} = (1/N) conjugate(FFT{conjugate(X)}).

Finite precision introduces round-off error. FFT algorithms usually have better numerical behavior than direct evaluation because they use structured operations, although scaling and overflow must be managed in fixed-point systems. Floating-point cancellation can become relevant when a small component is extracted from a large spectrum. Engineering implementations should specify transform normalization, data type, scaling, and treatment of exceptional values.

A Practical Analysis Workflow

A defensible spectral analysis normally proceeds as follows. First, define the engineering question: tone frequency, amplitude, bandwidth, transient content, or noise power. Next, select the sampling rate to avoid aliasing and determine an observation duration adequate for the required frequency discrimination. Inspect the record for trends, offsets, missing data, clipping, and nonstationarity. Remove an unwanted mean or trend only when justified, since preprocessing changes the spectrum.

Then select a window consistent with the measurement objective. Compute an FFT, map bins to physical frequencies, and apply appropriate amplitude or power normalization. Examine both magnitude and phase where timing or system identification matters. Validate the result using a known test signal, energy checks, or a second acquisition with a changed record length. A spectrum should be interpreted in relation to the acquisition process, not treated as an independent truth source.

Applied Case: FFT-Based Vibration Diagnosis

Background

Consider an illustrative case involving a motor-driven pump monitored by an accelerometer. The sampling frequency is 12,000 Hz, and 24,000 samples are acquired during normal operation. The shaft speed is approximately 1,800 revolutions per minute, or 30 Hz. Engineers wish to determine whether a rising vibration level is caused by imbalance or a bearing-related defect.

Situation and Analysis

A 24,000-point FFT gives a bin spacing of 0.5 Hz. The 30 Hz rotational component is therefore bin-centred if the speed remains exactly constant. A rectangular-window spectrum shows a strong component near 30 Hz and several harmonics. However, speed variation during the record causes spreading around the rotational frequency. A Hann window reduces sidelobes and makes weaker components easier to inspect, although its wider main lobe must be considered when distinguishing closely spaced tones.

The analyst removes the sensor’s DC offset, applies the selected window, and computes the FFT. The positive-frequency half is displayed after amplitude normalization and coherent-gain correction. A peak near 30 Hz with harmonics is consistent with imbalance or misalignment, but it is not by itself diagnostic. Bearing faults may produce characteristic repetitive components and sidebands; their identification requires knowledge of bearing geometry, shaft speed, and often envelope analysis.

Approach and Outcome

The team compares spectra from several operating speeds and uses a tachometer reference. Peaks that track shaft speed support a rotational source. Components that remain at characteristic bearing-related orders or appear as sidebands around rotational frequencies warrant further inspection. The FFT is complemented by time-domain waveform analysis and trend monitoring rather than used as the sole decision criterion.

Learning Points

The case illustrates that a longer record improves bin spacing, but speed variation can still complicate interpretation. Window choice affects visibility, normalization affects amplitude conclusions, and engineering diagnosis requires physical context. A computationally efficient FFT does not remove the need for sound measurement design.

Challenges, Risks, and Common Mistakes

A frequent mistake is to identify Δf = f_s/N as guaranteed frequency resolution. It is the frequency-grid spacing; the ability to resolve tones also depends on window main-lobe width, signal-to-noise ratio, record stability, and estimator design. Another mistake is assuming that zero padding creates new resolution. It produces smoother sampling of the underlying finite-record spectrum and can improve peak interpolation, but it cannot recover unrecorded information.

Other common errors include interpreting the two-sided spectrum as one-sided without correcting amplitude, forgetting the factor of two for non-DC, non-Nyquist components in a one-sided spectrum, using a rectangular window for every task, and failing to zero pad before FFT-based linear convolution. Spectral peaks can also be caused by sensor resonance, electrical interference, aliasing, or leakage rather than the phenomenon under investigation.

Aliasing must be controlled before the DFT by suitable analog anti-alias filtering and an adequate sampling rate. Once aliased components enter the sampled data, an FFT cannot identify their original frequencies. In streaming applications, latency, block boundaries, overlap, and computational deadlines are system-level constraints, not merely coding details.

Professional and Emerging Practice

Modern DSP software commonly uses optimized FFT libraries, SIMD instructions, multicore processors, GPUs, and embedded DSP hardware. Real-time systems may use fixed-point arithmetic, DMA transfers, double buffering, and precomputed twiddle factors. Automated spectral monitoring can calculate peak features, band power, spectral kurtosis, or order-tracking indicators, while machine-learning models may classify machine conditions from these features.

Automation does not eliminate professional responsibility. Engineers must document sampling conditions, calibration, window and normalization choices, uncertainty, data provenance, and decision thresholds. In safety-related or regulated systems, diagnostic algorithms require validation over representative operating conditions, version control, traceability, and appropriate human review. A model trained on one machine or operating regime may fail when applied elsewhere.

Best practice is therefore to treat the FFT as a mathematically exact computational tool embedded within a measurement system. The quality of the result depends on acquisition, preprocessing, transform conventions, interpretation, and validation.

Chapter Summary

The DFT represents an N-sample sequence by N equally spaced frequency samples and has a corresponding inverse transform. It can be interpreted as the Fourier-series description of a periodic extension of the finite record. Its properties explain conjugate symmetry, phase behavior, Parseval energy relations, and the connection between multiplication and circular convolution.

Finite observation causes leakage when signal frequencies do not align with DFT bins. Windowing trades main-lobe width against sidelobe level, while zero padding refines the frequency grid without adding information. Linear convolution can be computed through circular convolution when adequate zero padding is used. Radix-2 FFT algorithms exploit even–odd decomposition and butterfly operations to reduce complexity from O(N²) to O(N log N). Practical spectral analysis requires attention to sampling, normalization, resolution, amplitude correction, aliasing, numerical precision, and the physical meaning of observed components.

Key Terms

DFT: Finite-length transform that maps N time samples to N discrete frequency samples.

IDFT: Inverse operation that reconstructs the finite sequence from DFT coefficients.

FFT: A fast algorithm for computing the DFT efficiently.

IFFT: An efficient algorithm for computing the inverse DFT.

Twiddle factor: The complex factor W_N^k = exp(−j2πk/N) used in DFT computation.

Bin: One discrete frequency location in a DFT.

Bin spacing: Frequency separation between adjacent DFT bins, equal to f_s/N.

Spectral leakage: Spreading of a finite-record component across frequency bins.

Window: A sequence used to taper or weight a finite data record before transformation.

Main lobe: Central concentration region of a window spectrum around a component.

Sidelobe: Secondary spectral region away from the main lobe.

Coherent gain: Amplitude reduction imposed by a window on a bin-centred sinusoid.

Zero padding: Appending zeros to a record before transformation or convolution.

Circular convolution: Convolution in which indices wrap modulo N.

Linear convolution: Ordinary convolution whose output length is L+M−1.

Time aliasing: Wraparound contamination caused by insufficient padding in circular convolution.

Butterfly: Basic sum-and-difference computation in an FFT.

Bit reversal: Permutation of indices used in many iterative FFT implementations.

Conjugate symmetry: Property X[N−k] = X*[k] for real-valued sequences.

Parseval relation: Equality connecting time-domain and frequency-domain energy.

Review Questions

Short Answer Questions

1. Define the N-point DFT and state the role of its frequency index k.

2. Why does a real-valued sequence have conjugate-symmetric DFT coefficients?

3. Distinguish DFT bin spacing from frequency resolution.

4. What is spectral leakage, and why does it occur?

5. State the condition under which circular convolution equals linear convolution after DFT processing.

Long Answer Questions

1. Derive the inverse DFT and explain the interpretation of the DFT as the Fourier-series representation of a periodic sequence.

2. Explain the effects of rectangular, Hann, and flat-top windows on main-lobe width, sidelobes, and amplitude measurement.

3. Derive the radix-2 decimation-in-time FFT using even and odd input samples.

4. Explain overlap-add and overlap-save methods for block-based FFT filtering.

5. Discuss the computational and numerical differences between direct DFT evaluation and FFT implementation.

Analytical / Application Questions

1. A 4,000 Hz sampled signal is analyzed using an 8,000-point DFT. Calculate the bin spacing and explain whether zero padding would improve the ability to distinguish two closely spaced tones.

2. A length-100 sequence is convolved with a length-60 sequence using an FFT. Determine the minimum transform length required to avoid circular wraparound and explain the consequence of using a shorter length.

3. In a vibration measurement, a strong non-bin-centred tone masks a weaker nearby component. Recommend a window and an acquisition strategy, and justify the trade-offs involved.

22. Multiple Choice Questions with Answers

Question 1

For an N-point DFT sampled at f_s, what is the frequency spacing between adjacent bins?

A. f_s/N

B. N/f_s

C. f_s(N−1)

D. 2πNf_s

Correct Answer: A. f_s/N

Question 2

Which statement best describes zero padding before an FFT?

A. It removes aliasing already present in sampled data.

B. It increases the information content of the original record.

C. It provides more closely spaced samples of the finite-record spectrum.

D. It always improves the ability to resolve two nearby tones.

Correct Answer: C. It provides more closely spaced samples of the finite-record spectrum.

Question 3

For a real-valued time sequence, which DFT relationship is generally valid?

A. X[k] = X[k+1]

B. X[N−k] = X*[k]

C. X[N−k] = −X[k]

D. X[k] is purely imaginary for every k

Correct Answer: B. X[N−k] = X*[k]

Question 4

What is the principal computational advantage of a radix-2 FFT over direct DFT evaluation?

A. It changes the DFT into an approximation.

B. It reduces complexity from order N² to order N log₂N.

C. It eliminates the need for an inverse transform.

D. It operates without complex arithmetic.

Correct Answer: B. It reduces complexity from order N² to order N log₂N.

Question 5

A sinusoid does not complete an integer number of cycles in the observation interval. What is the most likely consequence?

A. Spectral leakage

B. Perfect concentration in one DFT bin

C. Elimination of its phase information

D. Automatic removal of its DC component

Correct Answer: A. Spectral leakage

Question 6

To compute the linear convolution of sequences of lengths L and M using one circular convolution, the transform length should be at least

A. max(L,M)

B. L+M−2

C. L+M−1

D. LM

Correct Answer: C. L+M−1

Question 7

In a radix-2 decimation-in-time FFT, an N-point transform is first decomposed into

A. two N-point transforms

B. one N/2-point transform and one N/4-point transform

C. two N/2-point transforms based on even and odd samples

D. N one-point transforms with no recombination

Correct Answer: C. two N/2-point transforms based on even and odd samples

Question 8

Which window is generally associated with reduced sidelobes compared with a rectangular window, at the cost of a wider main lobe?

A. Hann window

B. Impulse window

C. Infinite window

D. Unit-delay window

Correct Answer: A. Hann window

Question 9

If insufficient zero padding is used for FFT-based convolution, what artifact results?

A. Time-domain wraparound or time aliasing

B. Improved frequency resolution

C. Guaranteed cancellation of sidelobes

D. Removal of numerical round-off

Correct Answer: A. Time-domain wraparound or time aliasing

Question 10

For an IFFT convention in which the inverse includes 1/N, which identity is valid?

A. IFFT(X) = FFT(X)

B. IFFT(X) = N·FFT(X)

C. IFFT(X) = (1/N)conjugate(FFT(conjugate(X)))

D. IFFT(X) = FFT(conjugate(X)) without scaling

Correct Answer: C. IFFT(X) = (1/N)conjugate(FFT(conjugate(X)))