The main operation of the Discrete Fourier Transform is the dot product.1 Actually performing the dot product is straightforward. We take two signals of equal length, multiply their elements together one-by-one, and then sum up the products.
| Equation 1. Classical Notation for the Dot Product | Example 1. Example Calculation of the Dot Product |
|
$$\sum_{n=0}^{N-1} a[n] \cdot b[n]$$
|
Given two signals a and b, a[n] = [3, 5, 7, 9, 4] b[n] = [8, 2, 5, 3, 1] We compute their dot product as, (3 × 8) + (5 × 2) + (7 × 5) + (9 × 3) + (4 × 1) Which leaves us with, 24 + 10 + 35 + 27 + 4 = 100 |
At first glance this operation may seem uninteresting, but there is a nice geometric interpretation of that dot product that we can leverage. As it turns out, we can use the dot product to measure the degree to which two vectors or signals are pointing or heading in the same direction. When two vectors are perpendicular to one another, they point in completely different directions and their dot product will be zero. The dot product is at its maximum when two vectors run parallel to one another. Note that the dot product may be negative, indicating the the two vectors have a similar but opposite heading. Play around with the following figure to see how the value of the dot product changes as the orientation between the two vectors changes.
|
Figure 1. Geometric Interpretation of the Dot Product Click and drag to change the endpoint of the pink vector |
|
|
I’d like you to think of the dot product as a measure of similarity. In the next section we’ll see how the dot product can be used to measure the similarity between something a bit more complicated than two dimensional vectors - signals of arbitrary length.