FOURIER TRANSFORM

We first examine the two ways to visualize polynomial multiplication. The two ways lead us to the most basic principle of Fourier analysis that

A product in the Fourier domain is a convolution in the physical domain

Look what happens to the coefficients when we multiply polynomials.

$$\begin{eqnarray} X(Z)\, B(Z) &\quad =\quad& Y(Z) \\ (x_0 + x_1 Z + x_2 Z^2 + \cd... ...0 + b_1 Z + b_2 Z^2) &\quad =\quad& y_0 + y_1 Z + y_2 Z^2 + \cdots\end{eqnarray}$$ (1) (2)

Identifying coefficients of successive powers of Z, we get

$$\begin{eqnarray} y_0 &\quad =\quad& x_0 b_0 \nonumber \\ y_1 &\quad =\quad& x_1 ... ... \\ &\quad =\quad& \cdots\cdots\cdots\cdots\cdots\cdots \nonumber\end{eqnarray}$$ (3)

In matrix form this looks like  

$$\left[ \begin{array} {c} y_0 \\ y_1 \\ y_2 \\ y_3... ... \begin{array} {c} b_0 \\ b_1 \\ b_2 \end{array} \right]$$ (4)

The following equation, called the ``convolution equation,'' carries the spirit of the group shown in (3)  

$$y_k \quad =\quad\sum_{i = 0} x_{k - i} b_i$$ (5)

The second way to visualize polynomial multiplication is simpler. Above we did not think of Z as a numerical value. Instead we thought of it as ``a unit delay operator''. Now we think of the product X(Z) B(Z) = Y(Z) numerically. For all possible numerical values of Z, each value Y is determined from the product of the two numbers X and B. Instead of considering all possible numerical values we limit ourselves to all values of unit magnitude $Z=e^{i\omega}$ for all real values of $\omega$.This is Fourier analysis, a topic we consider next.