Problem 589656 · easy · Level 05 Advanced Algorithms & Graphs

How Late Is the Smoothed Pulse?

FIR filter · group delay · linear phase · symmetric weights · complex numbers

A fingertip pulse sensor records the light passing through a finger, fs samples per second, and the firmware smooths it with an FIR filter of N weights b: y[n] = b[0] * x[n] + b[1] * x[n-1] + ... + b[N-1] * x[n-N+1]. Smoothing makes the output late: each output is a weighted average of past inputs. A heart-rate alarm needs to know how late, and whether every part of the beat (its slow swell and its quick notch) is late by the same amount; if not, the shape of the beat is bent.

The group delay at frequency f says how many samples late a wave near f, and the bump it carries, comes out. With w = 2 * pi * f / fs:

B = sum over k of  b[k] * exp(-1j * w * k)          (the filter's response at f)
C = sum over k of  k * b[k] * exp(-1j * w * k)      (the same, each weight times its age k)
delay = (C / B).real                                 (in samples)

At 0 Hz all the arrows point the same way and this is sum(k * b[k]) / sum(b): the centre of mass of the weights, the average age of the samples the filter mixes. When the weights are symmetric (b[k] == b[N-1-k]), the delay is exactly (N - 1) / 2 at every frequency, so every part of the beat moves together and the shape is kept: such a filter is called linear phase, and its delay can be undone by a simple shift.

Write group_delays(b, fs, freqs) that returns a pair:

  1. the list of group delays in milliseconds (delay / fs * 1000), one per frequency in freqs,
  2. True if the weights are symmetric (every abs(b[k] - b[N-1-k]) <= 1e-12), else False.

Press Run with plot(grid, group_delays(b, fs, grid)[0]) for a list grid of frequencies to see how the delay of a lopsided filter changes with frequency.

Examples

Input:  b = [0.25, 0.5, 0.25], fs = 100, freqs = [0, 10, 25]
Output: ([10.0, 10.0, 10.0], True)
Explanation: symmetric weights, N = 3: one sample late at every frequency, 10 ms at 100 Hz.

Input:  b = [0.5, 0.3, 0.2], fs = 50, freqs = [0, 12.5, 25]
Output: ([14.0, -3.3333333333333326, 5.000000000000001], False)
Explanation: at 0 Hz the centre of mass is (0 * 0.5 + 1 * 0.3 + 2 * 0.2) / 1 = 0.7 samples, 14 ms.
At 12.5 Hz (w = pi / 2), B = 0.3 - 0.3j and C = -0.4 - 0.3j, so the delay is -0.167 samples:
a wave there even comes out slightly early. Different parts of the beat are shifted differently.

Constraints

  • 1 <= N <= 200; 1 <= len(freqs) <= 50, each 0 <= f <= fs / 2
  • the tests avoid frequencies where |B| is below 1e-3; answers are compared with a tolerance of 1e-6

Goals

  • Compute the group delay of an FIR filter at a frequency from its weights
  • See that symmetric weights delay every frequency by the same (N - 1) / 2 samples
  • Read the delay at 0 Hz as the centre of mass of the weights
Starting Python…