Discrete Fourier transform and FFT

Why it matters

The spectrum shown on a digital oscilloscope, a vibration analyser or a power-quality meter is computed with the FFT. To read it correctly you need to know what each bin means, how fine the frequency resolution is, why a pure tone can smear into neighbouring bins, and how much computation the FFT saves — all of which comes from the discrete Fourier transform (DFT).

Key ideas

What the DFT is. For a finite block of N samples x[0] … x[N − 1], the N-point DFT gives N complex numbers X[0] … X[N − 1]. They are exactly N equally spaced samples of the DTFT over one period: X[k] = X(e^(jω)) at ω = 2πk/N.

Meaning of the bins (sampling rate fs)

• Bin k corresponds to frequency fk = k·fs/N. Bin spacing (resolution) Δf = fs/N = 1/(N·Ts) — the reciprocal of the record length in seconds.
• X[0] is N times the mean value (DC).
• For real x[n]: X[N − k] = X*[k], so bins above N/2 mirror those below; only k = 0 … N/2 carry independent information, up to fs/2.
• A cosine of amplitude A at exactly bin k0 gives |X[k0]| = |X[N − k0]| = A·N/2.

Implied periodicity. The DFT treats the N samples as one period of a periodic sequence, and the IDFT returns a periodic sequence. All shifts are therefore circular (modulo N).

Circular convolution. Multiplying two N-point DFTs corresponds to N-point circular convolution in time. To get the ordinary (linear) convolution of an L-point and an M-point sequence, zero-pad both to N ≥ L + M − 1. Long data streams are filtered block by block with overlap-add or overlap-save.

Spectral leakage. If the record does not contain a whole number of periods of a tone, the tone falls between bins and its energy spreads into many bins, with the peak reduced (up to about 36 % amplitude, or 3.9 dB, for a rectangular window). Remedies: synchronise sampling to the signal, use a tapered window (Hann, Hamming, flat-top), or use a longer record.

Zero-padding samples the same DTFT more densely; it makes peaks easier to locate but does not improve the true resolution, which is fixed by the record length.

FFT. The FFT is not a different transform; it is a fast algorithm for the DFT. Radix-2 decimation-in-time (or decimation-in-frequency) splits an N-point DFT (N a power of 2) into log2 N stages of N/2 butterflies, each needing one complex multiplication by a twiddle factor W_N^k. Decimation-in-time takes input in bit-reversed order (for N = 8: 0, 4, 2, 6, 1, 5, 3, 7) and gives output in natural order.

Formulas

• X[k] = Σ from n=0 to N−1 of x[n] W_N^(kn), k = 0 … N − 1 — DFT.
• x[n] = (1/N) Σ from k=0 to N−1 of X[k] W_N^(−kn) — inverse DFT.
• W_N = e^(−j2π/N) — twiddle factor; W_N^N = 1, W_N^(N/2) = −1.
• fk = k·fs/N, Δf = fs/N — bin frequency and resolution.
• Σ |x[n]|² = (1/N) Σ |X[k]|² — Parseval for the DFT.
• y[n] = Σ from m=0 to N−1 of x[m] h[(n − m) mod N] — circular convolution, Y[k] = X[k]H[k].
• N² complex multiplications (direct DFT) versus (N/2)·log2 N (radix-2 FFT); additions N(N − 1) versus N·log2 N.

Symbols: N number of points; n time index; k frequency index (bin); fs sampling frequency (Hz); Ts = 1/fs (s); Δf resolution (Hz); W_N twiddle factor (dimensionless).

Worked examples

Example 1 (standard). Find the 4-point DFT of x[n] = {1, 2, 3, 4} and check it with Parseval.

1. For N = 4, W_4 = e^(−jπ/2) = −j, so the powers are 1, −j, −1, j.
2. X[0] = 1 + 2 + 3 + 4 = 10.
3. X[1] = 1 + 2(−j) + 3(−1) + 4(j) = −2 + 2j.
4. X[2] = 1 − 2 + 3 − 4 = −2.
5. X[3] = 1 + 2(j) + 3(−1) + 4(−j) = −2 − 2j (= X*[1], as expected for real x).
6. Parseval: Σ x² = 30; (1/4)(100 + 8 + 4 + 8) = 30 ✓. X[k] = {10, −2 + 2j, −2, −2 − 2j}.

Example 2 (GATE level). (a) A vibration signal is sampled at 1 kHz and a 256-point FFT is taken. Find the resolution, the bin position of a 100 Hz component, and the saving in complex multiplications versus a direct DFT. (b) Find the 4-point circular convolution of {1, 2, 3, 4} with {1, 1, 0, 0}.

1. (a) Δf = 1000/256 = 3.906 Hz.
2. 100/3.906 = 25.6 — not an integer, so the tone lies between bins 25 and 26 and leaks.
3. Direct DFT: 256² = 65 536 multiplications. FFT: (256/2)·log2 256 = 128 × 8 = 1024. Saving factor = 64.
4. (b) With h = {1, 1, 0, 0}: y[n] = x[n] + x[(n − 1) mod 4].
5. y[0] = 1 + 4 = 5, y[1] = 2 + 1 = 3, y[2] = 3 + 2 = 5, y[3] = 4 + 3 = 7.
6. (a) Δf ≈ 3.91 Hz, 100 Hz at bin 25.6 (leakage), 64 times fewer multiplications; (b) y = {5, 3, 5, 7}. The linear convolution {1, 3, 5, 7, 4} has its last sample wrapped onto y[0] (1 + 4 = 5); padding to N ≥ 5 avoids this.

Common mistakes

• Calling fs/N the highest frequency; it is the spacing. The highest is fs/2.
• Expecting zero-padding to separate two close tones.
• Using linear convolution where the DFT gives circular (and vice versa).
• Forgetting the 1/N in the inverse DFT or in Parseval.
• Reading |X[k]| as the amplitude directly — divide by N/2 for a sinusoid (by N for DC).
• Thinking the FFT gives a different or more accurate answer than the DFT — it gives the same numbers faster.

For GATE IN

Expect: computing a 4- or 8-point DFT (or one coefficient of it), using DFT properties such as X[0] = Σx[n], symmetry X[N − k] = X*[k] or Parseval to find missing values, circular convolution and the padding needed for linear convolution, bin frequency and resolution from fs and N, and FFT operation counts or bit-reversed ordering. Practise the 4-point DFT by the {1, −j, −1, j} pattern until it is mechanical.

Quick check

1. A 512-point FFT at fs = 10.24 kHz — resolution?
2. For real x, X[3] = 2 − j in an 8-point DFT. What is X[5]?
3. Minimum DFT length for linear convolution of 6-point and 4-point sequences?
4. Number of stages in a 64-point radix-2 FFT?
5. 4-point DFT of {1, 0, 1, 0} — value of X[2]? Answers: 1. 20 Hz. 2. 2 + j. 3. 9. 4. log2 64 = 6. 5. 1 + 1 = 2.