Discrete Fourier Transform
The discrete Fourier transform (DFT) is a method for converting a sequence of complex numbers to a new sequence of complex numbers,
for
The are thought of as the values of a function, or signal, at equally spaced times The output is a complex number which encodes the amplitude and phase of a sinusoidal wave with frequency cycles per time unit. This comes from Euler's formula: The effect of computing the is to find the coefficients of an approximation of the signal by a linear combination of such waves. Since each wave has an integer number of cycles per time units, the approximation will be periodic with period This approximation is given by the inverse Fourier transform
The DFT is useful in many applications, including the simple signal spectral analysis outlined above. Knowing how a signal can be expressed as a combination of waves allows for manipulation of that signal and comparisons of different signals:
Digital files (jpg, mp3, etc.) can be shrunk by eliminating contributions from the least important waves in the combination.
Different sound files can be compared by comparing the coefficients of the DFT.
Radio waves can be filtered to avoid "noise" and listen to the important components of the signal.
Other applications of the DFT arise because it can be computed very efficiently by the fast Fourier transform (FFT) algorithm. For example, the DFT is used in state-of-the-art algorithms for multiplying polynomials and large integers together; instead of working with polynomial multiplication directly, it turns out to be faster to compute the DFT of the polynomial functions and convert the problem of multiplying polynomials to an analogous problem involving their DFTs.
Contents
Basic Examples
Let Then the DFT of the is So this gives an expression of as Check: When this returns and when this returns
So the DFT gives a breakdown of a "spike" into a sum of waves (equally weighted in this case), which all peak at but interfere with each other and cancel out perfectly at other integer time values
If the spike occurs at a different time, the coefficients change:
Find the DFT of
In this case, So The answer is
Proceeding as in the previous example, this gives the expansion Converting the complex coefficients to complex exponentials gives This is an example of phase shifting occurring in the sum. Taking the real parts of both sides gives a sum of cosine waves: where the addition of has the effect of shifting the waves forward by respectively.
Orthogonality and the Inverse Transform
Why is the formula for the inverse transform true? Substitute the formula for into the formula for : When the inner sum is by the formula for a geometric series (as in the first example in the previous section). When the inner sum is So the entire sum is as desired.
Another way to think of this argument is that it is a consequence of orthogonality with respect to the complex dot product. Consider the complex vectors where It is not hard to check, by an argument similar to the one given above, that these complex vectors are orthogonal with respect to the complex dot product (or inner product): if , otherwise Remember that the complex dot product of two vectors and is where the bar denotes complex conjugation. There are of these vectors, so they form an orthogonal basis of
The DFT formula for is simply that where is the vector The inverse formula recovers in terms of , by writing using the standard formula for expressing any vector as a linear combination of orthogonal basis vectors:
Convolution and Polynomial Multiplication
As a sample application of the DFT, consider polynomial multiplication.
Given two polynomials and call the coefficient vectors and and , respectively. The product will have degree with the coefficients given by the convolution vector with
It is convenient to extend the vectors and to a common space by padding them with extra s: take a value of larger than and let if or is larger than or , respectively. (For FFT applications it is often best to let be a power of 2.) Then the beautiful fact about convolution and the DFT is
The DFT of is the componentwise product of the DFT of and the DFT of .
The proof of this fact is straightforward and can be found in most standard references.
So multiplying and can be accomplished by padding the coefficient vectors, computing their DFTs, multiplying the DFTs, and applying the inverse DFT to the result.
Find using the DFT.
Pad the coordinate vectors to and The DFT of is this follows from the two examples above, since the DFT is additive and we know the DFTs of and and the DFT of is The coordinatewise product of these two is and the inverse DFT of this vector is So the product is
This may seem like a roundabout way to accomplish a simple polynomial multiplication, but in fact it is quite efficient due to the existence of a fast Fourier transform (FFT). The point is that a normal polynomial multiplication requires multiplications of integers, while the coordinatewise multiplication in this algorithm requires only multiplications. The FFT algorithm is so the polynomial multiplication algorithm which uses the FFT is as well.
Multiplying large integers is done in the same way: an integer like can be viewed as the evaluation of the polynomial at so multiplying integers can be reduced to multiplying polynomials (and then evaluating at 10, or whatever base is most convenient).