Problem 410413 · medium · Level 04 Non-Linear Data Structures

The Subwoofer Filter's Bode Table

frequency response · unit circle · gain · phase · decibels · Bode plot

A subwoofer must only play the low notes, so its amplifier passes the music through a digital low-pass filter H(z) = B(z) / A(z) (coefficient lists b and a in powers of z^-1). In Level 3 you computed the frequency response of an FIR filter. A recursive filter works the same way: a sine wave of frequency f hertz, sampled at fs hertz, turns by w = 2 * pi * f / fs radians per sample, and each delay z^-1 multiplies it by exp(-1j * w). So its response is the transfer function evaluated on the unit circle:

w = 2 * pi * f / fs
z = exp(1j * w)            (so z^-1 = exp(-1j * w))
H = B(z) / A(z)

The gain |H| scales the wave's amplitude; in decibels, 20 * log10(|H|). The phase cmath.phase(H), converted to degrees with math.degrees, is how far the output wave is shifted: a negative phase means the output lags behind the input. Report (-120.0, 0.0) when |H| < 1e-6 (a perfect null has no phase). The table of both against frequency, drawn with a logarithmic frequency axis, is a Bode plot, the standard picture of a filter.

Write bode_table(b, a, fs, freqs) that returns a list with one pair (gain_db, phase_deg) per frequency in freqs, in order. Press Run with plot(freqs, [g for g, p in bode_table(b, a, fs, freqs)], logx=True) over frequencies such as [10 * 1.2 ** i for i in range(22)] (10 Hz to 460 Hz for fs = 1000) to draw the Bode plot.

Examples

Input:  b = [1], a = [1, -0.5], fs = 8, freqs = [0, 2]
Output: [(6.020599913279624, 0.0), (-0.9691001300805633, -26.56505117707799)]
Explanation: at 0 Hz, H = 1 / (1 - 0.5) = 2, which is +6.02 dB. At 2 Hz, w = pi / 2,
z^-1 = -1j, H = 1 / (1 + 0.5j) = 0.8 - 0.4j: gain 0.894 (-0.97 dB), lagging by 26.6 degrees.

Input:  b = [0.0675, 0.135, 0.0675], a = [1, -1.143, 0.4128], fs = 1000, freqs = [0, 100, 250]
Output: [(0.006436376462038894, 0.0), (-3.004566354838601, -90.00345127558515),
         (-19.571460405789864, -152.80881216072058)]
Explanation: the subwoofer filter passes 0 Hz, is 3 dB down at its cutoff of 100 Hz
(with a quarter-cycle lag), and 19.6 dB down at 250 Hz.

Constraints

  • 0 <= f < fs / 2 for every frequency; the filter has no pole on the unit circle
  • phases lie between -180 and 180 degrees, as cmath.phase gives them; the tests never ask for a frequency where H is a negative real number (a phase of exactly 180 degrees)
  • answers are compared with a tolerance of 1e-6; the tests never have a gain close to 1e-6 unless it is a true null

Goals

  • Evaluate a transfer function on the unit circle, z = exp(j w), to get its frequency response
  • Report the gain in decibels and the phase shift in degrees
  • Read a cutoff frequency as the point where the gain is 3 dB down
Starting Python…