Deconvolution and Polynomial division

Question

I found this comment inside MATLAB's deconv.m function

Deconvolution and polynomial division are the same operations as a digital filter's impulse response $B(z)/A(z)$.

What does this statement mean?

Does this mean that one can recover the original signal, $x[n]$, given an impulse response $h[n]$ and output $y[n]$? If so, how?

Is it correct that if I subject an impulse signal $\delta[n]$ as input to a filter with the coefficients of $y[n]$ as the denominator and the coefficients of $h[n]$ as numerator I will get the original $x[n]$?

Answer 1

In addition to the answer from Matt L., I want to emphasize the fact why the comment mentions the polynomial division. Consider to finite-length sequences $h[n]$ and $x[n]$, with length $N$ (one sequence can be zero-padded to length $N$).

Now, look at the convolution of both:

$$y[n]=h[n]*x[n]=\sum_{n'=0}^{N-1}h[n']x[n-n']$$

As an example, consider the two sequences $h[n]=[1, 2, 3]$ and $x[n]=[4, 6, 5]$. Their convolution is (in Matlab)

>> conv([1 2 3], [4 6 5])

ans =

     4    14    29    28    15

Now, consider the product of the two polynomials $h(x)=1+2x+3x^2$ and $x(x)=4+6x+5x^2$ (in Mathematica):

Expand[(1 + 2 x + 3 x^2) (4 + 6 x + 5 x^2)]
>>> 4+14 x+29 x^2+28 x^3+15 x^4

As you can see, the coefficients of the polynomial of the product are equal to the values of the convolution of both sequences.

So, now to get $x[n]$ from $y[n]$, you need to perform the polynomial division of $y(x)/h(x)$:

PolynomialQuotient[4 + 14 x + 29 x^2 + 28 x^3 + 15 x^4, (1 + 2*x + 3*x^2), x]
>>> 4+6 x+5 x^2

Hence, the coefficients of the polynomial yield the original sequence.

This technique can be extended to infinite sequences.

To get the connection to the Z-Transform here: The Z-Transform of the finite sequences $x[n]$ and $h[n]$ are given by

$$H(z)=1+2z^{-1}+3z^{-2}\\ X(z)=4+6z^{-1}+5z^{-2}$$

And the Z-Transform of the output $y[n]$ is given by

$$Y(z)=H(z)X(z).$$

Here, you again have the polynomial multiplication. Also, here it becomes even easier to spot, why it also works with infinite sequences: Then both $H(z)$ and $X(z)$ become fractions of polynomials, but the principle of the polynomial multipication remains.

Answer 2

For finite length sequences that's indeed easily possible. The convolution of two sequences $x[n]$ and $h[n]$

$$y[n]=x[n]\star h[n]\tag{1}$$

corresponds to multiplication of their $\mathcal{Z}$-transforms:

$$Y(z)=X(z)H(z)\tag{2}$$

from which

$$X(z)=\frac{Y(z)}{H(z)}\tag{3}$$

follows. Consequently, $x[n]$ can be obtained by computing the impulse response of a recursive filter with numerator polynomial $Y(z)$ and denominator polynomial $H(z)$. Note that this recursive filter is actually an FIR filter (due to pole/zero cancellation), because, obviously, its impulse response $x[n]$ is of finite length.

This little Matlab/Octave example should help clarify this:

x=[1,2,3,4,5];
h=[5,4,3,2,1];
y=conv(x,h);
x2=filter(y,h,[1,zeros(1,4)])
x2 =

   1.0000   2.0000   3.0000   4.0000   5.0000

Answer 3

If you "invert a deconvolution", you get a convolution. Looking a Matlab convolution conv you can read the one-liner:

Convolution and polynomial multiplication

So they are (almost) the same.

To get the idea, let us start from the standard multiplication, just forgetting about the carry for the moment. If you multiply 123 by 456.

To get the "units" (carry-free, remember), your only option is to multiply units ($3\times 6$). To get tens, you can now multiply tens by units; two options: tens from 123, units from 456, and units from 123, tens from 456. To get hundreds, you can multiply hundreds by units (two options) and tens by tens (one option). At each step, the sum of couples of affected indices is constant, and this sum grows by one unit as you move to the left.

Polynomial multiplication works like a carryless multiplication: to get the $x^D$ term, you have to combine the products of terms $x^d$ and $x^{D-d}$, as long as $d\ge 0$ and $D-d\ge 0$. Here you see that the sum of the powers $d$ and $D-d$ is constant for a given $D$, and grows with $D$. For (infinite) Laurent or power series, you get a similar grouping of terms as in the polynomial product (known as a Cauchy products).

Now, take a sequence or signal $(\ldots,a_{-1},a_{0},a_{1},a_{2},\ldots,a_{n},\ldots)$. You can convert it into a simple object, easier to manipulate, by encoding the index $n$ into a power $z^{-n}$, because "powers don't mix": one cannot confuse two different powers. You then have a bijection between the space of sequences and the different power series: $\cdots+a_{-1}z^{1}+a_{0}z^{0}+a_{1}z^{-1}+a_{2}z^{2}+\cdots+a_{n}z^{-n}+\cdots$. Since you have this analogy between indices and powers, the Cauchy product naturally encodes the convolution (an isomorphism).

You can read more on:

• Polynomials, Convolution and Toeplitz matrices – Connecting the dots
• SE.maths: Convolution and multiplication of polynomials is the same?
• SE.maths: Why is polynomial convolution equivalent to multiplication in $F[x]/(x^n-1)$?