Problem 418091 · easy · Level 04 Non-Linear Data Structures

Two Echo Units, Side by Side and in a Row

polynomials · coefficient lists · convolution · z-transform · FIR filter

A guitarist has two small echo pedals. Each one is an FIR filter: pedal p computes y[k] = p[0] * x[k] + p[1] * x[k-1] + p[2] * x[k-2] + .... From this level on we write such a filter as a polynomial. Let the symbol z^-1 stand for "delay by one sample", so z^-2 is a delay of two samples, and so on. The pedal is then

P(z) = p[0] + p[1] * z^-1 + p[2] * z^-2 + ...

and its list of weights p is exactly the polynomial's coefficient list, constant term first. This polynomial is the pedal's transfer function. Two ways of connecting the pedals are now plain algebra:

  • side by side (parallel: the same guitar signal goes into both and their outputs are added): P(z) + Q(z). Add the coefficients of equal powers; where one list is shorter, its missing coefficients are 0.
  • in a row (series: the output of p goes into q): P(z) * Q(z). Every term p[i] * z^-i times every term q[j] * z^-j gives p[i] * q[j] * z^-(i+j), so coefficient k of the product is the sum of p[i] * q[j] over all i + j = k. This is the convolution of Level 2: a delay of i followed by a delay of j is a delay of i + j.

Write combine(p, q) that returns the pair (parallel, series) of coefficient lists. parallel has max(len(p), len(q)) entries and series has len(p) + len(q) - 1. Keep every coefficient, including zeros at the end.

Examples

Input:  p = [1, 0.5], q = [1, 0, 0.25]
Output: ([2, 0.5, 0.25], [1, 0.5, 0.25, 0.125])
Explanation: (1 + 0.5 z^-1) + (1 + 0.25 z^-2) = 2 + 0.5 z^-1 + 0.25 z^-2.
(1 + 0.5 z^-1)(1 + 0.25 z^-2) = 1 + 0.5 z^-1 + 0.25 z^-2 + 0.125 z^-3.

Input:  p = [2], q = [0, 1]
Output: ([2, 1], [0, 2])
Explanation: a gain of 2 next to a one-sample delay; and a gain of 2 followed by the delay.

Constraints

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

Goals

  • Read a list of filter weights as a polynomial in the one-sample delay z^-1
  • Add two polynomials coefficient by coefficient, padding the shorter one with zeros
  • Multiply two polynomials, and recognise the product as the convolution of their lists
Starting Python…