Fourier Transform & the DFT

The Fourier transform is a change of coordinates. Instead of asking for a signal's value at each time, it asks how strongly the signal aligns with every rotating complex exponential. Magnitude records how much of a frequency is present; phase records where that component sits in time. No information is lost when the transform and its inverse use a consistent convention.

The continuous transform, Fourier series, discrete-time transform, and DFT answer related but different questions. Most implementation errors come from moving between them without carrying the record duration, sampling interval, frequency grid, and normalization.

One mechanism, four domains #

For the continuous convention in hertz,

$$X(f)=\int_{-\infty}^{\infty}x(t)e^{-j2\pi ft}\,dt, \qquad x(t)=\int_{-\infty}^{\infty}X(f)e^{j2\pi ft}\,df.$$

Using angular frequency $\omega=2\pi f$ moves the $2\pi$ into the inverse measure. Neither convention is more correct; mixing them is wrong.

For a finite sequence $x[0],\ldots,x[N-1]$, NumPy's default DFT convention is

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}, \qquad k=0,\ldots,N-1,$$

with inverse

$$x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j2\pi kn/N}.$$

The forward transform is unscaled and the inverse carries $1/N$. Libraries also offer a unitary convention, with $1/\sqrt N$ in both directions, or a forward-normalized convention. The pair is what matters.

flowchart LR
  CT["Continuous signal x(t)"] -->|"sample every Δt"| S["N samples x[n]"]
  S -->|"N-point DFT"| B["N complex bins X[k]"]
  B -->|"inverse DFT"| S
  S -->|"interpret with fs and N"| F["frequencies fk = k fs / N"]

A DFT bin is a complex correlation #

The basis vector with index $k$ is

$$v_k[n]=e^{j2\pi kn/N}.$$

The DFT coefficient $X[k]$ is the inner product of $x$ with $v_k$: multiply by the conjugate rotating phasor and sum. If the signal rotates at exactly the same rate, every product points in the same direction and adds coherently. Orthogonal bin-centred components sum to zero.

This geometric view explains both amplitude and phase. If

$$x[n]=A\cos\left(2\pi k_0n/N+\phi\right),$$

and $k_0$ is neither DC nor Nyquist, then a two-sided unscaled DFT has

$$X[k_0]=\frac{AN}{2}e^{j\phi}, \qquad X[N-k_0]=\frac{AN}{2}e^{-j\phi}.$$

The real cosine is the sum of positive- and negative-frequency complex exponentials. Consequently, its amplitude is recovered as $2|X[k_0]|/N$ from a one-sided plot. DC and the even-$N$ Nyquist bin are not doubled because they do not have distinct partners.

The grid follows from the record #

With sampling rate $f_s$ and $N$ samples, the observation duration is $T=N/f_s$ and the DFT grid spacing is

$$\Delta f=\frac{f_s}{N}=\frac{1}{T}.$$

Bins $0\ldots\lfloor N/2\rfloor$ represent non-negative frequencies. In the usual unshifted ordering, the remaining bins represent negative frequencies:

$$f_k=\begin{cases} kf_s/N,&0\le k\le\lfloor N/2\rfloor,\\ (k-N)f_s/N,&\lfloor N/2\rfloor<k<N. \end{cases}$$

For even $N$, bin $N/2$ is the Nyquist frequency and represents both $+f_s/2$ and $-f_s/2$; for real data it must be real. fftshift only reorders bins so negative frequencies appear left of zero. It does not change the transform.

Longer observation creates a finer physical grid. Appending zeros asks for more samples of the same finite-record transform between the original bins; it makes a curve look smoother but does not separate components that the original duration cannot resolve. Resolution belongs to spectral estimation, not to the array length passed to an FFT routine.

Worked transform: four samples #

Take $x=[0,1,0,0]$. It is a unit impulse delayed by one sample:

$$X[k]=e^{-j2\pi k/4}=[1,-j,-1,j].$$

Every bin has unit magnitude. Delay has changed phase, not magnitude: the phase decreases linearly with frequency. Applying the inverse,

$$x[1]=\frac14\left(1+(-j)j+(-1)(-1)+j(-j)\right)=1,$$

and the other time samples cancel to zero. This is the shift theorem in its smallest nontrivial form.

