Problem 343679 · hard · Level 03 Linear Management & Searching

Leakage in an Engine Recording

spectral leakage · Hann window · DFT · energy · windowing

A mechanic records the sound of an engine to look for a weak rattle next to the strong engine tone. The DFT treats the recording as one period of an endlessly repeating signal. If the engine tone makes a whole number of cycles in the recording, the repeat is seamless and the tone lands in one bin. If not, the repeat has a jump where the end meets the start, and the tone's energy leaks into every bin, enough to bury a weak rattle.

The usual cure is a window: multiply the recording by a curve that fades it in and out, so there is no jump. The Hann window for N samples is

w[n] = 0.5 - 0.5 * cos(2 * pi * n / N)        for n = 0 .. N-1

which is 0 at the start, 1 in the middle and almost 0 again at the end.

Measure the leakage of a recording x (with N samples) like this:

  1. For every bin k = 1, 2, ..., N // 2, compute the energy |X[k]|², where X[k] is the sum of x[n] * exp(-2j * pi * k * n / N) over n (bin 0, the offset, is left out).
  2. Find the peak bin, the one with the largest energy among them.
  3. The leakage is the percentage of the total energy of these bins that lies in bins more than 2 bins away from the peak: 100 * far / total.

Write leakage(x) that returns a pair: the leakage of x itself, and the leakage of the windowed recording [x[n] * w[n] for n in range(N)]. Press Run with plot(...) of the bin energies in decibels, 10 * log10(|X[k]|²), with and without the window to see the skirt of leaked energy shrink.

Examples

Input:  x = [cos(2 * pi * 4 * n / 32) for n in range(32)]
Output: (0.0, 0.0)
Explanation: exactly 4 cycles in the recording; all the energy is in bin 4, with or without
the window (the window spreads it only over bins 3, 4 and 5).

Input:  x = [cos(2 * pi * 4.3 * n / 32) for n in range(32)]
Output: (3.339741893903544, 0.021900869423165416)
Explanation: 4.3 cycles do not fit. Without the window 3.3 % of the energy sits more than
2 bins from the peak; with it, 0.02 %, about 150 times less.

Constraints

  • 8 <= N <= 256; the recordings are tones, so no recording is all zeros, with or without the window
  • the two strongest bins are never nearly equal (no tone sits half-way between two bins)
  • answers are compared with a tolerance of 1e-6

Goals

  • See why a tone that does not fit a whole number of cycles spreads over many bins
  • Measure leakage as the share of spectrum energy far from the peak
  • Apply a Hann window and show that it keeps the energy close to the peak
Starting Python…