Problem 544023 · medium · Level 05 Advanced Algorithms & Graphs

Tuning a Guitar String with Zero Padding

zero padding · spectrum interpolation · frequency resolution · numpy.fft · peak picking

A tuner app listens to a guitar string for a short moment: N samples at fs samples per second. The bins of an N-point spectrum are fs / N hertz apart, so with 256 samples at 8000 per second the app can only say "187.5 Hz or 218.75 Hz", far too coarse to tune a string to 196 Hz.

Zero padding helps: append zeros to the recording until it has pad_to samples, then transform. The zeros add no new information, but bin k of the longer transform sits at k * fs / pad_to hertz, so the same underlying spectrum is sampled on a finer grid and its peak can be located more precisely. (It does not separate two tones that are closer than about fs / N: that needs a longer recording.)

Write padded_peak(x, fs, pad_to) that returns the pair (coarse, fine) in hertz:

  1. Subtract the mean of x from every sample (the string's sound has no steady part, but the microphone may add an offset).
  2. coarse: the frequency k * fs / N of the bin with the largest magnitude |X[k]| of the N-point DFT, among k = 1, ..., N // 2.
  3. fine: the same with the zero-padded recording of length pad_to: the largest |X[k]| among k = 1, ..., pad_to // 2, at k * fs / pad_to.

The DFT is X[k] = sum over n of x[n] * exp(-2j * pi * k * n / L) for a recording of length L. With pad_to in the thousands a hand-written DFT is too slow, so this problem lets you use numpy: numpy.fft.rfft(v, n=L) pads v with zeros to length L and returns the bins X[0], ..., X[L // 2]; numpy.abs and numpy.argmax do the rest. Press Run with plot(numpy.abs(numpy.fft.rfft(x, n=pad_to))) to see the smooth padded spectrum.

Examples

Input:  x = [math.cos(2 * math.pi * 196 * n / 8000) for n in range(256)], fs = 8000, pad_to = 4096
Output: (187.5, 195.3125)
Explanation: the 256-point bins are 31.25 Hz apart and bin 6 (187.5 Hz) is the closest to 196 Hz.
Padded to 4096, the bins are 1.953 Hz apart and the peak lands at bin 100, 195.3 Hz.

Input:  x = [3 + math.sin(2 * math.pi * 0.9 * n / 10) for n in range(40)], fs = 10, pad_to = 400
Output: (1.0, 0.9)
Explanation: after removing the offset 3, the 0.9 Hz tone falls between the 0.25 Hz bins
(the largest is at 1.0 Hz); padding to 400 gives a 0.025 Hz grid and finds 0.9 Hz.

Constraints

  • 2 <= N <= 4096, N <= pad_to <= 2**17
  • the tests never have two bins with (nearly) equal largest magnitude; answers are compared with a tolerance of 1e-6

Goals

  • Find the strongest frequency of a short recording from its spectrum
  • Append zeros before the transform to sample the same spectrum on a finer grid
  • Use numpy.fft.rfft, which pads for you, for a transform too long to write by hand
Starting Python…