Polynomial Multiplication and Signal Processing

Why multiply polynomials?

For one thing, it turns out that the fastest algorithms we have for multiplying integers rely heavily on polynomial multiplication. More importantly, multiplying polynomials is crucial for signal processing. A signal is any quantity that is a function of time (as in Figure (a)) or of position.
In order to extract information from a signal, we need to first digitize it by sampling (Figure (b))—and, then, to put it through a system that will transform it in some way. The output is called the response of the system

An important class of systems are those that are linear—the response to the sum of two signals is just the sum of their individual responses—and time invariant—shifting the input signal by time t produces the same output, also shifted by t.

Any system with these properties is completely characterized by its response to the simplest possible input signal: the unit impulse $\delta(t)$ . We can express any signal $a(t)$ of such property as:

a(t) = \sum_{i=0}^{T-1}a(i)\delta(t-i)

The system’s response to input $a(t)$ is determined by the responses to the various $\delta(t − i)$ . And by time invariance, these are in turn just shifted copies of the impulse response $b(t)$ , the response to $\delta(t)$ . Therefore the output of the system at time k is

c(k) = \sum_{i=0}^ka(i)b(k-i)

This looks exactly like a polynomial multiplication formula!