Problem 310491 · easy · Level 03 Linear Management & Searching

How Much Hum Is in the Recording?

discrete Fourier transform · complex numbers · correlation · amplitude

An electric guitar's pickup also catches the hum of the mains wiring. A sound engineer has a recording x of N samples and wants to know how strong one particular wave in it is: the wave that goes through exactly k whole cycles during the recording.

The tool for this is one bin of the discrete Fourier transform (DFT):

X_k = \sum_{n=0}^{N-1} x_n \, e^{-2\pi j k n / N}

Here x_n is sample n and j is the imaginary unit, 1j in Python. The sum over n is a loop over the samples, for instance sum(x[n] * cmath.exp(-2j * cmath.pi * k * n / N) for n in range(N)). Each e^{-2\pi j k n / N} is a unit arrow (a complex number of length 1, real part cos, imaginary part sin of its angle) that turns backwards k times over the recording. Each sample is multiplied by the arrow at its moment, and the products are added. If the recording contains a wave that also turns k times, the products keep pointing the same way and pile up. Any other whole number of cycles, and any constant offset, makes them point all round the circle and cancel out. A wave a\cos(2\pi k n / N + p) gives |X_k| = aN / 2, so its amplitude is

a = \frac{2\,|X_k|}{N}

Write hum_bin(x, k) that returns a tuple (re, im, amplitude): the real and imaginary parts of X[k] and the amplitude. Use cmath.exp, or math.cos and math.sin (e^{-j\theta} = \cos\theta - j\sin\theta). Press Run with plot([hum_bin(x, k)[2] for k in range(1, len(x) // 2)], kind="stem") to see the amplitude of every bin at once.

Examples

Input:  x = [0, 1, 0, -1], k = 1
Output: (0.0, -2.0, 1.0)
Explanation: one cycle of a sine of amplitude 1. The arrows at n = 0..3 are 1, -1j, -1, 1j;
the products are 0, -1j, 0, -1j, adding up to -2j, and 2 * 2 / 4 = 1.

Input:  x = [1, 0, -1, 0, 1, 0, -1, 0], k = 2
Output: (4.0, 0.0, 1.0)

Input:  x = [2, 2, 2, 2, 2, 2], k = 1
Output: (0.0, 0.0, 0.0)
Explanation: a constant voltage has no wave that turns once.

Constraints

  • 1 <= k < N / 2
  • answers are compared with a tolerance of 1e-6; values like 1e-16 for 0 count as correct

Goals

  • Compute one bin of the DFT from its formula
  • See a DFT bin as the signal multiplied by a turning arrow and added up
  • Turn the size of a bin into the amplitude of the wave it measures
Starting Python…