The same calculation gives a practical invariant: a circular shift by $n_0$ samples multiplies each bin by $e^{-j2\pi kn_0/N}$. If a pipeline moves a waveform and its magnitude spectrum changes substantially, the cause is not the ideal shift alone.

Real signals have conjugate symmetry #

If every $x[n]$ is real,

$$X[(-k)\bmod N]=X[k]^*.$$

The DC bin $X[0]$ is therefore real; for even $N$, the Nyquist bin $X[N/2]$ is real as well. The negative-frequency half is redundant, so real-input routines return $N/2+1$ values for even $N$. This saves computation and storage, but it does not turn a complex analytic signal into a real signal: calling a real FFT on complex input may discard the imaginary part.

Symmetry also catches data corruption. Except for round-off, a full DFT of a real record must be Hermitian. An unmatched positive-frequency bin means the input or the indexing assumption is not real-valued.

Energy and units #

With the unscaled-forward convention, Parseval's identity is

$$\sum_{n=0}^{N-1}|x[n]|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2.$$

This is an excellent normalization test. It does not by itself turn $|X[k]|^2$ into a power spectral density. A PSD has units of signal-unit squared per hertz and must include the sampling rate, window energy, and one- versus two-sided convention. A raw squared magnitude has different units and scales with $N$.

Three common outputs therefore answer different questions:

The table assumes no detrending and names only the core normalization. An estimator must document its exact convention.

Multiplication and convolution swap roles #

For length-$N$ sequences, the DFT diagonalizes circular convolution:

$$\mathop{\mathrm{DFT}}\{x\circledast h\}[k]=X[k]H[k].$$

The inverse transform of a product wraps time indices modulo $N$. To compute linear convolution of lengths $L_x$ and $L_h$ with an FFT, zero-pad both to at least $L_x+L_h-1$ before multiplying. Otherwise the tail folds onto the beginning.

Conversely, multiplication by a window in time convolves the signal spectrum with the window spectrum. That is the mechanism behind leakage: recording only a finite interval implicitly multiplies an infinite signal by a rectangular window. Choosing another window changes that convolution kernel; it cannot remove the finite-record tradeoff.

The DFT is a matrix, the FFT is an algorithm #

The DFT can be written $X=Fx$ with

$$F_{k,n}=e^{-j2\pi kn/N}.$$

Each row of $F$ is one correlation recipe, so $Fx$ packages all $N$ row-by-column dot products at once.

Its rows are orthogonal and $F^{-1}=F^*/N$. Direct matrix multiplication takes $O(N^2)$ complex operations. Cooley and Tukey's 1965 paper showed how factorizations of $N$ split the same transform into smaller transforms; radix-2 FFTs reduce work to $O(N\log N)$. The result is not an approximation and not a different spectrum. FFT refers to a family of algorithms for evaluating the DFT.

Factorization affects speed. Power-of-two lengths are convenient, but modern libraries also handle mixed radices and primes. Padding a length merely to make an FFT fast can alter record interpretation if the caller later mistakes the padded duration for observed data.

Two dimensions and images #

For an $M\times N$ array,

$$X[k,\ell]=\sum_{m=0}^{M-1}\sum_{n=0}^{N-1} x[m,n]e^{-j2\pi(km/M+\ell n/N)}.$$

The transform is separable: apply a one-dimensional DFT along rows, then columns. Low spatial frequencies describe slowly varying image structure; high frequencies describe rapid changes such as texture and edges. A two-dimensional spectrum is periodic in both axes, and fftshift is commonly used to display DC at the centre.

Image codecs rarely take one global complex DFT. Block transforms such as the DCT use closely related real cosine bases and boundary assumptions that compact energy while avoiding explicit complex coefficients. The coordinate-change idea is the same; the coding constraints differ.

A reliable implementation checklist #

1. Record $f_s$, $N$, units, and the actual timestamp regularity with the samples.
2. Decide whether the task needs complex coefficients, amplitudes, power, or PSD.
3. State the forward/inverse normalization used by the library.
4. Use the library's frequency helper rather than hand-building an even/odd grid.
5. For real input, handle DC and Nyquist separately when making a one-sided spectrum.
6. Pad to $L_x+L_h-1$ for linear convolution; otherwise expect circular wrap.
7. Test inverse reconstruction, Parseval energy, a bin-centred sinusoid, a delayed impulse, and even/odd lengths.
8. Treat windowing, detrending, averaging, and confidence as estimator choices outside the bare DFT.