The DFT

Eight samples of two cosines, each multiplied by a turning probe and added up. Watch a bar rise only where a probe matches a cosine.

A signal of $N$ samples, $N$ numbers of spectrum

Sampling the spectrum (13.1) ended with a count. A computer keeps $N$ samples of a signal, and it can keep $N$ values of its spectrum, one at each $\Omega_k=2\pi k/N$. Those $N$ values are the discrete Fourier transform, or DFT.

For a signal $x[n]$ of $N$ samples, $n=0,\dots,N-1$, the DFT gives $N$ values, one for each $k$ from 0 to $N-1$:

and the signal comes back with

There is no scale on the forward transform and a $1/N$ on the way back, which is also what NumPy does. Many books write $W_N^{kn}$ for $e^{-j2\pi kn/N}$, with $W_N=e^{-j2\pi/N}$.

Read the forward sum as a recipe. The arrow $e^{-j2\pi kn/N}$ is probe $k$: it turns back $k/N$ of a turn for every sample. Multiply each sample by the probe’s arrow for that sample, add the results, and you have bin $k$, the number $X[k]$. It is the winding of Fourier series coefficients (7.2) and the chain of The DTFT (12.2), now with $N$ fixed probes. When $x$ has at most $N$ samples, bin $k$ is the DTFT sampled at $\Omega_k$.

Each bin: the signal times a probe, added up

I use one signal of $N=8$ samples: $x[n]=\cos(2\pi n/8)+0.5\cos(2\pi\cdot3n/8)$. It is two cosines, one that turns 1 time in 8 samples and one, half as big, that turns 3 times. Its samples are $1.5$, $0.354$, $0$, $-0.354$, $-1.5$, $-0.354$, $0$ and $0.354$.

The picture at the top of the page uses this signal. I will follow it bin by bin.

The probe for $k=0$ does not turn, so $X[0]$ only adds up the samples, and these eight cancel: $x$ has no average. The probe for $k=1$ turns with the first cosine. That part of every arrow points the same way and adds up, and the rest closes into a loop, so $X[1]=4$, half of 8 times the cosine’s size 1.

No part of $x$ turns at the rate of probe 2, so its chain comes back to 0. Probe 3 matches the second cosine, and $X[3]=2$, half of 8 times 0.5. Bin 4 is 0. Bins 5, 6 and 7 come last, as mirrors of bins 3, 2 and 1.

When the clip has finished, tap a bar, or use the arrow keys, to rebuild that bin’s chain. Tap bin 5 and watch it: “k = 5 turns like k = −3: the mirror of bin 3. X[5] = 2.”

Why does a chain close into a loop? A probe and a cosine that do not turn at matching rates leave arrows pointing all round the circle, and equal steps around the circle add to 0 (the roots of unity of Complex numbers for signals, 3.3). Only a part that the probe turns to a constant direction survives. Think of pushing a swing: pushes in step with the swing add up, and pushes out of step cancel.

A bin is a complex number

Bins are complex in general. The instrument’s signal gave real bins, because its two cosines are even about $n=0$. A signal that starts at $n=0$ and runs on one side does not.

Take $x=1,1,1,1,0,0,0,0$. Its first four samples are the only ones that count, so bin 1 is $\sum_{n=0}^{3}e^{-j\pi n/4}=1+(0.707-0.707j)+(-j)+(-0.707-0.707j)$, which is $1-2.414j$. Its size is $\sqrt{1+2.414^2}=2.613$ and its angle is $-67.5°$ ($-0.375\pi$ rad). The size says how much of probe 1 the signal has, and the angle says where in its turn.

All eight bins are $4$, $1-2.414j$, $0$, $1-0.414j$, $0$, $1+0.414j$, $0$, $1+2.414j$. The sizes are $4$, $2.613$, $0$, $1.082$, $0$, $1.082$, $0$, $2.613$, and the angles are $0$, $-67.5°$, $-$, $-22.5°$, $-$, $22.5°$, $-$, $67.5°$. A dash marks a bin of size 0, which has no angle.

To check the inverse at $n=0$, add all eight bins and divide by 8. The imaginary parts cancel in pairs, the real parts add to 8, and $x[0]=8/8=1$.

Bins in hertz, and the mirror

Bin $k$ is the frequency at which probe $k$ turns: $k/N$ of a turn per sample, which is $\Omega_k=2\pi k/N$ rad/sample. Sampled at $f_s$, that is

