What is Discrete Fourier transform?

A computation that converts N samples x[0] to x[N − 1] into N frequency components X[0] to X[N − 1]. It is defined by X[k] = Σx[n]e^(−j2πkn/N), and component k corresponds to the frequency k·fs/N. The bin spacing fs/N is the reciprocal of the observation time and indicates the frequency resolution. For a real signal, X[N − k] is the complex conjugate of X[k], so k = 0 to N/2 carries all the information. Computed from the definition it needs about N² operations, which the fast Fourier transform (FFT) reduces to about N log₂N. It is abbreviated DFT, which is unrelated to DFT in the sense of design for testability.

Japanese name: 離散フーリエ変換

Discrete Fourier transform appears in 2 practice questions across 2 topics, including Digital Signal Processing Basics, Wireless Communication Basics.

Field: Digital Signal Processing Basics

What the DFT assumes

The DFT assumes that the N observed points are one period of a repeating signal. If a sine wave fits a whole number of periods into the interval, the component falls in a single bin; otherwise the interval is treated as if its two ends joined discontinuously, and the energy spreads into the surrounding bins (spectral leakage). In measurements, a window function is therefore often applied before the DFT to smooth both ends of the interval.

Reading the frequency bins

k = 0 corresponds to DC (the sum of all samples) and k = N/2 to the Nyquist frequency. Bins with k above N/2 correspond to negative frequencies, and for a real signal they mirror bin k. For example, with fs = 48 kHz and N = 1024 the bin spacing is 46.875 Hz, and a 1 kHz component appears at k ≈ 21.3, between k = 21 and 22.

The inverse transform and Parseval's theorem

The inverse transform x[n] = (1/N)ΣX[k]e^(j2πkn/N) recovers the original samples exactly. Where the factor 1/N goes differs by convention, and some definitions split it as 1/√N on both sides. With X[k] defined as above, the energies on the time side and the frequency side are related by Σ|X[k]|² = N·Σ|x[n]|² (Parseval's theorem).

Try it: questions about Discrete Fourier transform

A signal sampled at 48 kHz is analyzed with a 1024-point discrete Fourier transform (DFT). Which of the following is the spacing of the frequency bins?

AAbout 23.4 Hz
BAbout 46.9 Hz
CAbout 93.8 Hz

Show answer and explanation

Answer: B. About 46.9 Hz

The bin spacing of an N-point DFT is Δf = fs/N, and 48000 ÷ 1024 = 46.875 Hz ≈ 46.9 Hz. Bin k corresponds to the frequency k × Δf: k = 0 is DC and k = N/2 = 512 is the Nyquist frequency of 24 kHz. Δf is also the reciprocal of the observation time T = N/fs ≈ 21.3 ms, so finer bins require a longer observation time.

FAQ

What is the difference between the discrete Fourier transform and the FFT?

The DFT is the definition of the transform, "what to compute", and the FFT is "a fast way (algorithm) to compute it". FFT results agree with the DFT definition apart from rounding errors. For N = 1024, the number of operations drops to about 1/100.

Does zero padding improve the frequency resolution?

No. Appending zeros makes the bin spacing finer and gives interpolated values of the spectrum, but no new information is added, so the ability to tell close frequencies apart is still set by the length of the data actually observed. Improving it requires recording data over a longer time.

Discrete Fourier transform in the explanations

SC-FDMA applies a discrete Fourier transform (DFT) to the data before mapping it onto subcarriers, producing a signal close to single-carrier with a small PAPR.
Which is the most appropriate main reason that the 4G LTE u…

Questions that mention Discrete Fourier transform (2)

Books on Digital Signal Processing Basics Ad

Search Amazon for semiconductor Digital Signal Processing Basics

As an Amazon Associate I earn from qualifying purchases.

Back to the glossary