Problem 398464 · medium · Level 03 Linear Management & Searching

What the Drone's Sensor Filter Lets Through

FIR filter · frequency response · gain · decibels · complex numbers

A drone's flight controller smooths its gyroscope readings with an FIR filter: each output is a weighted sum of the latest inputs, y[n] = b[0] * x[n] + b[1] * x[n-1] + ... + b[M-1] * x[n-M+1], with fixed weights b (the moving average of Level 1 is the case where all weights are 1 / M). The motors shake the frame at a known frequency, and the designer wants to know how much of that shaking gets through.

Feed the filter a sine wave of frequency f hertz at fs samples per second. What comes out is a sine of the same frequency, scaled and shifted by the filter's frequency response

w = 2 * pi * f / fs                                   (radians per sample)
H = sum over k = 0 .. M-1 of  b[k] * exp(-1j * w * k)

Each weight multiplies an arrow turned back by k samples of the wave; where the arrows cancel, the wave is removed. The gain |H| is the factor by which the wave's amplitude is multiplied, and in decibels it is 20 * log10(|H|) (an amplitude ratio). A gain of exactly 0 would be minus infinity decibels, so: if the gain is below 1e-6, report -120.0 dB instead.

Write fir_response(b, fs, freqs) that returns a list with one pair (gain, gain_db) for each frequency in freqs, in order. Press Run with plot(fs_list, [g for g, d in fir_response(b, fs, fs_list)]) over a list of frequencies fs_list to see the whole response.

Examples

Input:  b = [0.25, 0.25, 0.25, 0.25], fs = 100, freqs = [0, 12.5, 25]
Output: [(1.0, 0.0), (0.6532814824381883, -3.6979930382208988), (0.0, -120.0)]
Explanation: a four-sample average passes a constant unchanged, weakens 12.5 Hz to 65 %,
and removes 25 Hz completely: four samples span exactly one cycle, so they average to 0.

Input:  b = [0.5, -0.5], fs = 1000, freqs = [0, 250]
Output: [(0.0, -120.0), (0.7071067811865475, -3.0102999566398125)]
Explanation: the difference of neighbours removes a constant and passes faster waves.

Constraints

  • answers are compared with a tolerance of 1e-6; a gain like 4e-17 counts as 0.0
  • the tests never have a gain close to the 1e-6 floor unless it is a true null

Goals

  • Compute the frequency response H of an FIR filter at a given frequency
  • Read |H| as the factor by which a sine wave of that frequency is scaled
  • Express the gain in decibels, with a floor for a perfect null
Starting Python…