Problem 264273 · medium · Level 02 Linear Data Structures

Will the Stage Monitor Howl?

BIBO stability · FIR filter · recursive filter · feedback · bounds

A system is BIBO stable (bounded input, bounded output) if every input that stays within some limit M (|x[k]| <= M for all k) gives an output that also stays within some limit. On a stage, an unstable loop is the howl you hear when a microphone picks up its own monitor speaker.

A sound desk runs two kinds of effect, both starting from silence (every value before sample 0 is 0):

  • "fir", coefficients b: y[k] = b[0]*x[k] + b[1]*x[k-1] + ... (an FIR filter). Each output is a fixed weighted sum of at most len(b) inputs, so |y[k]| <= M * (|b[0]| + |b[1]| + ...): always stable, with bound M * sum(|b|).
  • "loop", a feedback gain a: y[k] = a * y[k-1] + x[k] (a fraction a of the last output comes back). Its impulse response is 1, a, a*a, a**3, ...; when |a| < 1 these shrink, and |y[k]| <= M * (1 + |a| + |a|**2 + ...) = M / (1 - |a|). When |a| >= 1 it is unstable: some bounded input (all ones for a >= 1, alternating 1, -1, 1, ... for a <= -1) makes the output grow without limit.

The desk's test plays a bounded input x through the effect. Write stability(kind, coef, x) that returns (stable, peak, bound):

  • stable: whether the effect is BIBO stable (decided from coef, not from this one test);
  • peak: the largest |y[k]| over k = 0, ..., len(x) - 1 for this input;
  • bound: the guaranteed limit for any input as large as this one, with M = max(|x|), or None if the effect is unstable.

Press Run with plot(...) of the outputs for a = 0.9 and a = 1.05 to see one settle and the other run away.

Examples

Input:  kind = "loop", coef = 0.5, x = [1, 1, 1, 1]
Output: (True, 1.875, 2.0)
Explanation: y = 1, 1.5, 1.75, 1.875, creeping up to 1 / (1 - 0.5) = 2.

Input:  kind = "fir", coef = [0.5, -0.5, 0.25], x = [1, -1, 1, -1]
Output: (True, 1.25, 1.25)
Explanation: y = 0.5, -1.0, 1.25, -1.25. The bound is 1 * (0.5 + 0.5 + 0.25) = 1.25,
and this input, matching the coefficients' signs, reaches it.

Input:  kind = "loop", coef = -1, x = [1, 1, 1, 1]
Output: (False, 1.0, None)
Explanation: y = 1, 0, 1, 0 stays small, but the input 1, -1, 1, -1 would give 1, -2, 3, -4, ...

Constraints

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

Goals

  • Know that an FIR filter is always BIBO stable, with output bound M * sum(|b|)
  • Know that y[k] = a * y[k-1] + x[k] is BIBO stable exactly when |a| < 1, with bound M / (1 - |a|)
  • See that one bounded test input can stay bounded even through an unstable system
Starting Python…