⏱️ 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
  1. What the DFT solves that the DTFT does not
  2. The DFT: treating N samples as one period of a periodic signal
  3. The DFT is the sampled DTFT: the relationship that connects both transforms
  4. What it means for you: when to pick DFT, FFT, or neither
  5. DFT vs. STFT, DCT, and the wavelet transform
  6. When the DFT falls short: limitations and costs
  7. What the community says about this series
  8. Frequently Asked Questions about the DFT
    1. Are the DFT and the FFT the same thing?
    2. Why does the DFT assume the signal is periodic when in reality it isn’t?
  9. 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 turns N samples of a signal into N frequency coefficients. Foto de CDC en Unsplash

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.

TechniqueWhat it adds over the DFTWhen to use itKey limitation
DFT (this article)Baseline: frequencies for the whole block of N samples, with no time informationStationary signal or analysis of a fixed blockLoses when each frequency occurs within the block
STFT (short-time Fourier transform)Applies the DFT over sliding windows to locate frequency in timeAudio spectrograms, speech, vibrationFixed trade-off between time and frequency resolution set by window size
DCT (discrete cosine transform)Uses only real cosines and concentrates energy in few coefficientsCompression (JPEG, MP3) where file size matters more than phaseDiscards the phase information the DFT keeps
Wavelet transformChanges time-frequency resolution by scale instead of using a fixed windowBrief or transient events: fault detection, seismic analysisMore complex to implement and interpret than a direct FFT
Each technique splits time and frequency resolution differently. Foto de ThisisEngineering en Unsplash

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).

📬 Get new articles by email

We only email about big articles (1-2 a month).

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

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
Categories: Tech NewsTutorials

El Solitario Editorial

Article prepared by the El Solitario editorial team from cited sources, under the editorial responsibility of Luis Navarro. More details in "How we work".

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *

You can include code inside <code>…</code> or, for several lines, <pre><code>…</code></pre>.

This site uses Akismet to reduce spam. Learn how your comment data is processed.