DTFT vs DFT vs FFT: Definitions, Relationships, and Python Implementation

Introduction

DTFT, DFT, FFT — the abbreviations look almost identical, and it is easy to use them loosely without internalizing what each one really means. In fact the three are sharply distinct:

• DTFT (Discrete-Time Fourier Transform) — a continuous frequency representation of a discrete-time signal
• DFT (Discrete Fourier Transform) — the DTFT sampled on the frequency axis
• FFT (Fast Fourier Transform) — an algorithm that computes the DFT efficiently

This article walks through the chain from continuous-time signals to sampled signals and then to spectra, organizes the definitions and relationships of DTFT/DFT/FFT, and finally compares a direct DFT computation with np.fft.fft in Python to confirm understanding.

The companion articles FFT: Theory and Python Implementation and Window Functions and PSD focus on implementations; this article complements them by laying out the underlying theory.

From Continuous to Discrete Signals

Continuous-Time Fourier Transform (CTFT)

The Fourier transform of a continuous-time signal \(x_c(t)\) is defined as

where \(\Omega\) is the continuous angular frequency in rad/s. \(X_c(j\Omega)\) is a continuous function of frequency.

Discretization via Sampling

As covered in the sampling theorem article, sampling \(x_c(t)\) with period \(T_s\) (rate \(f_s = 1/T_s\) ) yields the discrete-time signal \(x[n] = x_c(nT_s)\) . The discrete-domain angular frequency \(\omega\) relates to the continuous one \(\Omega\) by

\(\omega\) has units of rad/sample and is \(2\pi\) -periodic. This is the natural axis on which DTFT and DFT are defined.

DTFT: Discrete-Time Fourier Transform

Definition

For a discrete-time signal \(x[n]\) (\(n \in \mathbb{Z}\) ), the DTFT is

where \(\omega \in \mathbb{R}\) is a continuous angular frequency in rad/sample, and \(X(e^{j\omega})\) is a \(2\pi\) -periodic continuous function of \(\omega\) .

Inverse DTFT

The integration window \([-\pi, \pi]\) covers a full period.

Key Properties

• Periodicity: \(X(e^{j(\omega + 2\pi)}) = X(e^{j\omega})\)
• Linearity: \(\mathcal{F}\{a x_1[n] + b x_2[n]\} = a X_1(e^{j\omega}) + b X_2(e^{j\omega})\)
• Time shift: \(\mathcal{F}\{x[n - k]\} = e^{-j\omega k} X(e^{j\omega})\)
• Convolution theorem: \(\mathcal{F}\{x_1[n] * x_2[n]\} = X_1(e^{j\omega})\, X_2(e^{j\omega})\)
• Parseval: \(\sum_{n} |x[n]|^2 = \dfrac{1}{2\pi}\int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega\)

Connection to the Z-Transform

As the Z-transform article shows, the DTFT is the Z-transform \(X(z) = \sum_n x[n] z^{-n}\) evaluated on the unit circle \(z = e^{j\omega}\) . The DTFT exists only when the ROC of the Z-transform contains the unit circle.

Why the DTFT Alone Is Not Enough on a Computer

Two practical issues prevent direct numerical use:

1. Infinite sum — undefined for finite memory.
2. Continuous frequency axis — \(\omega \in \mathbb{R}\) cannot be stored as-is.

The DFT addresses both.

DFT: Discrete Fourier Transform

Definition

For a finite-length signal \(x[n]\) (\(n = 0, 1, \ldots, N-1\) ), the DFT is

The DFT is a finite-to-finite map: \(N\) samples in, \(N\) samples out. This is the central distinction from the DTFT.

Inverse DFT (IDFT)

Relationship Between DTFT and DFT

The DFT samples the DTFT at \(N\) equally spaced frequencies \(\omega_k = 2\pi k / N\) (\(k = 0, \ldots, N-1\) ):

In other words, the DFT is the DTFT discretized on the frequency axis as well, producing a finite data structure that fits in memory. \(X[k]\) are samples of the continuous spectrum \(X(e^{j\omega})\) , and values between bins are not represented.

Frequency Resolution

For sampling rate \(f_s\) and DFT length \(N\) , bin \(k\) corresponds to physical frequency

