Fourier as a bank of correlators

← A cosine as a sum of two rotations; complex baseband

Why we need a spectrum

Imagine that two signals come into the receiver at the same time. Each sample contains their sum. On a time plot, we see the shape of the total oscillation, but it can be difficult to find the frequencies of the separate components from it.

The spectrum helps to answer two questions: which frequencies are in the signal, and what are the amplitudes of its components?

In the previous lesson, we shifted the frequency of a signal by multiplication with a complex rotation. Now we use the same operation for measurement: we try to cancel the rotation of a selected frequency and see what we get when we add the samples.

A complex sample on the I/Q plane

We start with one complex tone — a signal whose phasor rotates at a constant rate and keeps its length. Each sample of it is a complex number:

On the diagram, this is a vector from the origin to the point $(I[n],Q[n])$. Its length shows the magnitude of the number, and its angle from the positive $I$ axis shows the phase. When we change the index $n$, we look at consecutive samples of one signal.

For our example, we set:

• signal frequency $+2$ kHz;
• sample rate $F_s=8$ kS/s;
• amplitude $1$ and initial phase $0$;
• eight samples, from $n=0$ to $n=7$.

In the interval between samples, the vector turns counterclockwise by

The first samples are:

How to test one frequency

We want to find out if the input signal has a component at the frequency $+2$ kHz. For this, the program makes a reference signal: a complex exponential. Its amplitude is $1$, its initial phase is $0$, and it rotates clockwise: by $-90^\circ$ per sample.

Here it is important to keep apart the analysis frequency $+2$ kHz and the frequency of the reference rotation itself, $-2$ kHz. We need the opposite sign to cancel the rotation of the input signal.

We multiply the samples that have the same index:

where $p[n]$ is a sample of the reference signal and $y[n]$ is the result. This is the same operation that we called a digital mixer. When you multiply complex numbers, their magnitudes multiply and their angles add.

For example, at $n=1$ the angles add like this: $90^\circ+(-90^\circ)=0^\circ$. The result is the number $1$, and its vector points to the right.

All eight output samples are equal to $1$. Thus their sum is $8$. Geometrically, we add eight unit vectors: we move the start of each next vector to the end of the previous one. The result is a vector of length $8$.

A correlator does exactly these two actions: it multiplies the input samples by the reference samples, then adds the results.

What we get at a different analysis frequency

Now we test $+1$ kHz. The reference rotation is $-45^\circ$ per sample, and the input rotation is $+90^\circ$. After the multiplication, a rotation of $+45^\circ$ remains, which is the frequency $+1$ kHz.

The eight output samples have these angles:

n:      0    1    2     3     4     5     6     7
angle:  0°  45°  90°  135°  180°  225°  270°  315°

These vectors point in directions spread evenly around the circle. Each vector has an opposite one: for example, $0^\circ$ and $180^\circ$. When we add them, they cancel each other. If you put them one after another, you get a closed octagon, and the sum is zero.

In this example, the sum is exactly zero because of the frequencies and the number of samples that we selected. An arbitrary frequency that does not match does not have to give a zero sum. If the cancellation is not complete, part of the result remains; later we will study this as spectral leakage.

Start with the analysis frequency $+2$ kHz and change the sample index. The top row shows the input vector, the reference vector and the result of their multiplication. The input and the reference change direction, but the result is $1$ each time.

Then select $+1$ kHz. Now the direction of the result vector also changes. The bottom left shows all eight results from a common origin; the bottom right shows their consecutive addition. When the frequencies match, the eight vectors on the left lie on top of each other, so you see only one.

The same operation in formulas

For a complex tone with frequency $f_0$, amplitude $A$ and initial phase $\phi$:

To test the frequency $f_p$, we make a reference signal:

When we multiply, the angles add, so the difference of the frequencies remains:

At $f_p=f_0$, each result is the same number $Ae^{j\phi}$. Its vector points to the right only when the initial phase is zero, as in our example. With a different phase, all output vectors point at a different common angle. In both cases, the length of the sum is $NA$, where $N$ is the number of samples.

The output of one correlator

In the general case, we write the input sequence as $x[n]$: it can be one tone or a sum of several tones, a real or a complex signal. One formula gives the multiplication and the addition:

The symbol $\sum$ means “add the results for all $n$ from $0$ to $N-1$”. The output is one complex number $X(f_p)$.

