Free Books
   Free Books    Mathematics of the DFT  

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... ...\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}... ...=-\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 Section:
Multiplication of Decimal Numbers
Previous Section:
Graphical Convolution