Mathwords logoMathwords

Discrete Fourier Transform — Definition, Formula & Examples

The Discrete Fourier Transform (DFT) is a mathematical operation that takes a finite sequence of equally spaced samples and converts it into a sequence of complex numbers representing the amplitude and phase of each frequency component.

Given a sequence of NN complex numbers x0,x1,…,xN−1x_0, x_1, \ldots, x_{N-1}, the Discrete Fourier Transform produces a new sequence X0,X1,…,XN−1X_0, X_1, \ldots, X_{N-1} defined by Xk=∑n=0N−1xn e−i 2πkn/NX_k = \sum_{n=0}^{N-1} x_n \, e^{-i\,2\pi kn/N} for k=0,1,…,N−1k = 0, 1, \ldots, N-1. The inverse transform recovers the original sequence via xn=1N∑k=0N−1Xk e i 2πkn/Nx_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k \, e^{\,i\,2\pi kn/N}.

Key Formula

Xk=∑n=0N−1xn e−i 2πkn/N,k=0,1,…,N−1X_k = \sum_{n=0}^{N-1} x_n \, e^{-i\,2\pi kn / N}, \quad k = 0, 1, \ldots, N-1
Where:
  • xnx_n = The $n$-th sample of the input sequence
  • XkX_k = The $k$-th frequency-domain output coefficient
  • NN = Total number of samples in the sequence
  • ii = The imaginary unit, $i = \sqrt{-1}$
  • kk = Frequency index

How It Works

Each output XkX_k measures how much the input signal correlates with a complex exponential at frequency kk. The index k=0k=0 gives the sum of all samples (the DC component), while higher kk values correspond to higher-frequency oscillations. You compute each XkX_k by multiplying every input sample xnx_n by a rotating complex exponential (a "twiddle factor") and summing the results. In practice, the Fast Fourier Transform (FFT) algorithm computes the DFT in O(Nlog⁡N)O(N \log N) operations instead of the naive O(N2)O(N^2).

Worked Example

Problem: Compute the DFT of the 4-point sequence x=(1,2,3,4)x = (1, 2, 3, 4).
Setup: Here N=4N = 4, so the twiddle factor base is W=e−i 2π/4=e−iπ/2=−iW = e^{-i\,2\pi/4} = e^{-i\pi/2} = -i. We need Xk=∑n=03xn WknX_k = \sum_{n=0}^{3} x_n \, W^{kn}.
W=e−iπ/2=−iW = e^{-i\pi/2} = -i
Compute X_0: For k=0k = 0, every power of WW is 1, so X0X_0 is the sum of all samples.
X0=1+2+3+4=10X_0 = 1 + 2 + 3 + 4 = 10
Compute X_1: Use W0=1W^0 = 1, W1=−iW^1 = -i, W2=−1W^2 = -1, W3=iW^3 = i.
X1=1(1)+2(−i)+3(−1)+4(i)=1−2i−3+4i=−2+2iX_1 = 1(1) + 2(-i) + 3(-1) + 4(i) = 1 - 2i - 3 + 4i = -2 + 2i
Compute X_2: Powers cycle: W0=1W^0=1, W2=−1W^2=-1, W4=1W^4=1, W6=−1W^6=-1.
X2=1(1)+2(−1)+3(1)+4(−1)=1−2+3−4=−2X_2 = 1(1) + 2(-1) + 3(1) + 4(-1) = 1 - 2 + 3 - 4 = -2
Compute X_3: Powers: W0=1W^0=1, W3=iW^3=i, W6=−1W^6=-1, W9=−iW^9=-i.
X3=1(1)+2(i)+3(−1)+4(−i)=1+2i−3−4i=−2−2iX_3 = 1(1) + 2(i) + 3(-1) + 4(-i) = 1 + 2i - 3 - 4i = -2 - 2i
Answer: X=(10,  −2+2i,  −2,  −2−2i)X = (10,\; -2+2i,\; -2,\; -2-2i)

Why It Matters

The DFT is the computational backbone of signal processing, audio analysis, image compression (JPEG), and spectral methods for solving differential equations. Engineers and data scientists rely on FFT implementations of the DFT in nearly every domain that involves analyzing periodic or frequency-domain behavior.

Common Mistakes

Mistake: Confusing the sign convention in the exponent between the forward and inverse transforms.
Correction: The standard forward DFT uses e−i 2πkn/Ne^{-i\,2\pi kn/N} (negative exponent). The inverse uses e+i 2πkn/Ne^{+i\,2\pi kn/N} with a 1/N1/N normalization factor. Some references swap this convention, so always check which definition your textbook or software uses.