For a single complex tone at the analysis frequency:

• the magnitude $|X(f_p)|$ is $NA$, so division by $N$ gives the amplitude $A$;
• the angle of this number is the initial phase of the tone.

For a mix of signals, the correlator adds the contributions of all components. In our examples, we selected the frequencies so that the components that do not match give a zero contribution. With other frequencies and record lengths, the measurement can be less accurate.

From one correlator to the DFT

To make a spectrum, we repeat the measurement for a set of frequencies. The DFT — the discrete Fourier transform — uses $N$ analysis frequencies with the step

For example, for eight samples at $F_s=8$ kS/s, the step is $1$ kHz. When we put the negative frequencies on the left, the set is:

−4, −3, −2, −1, 0, +1, +2, +3 kHz

Here we wrote the Nyquist frequency as $-4$ kHz. We do not add the value $+4$ kHz separately: on the sample grid, these two rotations are the same.

You can write each analysis frequency as $f_k=kF_s/N$. When we put it into the previous formula, we get:

In this example, $k$ goes from $-4$ to $3$. Indices that differ by $N$ give the same reference samples: the added angle is an integer number of turns, $2\pi n$. Thus you can also number the results from $0$ to $N-1$, as NumPy does. The output is eight complex numbers, one for each analysis frequency. Their magnitudes give the magnitude spectrum.

The FFT is a fast algorithm that calculates the same DFT. The function np.fft.fft() returns the frequencies in a different order: first zero and the positive frequencies, then the negative ones. In the lab, np.fft.fftshift() changes the order of the results for a plot with the negative frequencies on the left. In the next lesson, we will study the indices and calculate a short DFT in detail.

Why a cosine with amplitude 1 gives two peaks of 0.5

In the previous lesson, we wrote a real cosine as a sum of two rotations in opposite directions:

The correlator at $+f$ picks up one of these rotations, and the correlator at $-f$ picks up the other. The amplitude of each is $A/2$.

The lab plot shows $|X[k]|/N$: the magnitude of the DFT result divided by the number of samples. Thus, for frequencies that are exactly on the DFT grid, we get:

This is a two-sided magnitude spectrum. Its peaks show the amplitudes of the complex rotations that add up to the original cosines.

You can also make a single-sided magnitude spectrum of a real signal: keep the positive frequencies and double their values. Then in our example we see $1$ and $0.5$. We do not double zero frequency and the Nyquist frequency, because they do not have a separate paired component. In this lesson, we keep both sides to keep the link with the two directions of rotation.

Python lab

The script combines two experiments. Run it from the project directory:

uv run labs/03/01-frequency-probe.py --show

The top row tests one complex tone. Here the parameters are different from the interactive diagram: input frequency $+1$ kHz, number of samples $N=32$, sample rate $8$ kS/s.

• The left plot shows $I$ and $Q$ of the input samples in time.
• The center plot shows the consecutive addition of the results for the analysis frequency $+1$ kHz. All 32 results are equal to $1$, and the sum is $32$.
• The right plot shows the same addition for the analysis frequency $+1.5$ kHz. The remaining frequency is $-0.5$ kHz. The sum is near zero; the small error comes from floating-point calculation.

The bottom row analyzes the sum of two real cosines:

On the plot Two real cosines and their sum, dashed lines show the original cosines. The black line is their sum, calculated on a dense time grid to draw a continuous curve. The blue dots are 32 samples of this sum at $F_s=8$ kS/s. These are the values that go into the DFT.

The bottom right plot is the two-sided spectrum of the sum. The step of the analysis frequencies is $8000/32=250$ Hz. Both original frequencies are exactly on this grid. Thus you see four peaks: at $\pm1$ kHz with height $0.5$ and at $\pm2$ kHz with height $0.25$.

The program calculates the DFT directly: for each frequency, it multiplies the samples by the reference signal and adds them. Then it compares the result with np.fft.fft().

Self-check

For questions 1–3, we use a complex tone of $+2$ kHz with amplitude $1$ and initial phase $0$. The sample rate is $8$ kS/s. We take eight samples, $n=0,\ldots,7$. The reference signal has amplitude $1$, initial phase $0$, and a frequency opposite to the analysis frequency. We write the result of the multiplication as $y[n]$.