For $N=8$ and $f_s=8$ kHz the bins are 0, 1, 2, 3 and 4 kHz. Bin $N/2$ is $f_s/2$, the Nyquist frequency of Sampling & aliasing (10.1).

Bins above $N/2$ follow the rule of Frequency in discrete time (12.1). A probe that turns more than half a turn per sample is the same as one that turns backward by the rest, so bin $k$ with $k>N/2$ is the frequency $(k-N)f_s/N$. Bins 5, 6 and 7 are $-3$, $-2$ and $-1$ kHz.

Bin 4 sits on the boundary. This page writes it as $+f_s/2$, but NumPy’s fftfreq lists it as $-f_s/2$, and the two are the same frequency.

The mirror in the last frame of the first instrument follows from the definition. Put $N-k$ in place of $k$:

because $e^{-j2\pi n}=1$ for whole $n$. This is the conjugate of probe $k$. If $x[n]$ is real, then $X[N-k]=X^*[k]$: the sizes of the bins mirror about $N/2$, and the angles flip sign. This is the DFT form of the real-signal symmetry of Properties of the DTFT (12.3), and it is why a real signal’s information sits in bins 0 to $N/2$. For the 1, 1, 1, 1, 0, 0, 0, 0 signal above, bins 1 and 7 are $1-2.414j$ and $1+2.414j$.

Two tones 100 Hz apart, more and more bins

Now the other question: how close can two frequencies be before the bins cannot tell them apart? Bins sit $\Delta f=f_s/N$ apart, so a longer record gives more of them. With $f_s=8$ kHz and $N$ samples the record lasts $N/f_s$ s, and $\Delta f$ is one over that time in seconds.

The next picture records two tones 100 Hz apart, at 1000 and 1100 Hz, and doubles $N$ three times. Watch when the two tones stop sharing a bar.

When the clip has finished, drag across the plot, or use the arrow keys, to set $N$ yourself, from 16 to 320.

Notice what the tones do at each stage. They share a bin at 400 Hz spacing and smear into a shoulder at 200 Hz. They take adjacent bins at 100 Hz, and at 50 Hz an empty bin separates them. The rule is $\Delta f=f_s/N$ at or below the gap, which is $N\ge f_s/\text{gap}$. For a gap of 100 Hz at 8 kHz that is $N\ge80$, a record of $80/8000=0.01$ s. Put another way, a record needs to be at least $1/\text{gap}$ seconds long. A ruler marked only every centimetre has the same limit: it cannot tell 3.2 cm from 3.3 cm.

Both tones here sit exactly on a bin at the chosen $N$ (they are multiples of 100 Hz), so the picture is clean. A tone between two bins spreads into all of them, which is called leakage, and Windowing & spectral leakage (15.1) takes it up.

Energy in time and in bins

The bins keep all the energy of the signal, with one factor. Parseval’s relation, which Properties of the DTFT (12.3) wrote as an integral, is a sum here:

For the instrument’s signal the time side is $5$, and the bin side is $(16+4+4+16)/8=5$.

Worked example

1. By hand. For $x=1,1,1,1,0,0,0,0$, bin 1 is $1-2.414j$, size 2.613 and angle $-67.5°$. All the bins are above. Parseval: the time side is $4$, and the sizes squared are $16$, $6.828$, $0$, $1.172$, $0$, $1.172$, $0$, $6.828$, which add to 32, so the bin side is $32/8=4$.
2. The instrument’s signal. $X=0$, $4$, $0$, $2$, $0$, $2$, $0$, $4$, and $5=40/8$.
3. Which bin? A 1 kHz tone at $f_s=8$ kHz with $N=64$ lands in bin $k=Nf/f_s=64\times1000/8000=8$.
4. Bin spacing. At $f_s=48$ kHz and $N=4096$ the spacing is $48000/4096=11.72$ Hz.
5. Resolution. To separate tones 100 Hz apart at 8 kHz you need $N\ge8000/100=80$ samples, a record of 0.01 s.
6. Hertz of bins. For $N=8$ and $f_s=8$ kHz the bins are $0$, $1$, $2$, $3$, $4$, $-3$, $-2$, $-1$ kHz.

Where you’ll meet this

Properties of the DFT (13.3) shows what a shift or a reversal does to the bins, once indices wrap round modulo $N$. The DFT as a matrix (13.5) writes all $N$ probes as the rows of one matrix. The sum above costs $N^2$ multiplications, and The FFT (14.1) gets the same bins with far fewer. Windowing & spectral leakage (15.1) handles tones between bins, and Zero-padding and resolution (15.3) shows what padding with zeros does and does not give you.

Reference card