with bin spacing \(\Delta f = f_s / N\) . The longer the observation window \(T = N/f_s\) , the finer the resolution.

Spectral Leakage

Equation \((5)\) implicitly assumes that \(x[n]\) is periodic with period \(N\) . When the actual signal does not match this implied period, finite-length truncation causes spectral leakage, mitigated by window functions.

FFT: Fast Fourier Transform

The FFT Is an Algorithm

A crucial point: the FFT is not a new transform, but a family of algorithms that compute the DFT efficiently. The output \(X[k]\) is exactly the DFT — only the procedure differs.

A naive evaluation of equation \((5)\) requires \(N\) complex multiplications per output bin, summing to \(O(N^2)\) operations overall. For \(N = 10^6\) that is \(10^{12}\) operations — far beyond real-time.

The Cooley-Tukey Idea

The 1965 Cooley-Tukey FFT splits a length-\(N\) DFT (with \(N\) composite, especially a power of two) into two length-\(N/2\) DFTs. With \(x_e[m] = x[2m]\) and \(x_o[m] = x[2m+1]\) ,

where \(W_N = e^{-j 2\pi / N}\) . Using the symmetry \(W_N^{k + N/2} = -W_N^k\) ,

— the butterfly operation. Recursive halving gives the recurrence \(T(N) = 2T(N/2) + O(N)\) , whose solution is

A full derivation is in the FFT article.

Complexity Comparison

The advantage of the FFT grows quickly with \(N\) .

Beyond radix-2

Production FFT libraries combine several algorithms to handle non-power-of-two lengths efficiently:

• radix-2 / radix-4 / split-radix — the staple algorithms for power-of-two lengths
• mixed-radix — generalization to any composite \(N = N_1 N_2\)
• Bluestein / chirp-Z — chirp-convolution transform for arbitrary \(N\)
• Rader — cyclic-convolution transform for prime \(N\)

NumPy’s np.fft.fft (FFTPACK / pocketfft underneath) dispatches between these, so the FFT remains efficient even when \(N\) is not a power of two.

Putting DTFT, DFT, and FFT Together

Concisely:

• DTFT — the theoretical definition.
• DFT — DTFT sampled in frequency; the finite, computable version.
• FFT — an \(O(N \log N)\) algorithm for the DFT.

The output of an FFT is the DFT — distinguishing the algorithm from the transform is conceptually important.

Comparing Direct DFT and FFT in Python

Direct DFT from the Definition

In matrix form, the DFT is \(X = W x\) with the DFT matrix \(W_{kn} = e^{-j 2\pi kn / N}\) . NumPy broadcasting gives a one-line implementation.

import numpy as np

def dft_direct(x: np.ndarray) -> np.ndarray:
    """Compute the DFT directly in O(N^2)."""
    x = np.asarray(x, dtype=complex)
    N = x.shape[0]
    n = np.arange(N)
    k = n.reshape(-1, 1)                 # column vector
    W = np.exp(-2j * np.pi * k * n / N)  # DFT matrix (N x N)
    return W @ x

# --- Verify against np.fft.fft ---
rng = np.random.default_rng(0)
x = rng.standard_normal(256) + 1j * rng.standard_normal(256)

X_dft = dft_direct(x)
X_fft = np.fft.fft(x)

abs_err = np.max(np.abs(X_dft - X_fft))
print(f"max absolute error: {abs_err:.3e}")
# Example output: max absolute error: 4.27e-13

The discrepancy is at floating-point round-off level (\(\sim 10^{-13}\) ), confirming that the FFT computes the DFT exactly (to machine precision).

Timing the Two

Vary \(N\) to feel the gap between \(O(N^2)\) and \(O(N \log N)\) .

import time
import numpy as np
import matplotlib.pyplot as plt

def dft_direct(x):
    x = np.asarray(x, dtype=complex)
    N = x.shape[0]
    n = np.arange(N)
    k = n.reshape(-1, 1)
    W = np.exp(-2j * np.pi * k * n / N)
    return W @ x

sizes = [2**p for p in range(6, 13)]  # 64, 128, ..., 4096
t_dft, t_fft = [], []

