Problem 323924 · hard · Level 03 Linear Management & Searching

Cleaning a Heart-Rate Signal in the Frequency Domain

inverse DFT · negative frequencies · filtering · complex numbers · reconstruction

A fitness watch measures blood flow with a light sensor. The pulse is a slow wave (around 1 to 3 Hz), but the reading also carries fast flicker from room lights and electronics. One way to remove it: take the DFT, set the bins of the unwanted frequencies to zero, and transform back.

The way back is the inverse DFT. It adds up the arrows of every bin, now turning forwards, and divides by N:

x[n] = (1 / N) * sum over k = 0 .. N-1 of  X[k] * exp(2j * pi * k * n / N)

and it gives back exactly the samples the DFT started from (up to rounding). Which frequency does each bin hold? For k <= N / 2 it is k * fs / N. The bins above N / 2 are the negative frequencies: bin k is the arrow turning backwards at (k - N) * fs / N hertz. A real signal needs both arrows of each pair (a cosine is half an arrow turning forwards plus half an arrow turning backwards), which is why the mirror bins exist.

Write clean_signal(x, fs, cutoff) that:

  1. computes the DFT X[k] of x for every k from 0 to N - 1,
  2. sets to 0 every bin whose frequency, as defined above, is greater than cutoff in size (abs(frequency) > cutoff), so both arrows of a removed wave go,
  3. returns the list of the real parts of the inverse DFT: the cleaned signal, N samples.

With cutoff at least fs / 2 nothing is removed, so the result is x itself: a good test of your inverse. Press Run with plot(x, label="raw") and plot(clean_signal(x, fs, 3), label="clean") to compare.

Examples

Input:  x = [4, 1, 2, 1, 4, 1, 2, 1], fs = 8, cutoff = 3
Output: [3.0, 2.0, 1.0, 2.0, 3.0, 2.0, 1.0, 2.0]
Explanation: x is 2 + cos(2 * pi * 2 * t) + cos(2 * pi * 4 * t). Bin 4 (4 Hz) is removed;
bins 2 and 6 (+2 Hz and -2 Hz) and bin 0 stay.

Input:  x = [4, 1, 2, 1, 4, 1, 2, 1], fs = 8, cutoff = 1
Output: [2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0]

Input:  x = [4, 1, 2, 1, 4, 1, 2, 1], fs = 8, cutoff = 4
Output: [4.0, 1.0, 2.0, 1.0, 4.0, 1.0, 2.0, 1.0]

Constraints

  • 1 <= N <= 256; cutoff never equals the frequency of a bin exactly
  • answers are compared with a tolerance of 1e-6

Goals

  • Rebuild a signal from its DFT with the inverse transform
  • Recognise the upper half of the bins as negative frequencies
  • Remove the fast part of a signal by zeroing bins, keeping the result real
Starting Python…