Convolution and Polynomial Multiplication

Published by Arun Isaac on

Tags: math, signals

"Convolution in the time domain is multiplication in the frequency domain" is an oft-quoted statement. But the exact relation between the two is seldom stressed adequately. Mathematically, convolution and polynomial multiplication are one and the same process, as I shall explain shortly.

"Convolution in the time domain is multiplication in the frequency domain" is an oft-quoted statement. But the exact relation between the two is seldom stressed adequately. Mathematically, convolution and polynomial multiplication are one and the same process, as I shall explain shortly.

Consider the signals \[ x[n] = {4,1,2} \] \[ h[n] = {1,2,3} \]

Their respective transforms are

\[ X(z) = 4 + z^{-1} + 2z^{-2} \] \[ H(z) = 1 + 2z^{-1} + 3z^{-2} \]

As you can very well see, the transforms are just the signal samples put with appropriate polynomial terms.

\[ Y(z) = X(z) H(z) \] \[ Y(z) = (4 + z^{-1} + 2z^{-2}) (1 + 2z^{-1} + 3z^{-2}) \] \[ Y(z) = 4(1 + 2z^{-1} + 3z^{-2}) + z^{-1}(1 + 2z^{-1} + 3z^{-2}) + 2z^{-2}(1 + 2z^{-1} + 3z^{-2}) \] \[ Y(z) = 4 + 9z^{-1} + 16z^{-2} + 7z^{-3} + 6z^{-4} \]

Notice carefully what is happening in the polynomial multiplication above. H(z) is getting multiplied by each term of X(z). That is the same as each sample of x[n] producing an appropriately scaled impulse response as output - exactly what happens with convolution!

Thus convolution and polynomial multiplication are mathematically one and the same thing. And if you notice, numerical computation software like GNU Octave and Mathworks Matlab do not have dedicated functions for polynomial multiplication and division. You just have to use the convolution function for polynomial multiplication, and the deconvolution function for polynomial division.

Yes, deconvolution is nothing but long division…