Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search


Polynomial Multiplication

Note that when you multiply two polynomials together, their coefficients are convolved. To see this, let $ p(x)$ denote the $ m$ th-order polynomial

$\displaystyle p(x) = p_0 + p_1 x + p_2 x^2 + \cdots + p_m x^m
$

with coefficients $ p_i$ , and let $ q(x)$ denote the $ n$ th-order polynomial

$\displaystyle q(x) = q_0 + q_1 x + q_2 x^2 + \cdots + q_n x^n
$

with coefficients $ q_i$ . Then we have [1]

\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 q_1 + p_2 q_0) x^2 \\
& & \mathop{+} (p_0 q_3 + p_1 q_2 + p_2 q_1 + p_3 q_0) x^3\\
& & \mathop{+} (p_0 q_4 + p_1 q_3 + p_2 q_2 + p_3 q_1 + p_4 q_0) x^4 + \cdots\\
& & \mathop{+} (p_0 q_{n+m} + p_1 q_{n+m-1} + p_2 q_{n+m-2} \\
& & \qquad\qquad\;
\mathop{+} p_{n+m-1} q_1 + p_{n+m} q_0) x^{n+m}.
\end{eqnarray*}

Denoting $ p(x) q(x)$ 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},
$

we have that the $ i$ th coefficient can be expressed as

\begin{eqnarray*}
r_i &=& p_0 q_i + p_1 q_{i-1} + p_2 q_{i-2} + \cdots + p_{i-1}q_1 + p_i q_0\\
&=& \sum_{j=0}^i p_j q_{i-j} = \sum_{j=-\infty}^\infty p_j q_{i-j}\\
&\isdef & (p \circledast q)(i),
\end{eqnarray*}

where $ p_i$ and $ q_i$ are doubly infinite sequences, defined as zero for $ i<0$ and $ i>m,n$ , respectively.


Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition'', by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8.
Copyright © 2014-04-06 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA