Sampling the spectrum

Keep only $N$ equally spaced values of the spectrum of $x=4,3,2,1$, and they describe copies of $x$, one every $N$ samples. Watch the copies close in as $N$ falls, until at $N=3$ they overlap and one period no longer reads 4, 3, 2, 1.

N numbers of a curve

The DTFT of The DTFT (12.2) is a curve: a value $X(e^{j\Omega})$ for every $\Omega$. A computer cannot hold a whole curve. It can hold $N$ numbers, so I keep $N$ equally spaced values of the curve and throw the rest away. The question for this page is what signal those $N$ numbers still describe.

The spacing between the values is $2\pi/N$. By Frequency in discrete time (12.1), frequencies $2\pi$ apart are the same frequency, so one period of $2\pi$ holds everything. I write the kept frequencies as

and the kept values as $X(e^{j\Omega_k})$. The figure shows them for $x=4,3,2,1$ at $n=0,1,2,3$, with $N=8$.

The curve starts at 10, which is the sum $4+3+2+1$, and falls to 2 at $\Omega=\pi$. The eight dots read 10, 7.25, 2.83, 2.72, 2, 2.72, 2.83 and 7.25. The dots at $k$ and $8-k$ match, because the size curve of a real signal is mirrored about $\Omega=\pi$.

What signal do N values describe?

I can rebuild a signal from the $N$ values. The DTFT (12.2) gets $x[n]$ back with an integral of $X(e^{j\Omega})e^{j\Omega n}$ over one period. I replace that integral by an average over the $N$ kept points, and call the result $\tilde x[n]$:

Now put in the definition $X(e^{j\Omega})=\sum_m x[m]e^{-j\Omega m}$ at $\Omega=2\pi k/N$ and swap the order of the sums:

The bracket holds the whole answer. If $n-m$ is a multiple of $N$, every term is $e^{j2\pi k\cdot\text{integer}}=1$, so the average is 1. If it is not, the $N$ terms are equally spaced points on the unit circle, some of them visited more than once. Equally spaced points on a circle add to 0, as in Complex numbers for signals (3.3), so the average is 0.

For $N=8$ and $n-m=3$ the eight points add to 0. For $n-m=8$ each term is 1 and the sum is 8, so the average is 1. Only the terms with $m=n-rN$, for whole numbers $r$, survive:

So $N$ values of the spectrum describe $x$ repeated every $N$ samples, with the copies added where they overlap. Each term $x[n-rN]$ is $x$ delayed by $rN$, as in Shifting, reversing and scaling time (2.1). This is The sampling theorem (10.2) with time and frequency swapped. Sampling a signal in time put copies of its spectrum every $2\pi$ in frequency. Sampling the spectrum puts copies of the signal every $N$ in time.

Fewer spectrum samples, closer copies

The picture at the top shows these copies for $x=4,3,2,1$, at $N=8$, 6, 4 and 3. Between copies it reads a gap of 4 samples, then 2, then none, then an overlap of 1 sample.

The gap follows from counting. The signal $x$ occupies 4 samples, $n=0$ to 3, and the next copy starts at $n=N$. So between them there are $N-4$ samples of zero when $N$ is greater than 4. At $N=4$ the copies touch, and below 4 they share $4-N$ samples. At $N=3$ the sample $x[3]=1$ lands on $x[0]=4$, and $4+1=5$. This overlap is time-domain aliasing: samples of different copies add and cannot be separated again. A word written on a ring of paper too short for it does the same, because the end writes over the start.

After the clip ends, drag the end of the period, or use the arrow keys, to set any $N$ from 1 to 12.

The periods the instrument shows, one period of $\tilde x$ starting at $n=0$, are:

Each one adds to 10, which is $X(e^{j0})$, the first of the kept values. Folding the samples of $x$ onto $N$ slots, as when $N=2$ puts $4+2$ and $3+1$ together, never changes their total.

Keeping x intact

The rule is a count. The copies have room while $N$ is at least the length of $x$, here 4. Then one period of $\tilde x$ is $x$ followed by zeros, and nothing is lost. For $N=8$ and $N=6$ the period is $x$ and zeros, and at $N=4$ it is $x$ alone. Below the length, the period no longer shows $x$.

A signal of length $L$ therefore needs $N\ge L$ spectrum samples. A 1 s recording at 8 kHz has $L=8000$ samples, so at least 8000 spectrum samples keep it intact.

N arrows: the discrete Fourier series

Now suppose $N$ is at least the length of $x$, so one period of $\tilde x$ is $x$ itself. The signal $\tilde x$ repeats every $N$ samples, so it is a sum of arrows, as in Fourier series coefficients (7.2). The arrows are $e^{j2\pi kn/N}$. Only $N$ of them are different: the arrow for $k+N$ turns $2\pi n$ more than the arrow for $k$ at sample $n$, which is a whole number of turns, so it gives the same samples (Frequency in discrete time, 12.1). Taking $k=0,\dots,N-1$ is enough:

This is the discrete Fourier series of the period-$N$ signal $\tilde x$, and the numbers $\tilde X[k]$ are its coefficients. It is the series of 7.2 with the integral over a period replaced by a sum over $N$ samples. When $N$ is at least the length of $x$, the coefficients $\tilde X[k]$ are exactly the $N$ spectrum samples $X(e^{j\Omega_k})$, because the only nonzero terms of the sum are $n=0$ to the end of $x$. The DFT (13.2) gives these $N$ numbers their usual name.

Worked example

1. The curve. For $x=4,3,2,1$, $\lvert X\rvert$ is 10 at $\Omega=0$, 2.828 at $0.5\pi$ and 2 at $\pi$. The eight samples are 10, 7.2545, 2.8284, 2.7153, 2, 2.7153, 2.8284 and 7.2545, the same as np.fft.fft(x, 8).
2. The periods. The one period of $\tilde x$ for $N=8$ is 4, 3, 2, 1, 0, 0, 0, 0. For $N=3$ it is 5, 3, 2, and for $N=2$ it is 6, 4. Each period adds to 10.
3. Points on the circle. For $N=8$ and $n-m=3$, $\sum_{k=0}^{7}e^{j2\pi k\cdot3/8}=0$. For $n-m=8$ it is 8.
4. Practice. A 1 s recording at 8 kHz has 8000 samples, so at least 8000 spectrum samples keep it intact.

Where you’ll meet this

A computer that transforms a recording keeps $N$ spectrum values, and this page says what that choice means: the signal is treated as one period of a repeating signal. The DFT (13.2) names the $N$ values and puts them on a frequency axis in hertz. Circular vs linear convolution (13.4) uses the repeating picture to explain why the ends of a filtered block wrap around. Zero-padding and resolution (15.3) uses the rule $N\ge L$ the other way: it adds zeros to get more spectrum samples.

Reference card