This exercise covers several properties of the DFT. It has four parts; this post covers the first one, the spectrum of two sinusoids.
While doing this exercise I was writing a tuner. A tuner does the same thing as this part of the exercise, reading a peak accurately from a spectrum, so the examples are built around the 440 Hz concert pitch.
Reading the frequency of one sinusoid
First generate one second of a 440 Hz cosine with gen_sine from E2, at fs = 44100. E2 described a cosine as the horizontal position of a point going round a circle at constant speed; 440 Hz means the point goes round 440 times per second.
The animation slows the rotation down a few hundred times. On the left is the point on the circle, on the right the wave it draws, with real time on the horizontal axis: 4.4 turns in 10 ms. The button plays the 440 Hz tone at full speed.
A tuner does not analyse the whole recording; it takes a short slice at a time, called a frame. Take the first 2048 samples, about 46 ms, compute the FFT, find the bin with the largest magnitude, and convert it to a frequency with the formula from E2, f = k · fs / M.
The figure shows only the region around 440 Hz. The dashed orange line is the true frequency, the blue bars are the magnitudes of the bins, and the ticks on the line below mark where the bins are. With M = 2048 the largest magnitude is at bin 20, which converts to 20 × 44100 / 2048 = 430.66 Hz.
The interval between two neighbouring semitones is divided into 100 parts, and one part is a cent. 430.66 Hz is 37 cents away from 440 Hz. The ear can tell a difference of about 5 cents, so this reading is unusable for a tuner.
Why the reading is 430.66 Hz
The first reason is that the bins are too far apart. With M = 2048, neighbouring bins are 44100 / 2048 = 21.5 Hz apart. Bin 20 is 430.66 Hz and bin 21 is 452.2 Hz; 440 Hz lies between them and no bin points at it. Around 440 Hz, 21.5 Hz is about 85 cents, close to a semitone.
The second reason is leakage. One turn of a 440 Hz wave takes 44100 / 440 = 100.2 samples, so 2048 samples hold 20.43 turns, not a whole number. The last section of E2 explained that when a frequency does not land on a bin, the energy that should be concentrated in one bin spreads to the neighbouring bins. In the figure, the tallest bar is shorter than it should be and a row of small bars extends on both sides.
The buttons above switch between a few settings. With the frequency set to 430.66 Hz, which is bin 20 itself, 2048 samples hold exactly 20 turns, the spectrum has a single bar and the error is 0. With M = 8192 the bin spacing shrinks to 5.4 Hz and the error drops to 5.6 cents, but the small bars remain, because 81.7 turns is still not a whole number. With M = 2205 the frame holds exactly 22 turns and there is a single bar again.
A longer frame helps, but the error can still be half a bin, and a longer frame means a longer wait for each reading: 8192 samples is 186 ms.
The seam of a frame
Every reference wave of the DFT makes a whole number of turns in M samples, so the signal the DFT sees is the frame joined end to beginning and repeated. A wave that makes 20.43 turns in the frame does not join up when repeated; at the seam there is a jump that is not in the original signal.
Below, the 2048-sample frame is repeated end to end, next to a 2205-sample frame that holds exactly 22 turns.
The waveform flows to the left, and each seam is marked with a dashed line. The upper wave jumps upward at the seam; the lower wave joins smoothly.
Both loops can be played. The first has a click 21 times per second, which is the seam. The second is a continuous 440 Hz.
The least common multiple for two sinusoids
The exercise gives two frequencies f1 and f2, both of which divide fs, and asks for the smallest frame length M such that the positive half of the M-point DFT has only two non-zero values.
In the two examples above with zero error, the frame held a whole number of turns. One turn of a frequency takes fs / f samples; this number is its period, in samples. If M is a multiple of the period, the frequency makes a whole number of turns in the frame and the spectrum has a value in one bin only. For both frequencies to satisfy this, M has to be a multiple of both periods, and the smallest such M is their least common multiple.
The exercise’s example is fs = 10000, f1 = 80 Hz, f2 = 200 Hz. The period of 80 Hz is 125 samples and the period of 200 Hz is 50 samples. The two frequencies are like two people running laps on a track, one taking 125 steps per lap and the other 50. They start together, and they are next both at the start at step 250.
- At step 50 the fast runner is at the start, and the slow one has done 0.4 of a lap;
- At step 125 the slow runner is at the start, and the fast one has done 2.5 laps;
- At step 250 one has done 5 laps and the other 2, and both are at the start.
On the left are the two tracks, on the right the two waves; the dashed black line is the end of the frame, moving one sample to the right per step, and below is the spectrum of the first M samples. The animation pauses briefly at 50, 125 and 250, and the slider can be dragged. At M = 250 both runners are at the start and the spectrum has only the two bars at 80 Hz and 200 Hz.
Implementation
When both periods are integers, the least common multiple is their product divided by their greatest common divisor, which math.gcd computes directly. The greatest common divisor of 125 and 50 is 25, and 125 × 50 / 25 = 250.
With M known, compute the FFT of the first M samples, keep the positive half, i.e. the first M/2 + 1 values, and convert to dB:
from scipy.fftpack import fft
from math import gcd
import numpy as np
def minimize_energy_spread_dft(x, fs, f1, f2):
T1 = int(fs / f1)
T2 = int(fs / f2)
M = T1 * T2 // gcd(T1, T2)
X = fft(x[:M])
return 20 * np.log10(np.abs(X[:M // 2 + 1]))
dB is 20 times the common logarithm of the magnitude. A magnitude of 125 is 20 × log10(125) ≈ 42 dB, and a magnitude of 0.000001 is −120 dB.
The exercise gives two test cases. The first is fs = 10000 with 80 Hz and 200 Hz: M = 250, 126 values are returned, and the non-zero ones are bins 2 and 5, since 2 × 10000 / 250 = 80 and 5 × 10000 / 250 = 200. The second is fs = 48000 with 300 Hz and 800 Hz: M = 480, 241 values are returned, and the non-zero ones are bins 3 and 8.
The two bars are at about 42 dB. The other bins should be exactly 0, but floating-point arithmetic leaves residues of the order of 1e−15, which is about −300 dB, so the exercise treats anything below −120 dB as zero.
Summary
- Neighbouring bins are fs / M Hz apart; when a frequency lies between two bins, the reading can be off by up to half a bin;
- When the frame holds a whole number of turns, the spectrum has a single bar; otherwise the energy spreads to the neighbouring bins, and the seam where the frame wraps around can be heard;
- For two sinusoids to both make a whole number of turns, the frame length is the least common multiple of their two periods.
Exercise source: E3-Fourier-properties.ipynb