⏱️ Reading time: 9 min
The FFT routine that runs in NumPy, SciPy or any audio library does not invent anything new: it computes, in an optimized way, the discrete Fourier transform (DFT), the operation that turns N samples of a signal into the coefficients that describe which frequencies compose it. Understanding the DFT from the inside helps decide when to trust that black box and when not to, something Eli Bendersky breaks down step by step in the latest post of his series on Fourier analysis.
📑 En este artículo
- What the DFT solves that the DTFT does not
- The DFT: treating N samples as one period of a periodic signal
- The DFT is the sampled DTFT: the relationship that connects both transforms
- What it means for you: when to pick DFT, FFT, or neither
- DFT vs. STFT, DCT, and the wavelet transform
- When the DFT falls short: limitations and costs
- What the community says about this series
- Frequently Asked Questions about the DFT
- References
What the DFT solves that the DTFT does not
In the real world, signal processing works with discrete, finite data: an audio recording, a sensor reading over 10 seconds, a series of per-minute prices. One option for analyzing the frequencies in that list of N numbers is to treat it as if it were an infinite signal padded with zeros outside the sample range, and compute its Discrete-Time Fourier Transform (DTFT).
The problem is that the DTFT returns a continuous function of frequency, and a computer cannot evaluate or store it for every possible value: it has to pick which points to compute it at (source). That choice of which points to compute is exactly what the DFT solves, which is why Bendersky presents it as the practical path for a problem the DTFT leaves open.
The DFT: treating N samples as one period of a periodic signal
The approach the DFT takes is different: instead of assuming the signal is infinite with zeros around it, it assumes those N samples are a single period of a periodic signal (source). With that assumption you can use the Discrete-Time Fourier Series (DTFS), whose coefficients reconstruct a periodic signal exactly.
Since the original signal has exactly N samples and is treated as one full period, those same DTFS coefficients also reconstruct the original finite signal without any loss of information. That is the core idea behind the DFT: an exact rearrangement of the same N numbers in the frequency domain, not an approximation (source).
By convention, the DFT coefficient X[k] is defined as N times the DTFS coefficient a_k, which gives the formula found in any signal processing textbook: X[k] is the sum, for each sample n between 0 and N-1, of x[n] multiplied by a complex exponential whose phase depends on k and n (source). The result is N complex coefficients, one for each frequency the DFT can distinguish within that block of N samples.
The DFT is the sampled DTFT: the relationship that connects both transforms
The DFT does not replace the DTFT: it samples it. The value the DFT gives at position k equals the value the DTFT would give when evaluated at frequency 2πk/N (source). Put differently, the DFT is N equally spaced samples of that continuous function the DTFT could not compute in full.
This has a practical consequence: the more samples you take, the finer the sampling in frequency, although the total range of representable frequencies stays limited by the sampling rate of the original signal, not by N.
There is another way to reach the same result, and it connects the DFT to a different object: the N-th roots of unity. Those roots, raised to different powers, form an orthogonal basis of the N-dimensional complex vector space (source). Building a matrix out of those powers, the so-called Fourier matrix, computing the DFT of a signal is equivalent to multiplying that matrix by the sample vector: X = F·x (source). That part of the derivation picks up an earlier post about the roots of unity, something Bendersky himself confirmed on Hacker News when a reader asked about reconstructing the signal (HN comment).
flowchart LR
A["x[n]: N samples"] --> B["Fourier matrix F (NxN)"]
B --> C["X[k]: N coefficients"]
D["Continuous DTFT X(w)"] -. "sampled at 2*pi*k/N" .-> C
What it means for you: when to pick DFT, FFT, or neither
If you work on audio analysis, IoT sensor vibration, or signal preprocessing for a machine learning model, say generating a spectrogram that feeds a classifier, you will rarely write out the DFT sum by hand. You will call your library’s FFT routine (NumPy, SciPy, librosa, or the equivalent in your language), which computes exactly the same mathematical result Bendersky describes, only with a more efficient algorithm for large N (source).
What changes once you understand the DFT from the inside is the design decision, not the code. Knowing the result is N complex coefficients explains why half the spectrum of a real signal is symmetric and redundant, why the N you pick determines the frequency resolution you will be able to distinguish, and why zero-padding before the FFT does not add new information: it only interpolates more points over the same underlying DTFT. For anyone debugging why a spectrogram looks blurry or why two close tones blend into a single peak, that distinction between real resolution and visual interpolation saves hours of tweaking the wrong code.
DFT vs. STFT, DCT, and the wavelet transform
The DFT assumes your N samples describe a single snapshot of frequencies, with no location in time. For signals that change over time (speech, music, the vibration of a machine starting up and braking), three alternatives solve that limitation in different ways.
| Technique | What it adds over the DFT | When to use it | Key limitation |
|---|---|---|---|
| DFT (this article) | Baseline: frequencies for the whole block of N samples, with no time information | Stationary signal or analysis of a fixed block | Loses when each frequency occurs within the block |
| STFT (short-time Fourier transform) | Applies the DFT over sliding windows to locate frequency in time | Audio spectrograms, speech, vibration | Fixed trade-off between time and frequency resolution set by window size |
| DCT (discrete cosine transform) | Uses only real cosines and concentrates energy in few coefficients | Compression (JPEG, MP3) where file size matters more than phase | Discards the phase information the DFT keeps |
| Wavelet transform | Changes time-frequency resolution by scale instead of using a fixed window | Brief or transient events: fault detection, seismic analysis | More complex to implement and interpret than a direct FFT |
When the DFT falls short: limitations and costs
The DFT assumes your block of N samples is periodic. If the real signal does not start and end at the same value within that window, spectral leakage appears: the result gets polluted with frequencies that are not actually in the signal. In practice this is mitigated by applying a window function (Hann, Hamming) before computing the DFT, an engineering step Bendersky’s post does not cover because it focuses on the mathematical definition, not on preprocessing.
Computing the DFT by summing term by term, as shown in the code from the original post, has a cost that grows with the square of N: for N samples you perform on the order of N² operations, because each of the N coefficients requires summing N terms. That is manageable for short signals or for understanding the concept, but it becomes impractical for long signals, which is exactly the problem the FFT algorithm solves without changing the mathematical result, only the way of getting there.
And if what you care about is when each frequency occurs in time, the DFT alone will not give you that: that is what the STFT or the wavelet transform from the previous section are for.
What the community says about this series
The post was discussed on Hacker News, where two details came up that are not in the original article’s body. The first is methodological: in response to a reader’s question, Bendersky clarified that he writes every post in the series himself, and that he uses AI only for brainstorming, checking the math, and helping with some visualizations (HN comment). At a time when a large share of technical content circulating on blogs is produced with heavy language-model assistance, that specific clarification matters when judging a source you plan to cite in your own work.
The second is an assessment of the proof method: a reader commented that proving the relationship between the DFT and the Fourier matrix the constructive way, showing the matrix-by-vector multiplication step by step, is not the shortest path, but it is one the engineering community values because it leaves nothing to the imagination (HN comment).
Frequently Asked Questions about the DFT
Are the DFT and the FFT the same thing?
No. The DFT is the mathematical operation, the frequency coefficients that come out of N samples. The FFT is an algorithm for computing that same operation faster. Every FFT computes a DFT, but not every way of computing a DFT goes through an FFT (source).
Why does the DFT assume the signal is periodic when in reality it isn’t?
Because that is the only way to reuse the Discrete-Time Fourier Series, which does reconstruct periodic signals exactly, to analyze a finite block of samples. It is a mathematical assumption, not a claim about your real signal, and that is why spectral leakage shows up if it isn’t compensated for with a window (source).
References
- Notes on the discrete Fourier transform (DFT), Eli Bendersky’s website: primary source with the full derivation, the Python code, and the connection to the Fourier matrix.
- Hacker News discussion: thread where the post was discussed and the author answered readers’ questions.
- Eli Bendersky’s comment on Hacker News: clarifies that he writes the posts himself and uses AI only to check the math and for brainstorming.
- slow_typist’s comment on Hacker News: assesses the constructive proof of the relationship between the DFT and the Fourier matrix.
Featured image: Foto de Jumping Jax en Unsplash
How each article is made (sources, testing and editorial criteria): How we work.
Did it work for you? Got a different error? Say so below: questions get answered and help the next reader.
Leave a comment
0 Comments