Problem 292936 · hard · Level 02 Linear Data Structures

The Microphone Chain's Fingerprint

cascade · convolution · impulse response · steady-state gain · recursive filter

A podcast studio's signal passes through a chain of stages: the microphone's preamp, a delay that lines it up with a second microphone, a filter, a feedback stage. Each stage is linear and time-invariant, and so is the whole chain: its own impulse response h is the chain's fingerprint. Because each stage only reshapes what it receives, the chain's impulse response is the convolution of the stages' impulse responses, and the order of the stages does not change it.

The stages, each a pair, with input x and output y, starting from silence (every value before sample 0 is 0):

  • ("gain", g): y[k] = g * x[k]. Steady gain g.
  • ("delay", d): y[k] = x[k - d], a whole number d >= 0 of samples. Steady gain 1.
  • ("fir", b): y[k] = b[0]*x[k] + b[1]*x[k-1] + .... Steady gain sum(b).
  • ("loop", a): y[k] = a * y[k-1] + x[k]. Steady gain 1 / (1 - a) when |a| < 1.

The steady gain is where the step response settles: hold the input at 1 for ever, and the output ends up at the steady gain (it is the sum of the impulse response, as on the induction hob). For a chain, the steady gains multiply.

Write cascade(stages, n) that returns (h, steady): h is the list of the first n samples of the chain's impulse response (the signal first enters stages[0]), and steady is the chain's steady gain, or None if any "loop" stage has |a| >= 1 (the lab quotes no steady gain then). An empty chain passes the signal unchanged. Press Run with plot(cascade(stages, 40)[0], kind="stem") to see the fingerprint.

Examples

Input:  stages = [("gain", 2), ("delay", 1), ("fir", [1, 0.5])], n = 5
Output: ([0.0, 2.0, 1.0, 0.0, 0.0], 3.0)
Explanation: the impulse becomes [2, 0, ...], then [0, 2, 0, ...], then the FIR adds half
of each sample to the next. Steady gain 2 * 1 * 1.5 = 3.

Input:  stages = [("loop", 0.5), ("fir", [1, -0.5])], n = 4
Output: ([1.0, 0.0, 0.0, 0.0], 1.0)
Explanation: the loop gives 1, 0.5, 0.25, 0.125; the FIR computes h[k] - 0.5 * h[k-1],
which undoes the loop exactly. Steady gain 2 * 0.5 = 1.

Constraints

  • answers are compared with a tolerance of 1e-6; a list [h, steady] is accepted in place of the tuple

Goals

  • Find the impulse response of a chain of LTI stages by passing an impulse through every stage
  • Know that the chain's impulse response is the convolution of the stages' responses, in any order
  • Combine the stages' steady-state gains by multiplying them
Starting Python…