Convolution in the frequency domain

Let $Y(Z)=X(Z)\,B(Z)$.The coefficients y_t can be found from the coefficients x_t and b_t by convolution in the time domain or by multiplication in the frequency domain. For the latter, we would evaluate both X(Z) and B(Z) at uniform locations around the unit circle, i.e., compute Fourier sums X_k and B_k from x_t and b_t. Then we would form C_k=X_k B_k for all k, and inverse Fourier transform to y_t. The values y_t come out the same as by the time-domain convolution method, roughly that of our calculation precision (typically four-byte arithmetic or about one part in 10^-6). The only way in which you need to be cautious is to use zero padding greater than the combined lengths of x_t and b_t.

An example is shown in Figure 8. It is the result of a Fourier-domain computation which shows that the convolution of a rectangle function with itself gives a triangle. Notice that the triangle is clean--there are no unexpected end effects.

 

box2triangle Figure 7 Top shows a rectangle transformed to a sinc. Bottom shows the sinc squared, back transformed to a triangle.

Because of the fast method of Fourier transform described next, the frequency-domain calculation is quicker when both X(Z) and B(Z) have more than roughly 20 coefficients. If either X(Z) or B(Z) has less than roughly 20 coefficients, then the time-domain calculation is quicker.