Polynomial Multiplication
Note that when you multiply two polynomials together, their
coefficients are convolved. To see this, let denote the
th-order polynomial
![$\displaystyle p(x) = p_0 + p_1 x + p_2 x^2 + \cdots + p_m x^m
$](http://www.dsprelated.com/josimages_new/mdft/img1196.png)
![$ p_i$](http://www.dsprelated.com/josimages_new/mdft/img1197.png)
![$ q(x)$](http://www.dsprelated.com/josimages_new/mdft/img1198.png)
![$ n$](http://www.dsprelated.com/josimages_new/mdft/img80.png)
![$\displaystyle q(x) = q_0 + q_1 x + q_2 x^2 + \cdots + q_n x^n
$](http://www.dsprelated.com/josimages_new/mdft/img1199.png)
![$ q_i$](http://www.dsprelated.com/josimages_new/mdft/img1200.png)
![\begin{eqnarray*}
p(x) q(x) &=& p_0 q_0 + (p_0 q_1 + p_1 q_0) x + (p_0 q_2 + p_1...
...\qquad\qquad\;
\mathop{+} p_{n+m-1} q_1 + p_{n+m} q_0) x^{n+m}.
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1201.png)
Denoting by
![$\displaystyle r(x) \isdef p(x) q(x) = r_0 + r_1 x + r_2 x^2 + \cdots + r_{m+n} x^{m+n},
$](http://www.dsprelated.com/josimages_new/mdft/img1203.png)
![$ i$](http://www.dsprelated.com/josimages_new/mdft/img88.png)
![\begin{eqnarray*}
r_i &=& p_0 q_i + p_1 q_{i-1} + p_2 q_{i-2} + \cdots + p_{i-1}...
...=-\infty}^\infty p_j q_{i-j}\\
&\isdef & (p \circledast q)(i),
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1204.png)
where and
are doubly infinite sequences, defined as
zero for
and
, respectively.
Next Section:
Multiplication of Decimal Numbers
Previous Section:
Graphical Convolution