for N in sizes:
    x = np.random.randn(N) + 1j * np.random.randn(N)

    # Direct DFT (matrix product)
    t0 = time.perf_counter()
    _ = dft_direct(x)
    t_dft.append(time.perf_counter() - t0)

    # np.fft.fft
    t0 = time.perf_counter()
    _ = np.fft.fft(x)
    t_fft.append(time.perf_counter() - t0)

plt.figure(figsize=(8, 5))
plt.loglog(sizes, t_dft, 'o-', label='DFT direct  (O(N^2))')
plt.loglog(sizes, t_fft, 's-', label='np.fft.fft  (O(N log N))')
plt.xlabel('N (signal length)')
plt.ylabel('Elapsed time [s]')
plt.title('DFT vs FFT: computational cost')
plt.grid(True, which='both', alpha=0.3)
plt.legend()
plt.tight_layout()
plt.show()

On a log-log plot, the direct DFT line has slope \(\approx 2\) (\(O(N^2)\) ) while the FFT line is nearly linear (\(O(N \log N)\) ). The gap widens rapidly with \(N\) .

Visualizing the DTFT (Bonus)

To inspect the spectrum between DFT bins, zero-pad the signal before the FFT — this samples the DTFT more densely without adding new information.

import numpy as np
import matplotlib.pyplot as plt

N = 32
n = np.arange(N)
x = np.cos(2 * np.pi * 0.1 * n)  # normalized frequency 0.1 cycles/sample

# DFT (N points)
X_dft = np.fft.fft(x)
freqs_dft = np.fft.fftfreq(N)

# DTFT approximation via zero padding (4096 points)
N_pad = 4096
X_dtft = np.fft.fft(x, n=N_pad)
freqs_dtft = np.fft.fftfreq(N_pad)

mask_dft = freqs_dft >= 0
mask_dtft = freqs_dtft >= 0

plt.figure(figsize=(9, 4))
plt.plot(freqs_dtft[mask_dtft], np.abs(X_dtft[mask_dtft]),
         'b-', alpha=0.6, label='DTFT (zero-padded approx.)')
plt.stem(freqs_dft[mask_dft], np.abs(X_dft[mask_dft]),
         linefmt='r-', markerfmt='ro', basefmt=' ',
         label='DFT bins')
plt.xlabel('Normalized frequency [cycles/sample]')
plt.ylabel('Magnitude')
plt.title('DFT bins as samples of the continuous DTFT')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

The plot makes it visually obvious that DFT bins (red) are samples of the continuous DTFT curve (blue).

Summary

• The DTFT is the continuous-frequency representation of a discrete signal — the Z-transform restricted to the unit circle.
• The DFT is the DTFT sampled at \(N\) equally spaced frequencies — a finite, computable form.
• The FFT is an \(O(N \log N)\) algorithm for the DFT (the output equals the DFT exactly).
• For large \(N\) , the FFT is decisively faster — at \(N = 2^{20}\) the speedup is in the tens of thousands.
• Zero padding does not add information; it is dense sampling of the underlying DTFT.

Holding this hierarchy in mind makes downstream topics — windowing, PSD estimation, filter design — easier to navigate, because it is always clear which axis you are working on.

Related Articles

• Fast Fourier Transform (FFT): Theory and Python Implementation — A detailed derivation of Cooley-Tukey and a recursive Python implementation.
• Window Functions and Power Spectral Density — Mitigates the spectral leakage caused by the DFT’s finite length, and covers Welch’s PSD estimation.
• Sampling Theorem and Aliasing — The gateway from continuous to discrete signals; underpins the discrete-frequency notion used here.
• Z-Transform and Digital Filter Transfer Functions — The DTFT is the Z-transform on the unit circle; pole-zero geometry drives the frequency response.

References

• Cooley, J. W., & Tukey, J. W. (1965). “An algorithm for the machine calculation of complex Fourier series.” Mathematics of Computation, 19(90), 297-301.
• Oppenheim, A. V., & Schafer, R. W. (2009). Discrete-Time Signal Processing (3rd ed.). Prentice Hall.
• Proakis, J. G., & Manolakis, D. G. (2006). Digital Signal Processing (4th ed.). Prentice Hall.
• NumPy FFT documentation