Three different Fourier transforms are usually defined and all have applications in digital signal processing.
The continuous Fourier transform of the function x(t) is defined with the formula
The inverse continuous Fourier transform is
The discrete Fourier transform of the function x(k) is defined with the formula
and its inverse is
The discrete-time Fourier transform is defined by the formula
and its inverse, usually written using ω = 2π f, is
The three forms of the Fourier transform above are sometimes abbreviated as FT, DFT, and DTFT.
Interpretation
As any other transform, the Fourier transform translates one type of function into another. The usual interpretation in digital signal processing is that the Fourier transforms translate a function of time given specific amplitudes, frequencies, and phase amounts into a function of frequencies and phase amounts for specific amplitudes and time.
For example, take the discrete Fourier transform and apply Euler's formula.
for n = 0, 1, …, N – 1. Suppose that x(k) is a real valued signal. Fourier analysis tells us that
where B_{n} = A_{n} cos(2π f_{n} τ_{n}) and C_{n} = A_{n} sin(2π f_{n} τ_{n}) are the coefficients of the simple wave A_{n} cos(2π f_{n} (t - τ_{n})) in x(k) with frequency f_{n}, amplitude A_{n}, and phase τ_{n}. Specifically, B_{n} and C_{n} define the amplitude and phase
of the frequency n in the signal x(k).
Thus, the Fourier transform is a natural extension of the Fourier series. There are three motivations for using the Fourier transform rather than the Fourier series. First, the Fourier transform allows for shorter notation. Second, the use of complex numbers allows the Fourier transform to return a complex valued function, which means two separate values that can be used to describe the amplitude and the phase of the signal separately. Using complex numbers in the Fourier transform allows us to compute the coefficients B_{n} and C_{n} simultaneously and to produce a single function H(n) – a function that indirectly returns both amplitude and phase. Third, the Fourier transform has an inverse transform, which is easy to describe and which has its own uses.
A simple example of the discrete Fourier transform
Suppose that we take a simple discrete sine wave with frequency f, amplitude A and phase m, sampled over N points for a period of time 1. The values of this simple wave would be
where B = -A sin(2π f m / N) and C = A cos(2π f m / N). We can compute the discrete Fourier transform as follows.
for n = 0, 1, …, N – 1. We use Euler's formula again
and note that most of these functions will be orthogonal over the sampling period, except in two cases – for n = f and for N – n = f. In the second case, we note that
The transform, as a function of f, translates to
The two sums for a large enough sampling frequency N evaluate to approximately N / 2 and so the transform is simply
Thus, the discrete Fourier transform of a simple wave with frequency f produces a function H(n) that indicates something about the single wave at components n = f and n = N – f and is zero otherwise. Specifically, at n = f and k = N – f .
These are the amplitude (scaled by N / 2) and phase of the original simple sine wave. If the original wave was a complex signal consisting of various waves with different amplitudes and frequencies, the result will be much the same due to the fact that simple sine or cosine waves with different frequencies are orthogonal.
Thus, the discrete Fourier transform H(n) of a real valued signal x(k), evaluated at the frequency n, shows the amplitude of the n^{th} simple wave component in the signal x(k)
and the phase of the n^{th} simple wave component in x(k) is
Suppose that we compute, for example, the discrete Fourier transform of a simple sine wave at 10 Hz, using the discrete Fourier transform with 100 points over 2 seconds of the wave. The magnitude of the resulting discrete Fourier transform components will be as in the following figure.
The discrete Fourier transform will be non-zero – approximately – at components 20 and 80. Since we are sampling with 100 points over 2 seconds, we have effectively sampled the wave with the sampling frequency 50 Hz. This means that we have used the discrete Fourier transform with components at 0.5 Hz, 1 Hz, 1.5 Hz, …, 49.5 Hz (These multiples of 0.5 Hz are orthogonal over 2 seconds.). The 20^{th} component is 10 Hz and it makes sense that we have a non-zero value at this component. According to the discussion above, we also get a non-zero value at component 80 = 100 – 20. The magnitude of the discrete Fourier transform at these components is 100 / 2 = 50. These results are as expected. (We chose to compute the discrete Fourier transform with N uniform points over 2 seconds. How we choose the points of the discrete Fourier transform defines what the transform components are. In this case, the components represent the frequencies between 0 and N / 2. Most often, the discrete Fourier transform is computed with the first N points of a signal sampled at the sampling frequency f_{s}. In this case, the components are the frequencies 0, f_{s} / N, 2 f_{s} / N, …, (N – 1) f_{s} / N. The discrete Fourier transform then poses one interesting question, namely what the component at 0 represents. The magnitude of the component at 0 for a signal of the form x(k) = A_{0} + A_{1} sin(2π k f / N) would be N A_{0}. Thus, although the discrete Fourier transform component at 0 is usually meaningless for digital signal processing, in analog signals it represents DC current.)
When the input to the discrete Fourier transform or the inverse discrete Fourier transform is real valued and not complex, the transform produces complex numbers such that H(N – 1 – n) is the complex conjugate of H(n). The information for n > N / 2 is redundant.
The fact that the discrete Fourier transform of a real valued signal produces repeated and redundant information is uncomfortable. We have two choices. First, we can ignore the second half. Second, we can feed the transform with complex numbers. The complex frequency f sampled over N, for example, is
When the discrete Fourier transform is used on complex data, however, the results are different. Take the simple wave
The component H(n) of the discrete Fourier transform at n = f would be
This result is twice larger than the result of the discrete Fourier transform of a real valued signal.
The discrete Fourier transform H(n) of a complex valued signal x(k) shows the amplitude of the n^{th} simple wave component in the signal x(k)
and the phase of the n^{th} simple wave component in x(k)
The discrete Fourier transform and finite impulse response filters
A finite impulse response low pass filter is simply a signal composed of the simple waves with frequencies less than the cutoff frequency f_{c} (see Low pass filter). We should be able to use the discrete Fourier transform to compute the frequency response (magnitude response and phase response) of the low pass filter. As above, we note that this low pass filter is real valued and hence we can dispose of half of the components. We also note that the low pass filter of length N in the Low pass filter topic is already scaled by 2 / N. Thus, we can compute the standard discrete Fourier transform over N points, but in order to compute the magnitude, we will not scale by 2 / N. The resulting computation for the magnitude response of the filter is
The fact that the discrete Fourier transform is computed with a small set of components – the length of the filter – means that the magnitude response would be sparse in the frequency domain, as shown on the following figure. Suppose that we take the sampling frequency of f_{s} = 2000 Hz and we create a standard finite impulse response low pass filter with length N = 101 and cutoff frequency of f_{c} = 40 Hz. The magnitude response of the filter in the figure below employs a transform of N = 101 points, which is the same as the length of the filter. The cutoff frequency is between components 2 and 3, which, given the sampling frequency of f_{s} = 2000 Hz, translates to between 39.6 Hz and 59.4 Hz (sampling 101 times over 2000 Hz implies 19.8 Hz per component). Note that this figure is limited to component 50, or half of N.
With the discrete Fourier transform we can also compute the phase response of our low pass filter prototype. We note that the filter has coefficients that are symmetric around the middle, i.e., a(k) = a(N – 1 – K). Assume for a moment, that Re(H(n)) > 0. Then
Since a(k) = a(N – 1 – k),
The phase response, assuming that the filter is of odd length, is as follows.
The "1 +" in the numerator and denominator handle the case when the filter is of odd length N. If the filter has even number of points N, the computations would be the same but without "1 +". Thus,
The phase response of a finite impulse response filter with coefficients that are symmetric around the middle is linear with respect to the frequency n and produces a delay of (N – 1) / 2 samples. These computations assume that Re(H(n)) > 0, but are similar in other cases.
Using the inverse discrete Fourier transform
If the discrete Fourier transform produces the magnitude response of a filter, then we should be able to produce a filter by taking the inverse discrete Fourier transform from a desired magnitude response. The topic Low pass filter shows how to create a low pass filter by summing up the simple waves up to the cutoff frequency.
This equation can also be written as
where B_{n} is the desired magnitude response of the filter, equal to 1 up to the cutoff frequency f_{c} and zero afterwards. The upper limit of the sum is f_{s} / 2 as suggested by the Nyquist-Shannon sampling theorem.
This formula is very similar to the inverse discrete Fourier transform, except that it only takes the real part of the inverse discrete Fourier transform, hence only the cosines, is limited to half of the inverse transform, hence the sum goes up to only f_{s} / 2, and is scaled by 2. Thus, this formula samples the frequency content and uses computations similar to the inverse discrete Fourier transform to create a filter. We are not limited to sampling only at f_{s}, and we can sample at any evenly spaced N points. In other words, the low pass filter can be created by
We note that cosine functions are symmetric around the origin and that the filter a(k) could similarly be symmetric around the origin, if we are after a linear phase response. We can then extend the sum and remove the scaling factor of 2 as follows.
Note the natural addition of n = 0 to the sum. Since Bn represents the desired filter magnitude response, the magnitude response should remain at 1 as the frequency approaches zero.
Finally, in an attempt to make the filter symmetric around (N – 1) / 2, we shift the filter as follows.
This filter formula resembles the inverse discrete Fourier transform, but it is not the inverse discrete Fourier transform. We do not use the inverse discrete Fourier transform to produce a FIR filter. There are important differences between the inverse transform and the filter computation above. First, the formula above uses only the real part of the inverse discrete Fourier transform. Second, the formula above is shifted both in n, as the sum runs from –N / 2 to N / 2 and in k, as the sum uses k – (N – 1) / 2.
The formula above is the real portion of a generalized or shifted form of the inverse complex valued discrete Fourier transform, which is usually written as
Note that we could easily add the imaginary part of the inverse discrete Fourier transform above. Since sine functions are odd (i.e., sin(-x) = -sin(x)), the sum of the sine values for n = -N / 2, …, N / 2 would simply be zero. In other words, by designing a desired magnitude response B_{n} that is symmetric around the origin, we created an inverse transform and thus a filter that contains only real valued coefficients.
Using a desired magnitude response that includes negative frequencies may be troublesome, since negative frequencies do not mean much. The technique of using a symmetric magnitude response to produce a real valued filter is, however, common.
Sampling of the continuous inverse Fourier transform
The continuous-time Fourier transform translates a signal x(t) that is a function of time for specific amplitudes, frequencies, and phase amounts into a signal H(x(t)) that is a function of frequencies and phase amounts for specific amplitudes and time. The inverse Fourier transform translates functions of frequencies and phase amounts into signals in time. An example of how the continuous inverse Fourier transform can be sampled to produce a low pass filter is shown in the topic Low pass filter.
Relationships between the Fourier transform and other transforms
The discrete-time Fourier transform is a special case of the Z transform. It is the Z transform evaluated at z = e^{jω} = e^{j 2πf}.
The continuous Fourier transform is equivalent to evaluating the bilateral Laplace transform with s = j ω = j 2πf.
Properties of the Fourier transform
The following are some of the more basic properties of the Fourier transform. Denote the Fourier transform of x(t) as in the definition above with H_{s}. Given integrable functions x(t) and y(t), complex numbers a and b, real numbers T and S, and the nonzero real number c
The first property is obviously the linearity of the Fourier transform. The second and third equations above are called the time shifting (or translation) properties. The fourth property shows scaling in the time domain. The fifth equation shows complex conjugation properties (this property explains the redundancy of the transform when used on real data). The last equation shows the transform of a convolution, which is useful when creating transfer functions of digital filters stacked one after the other.
A note on the fast Fourier transform
Using the discrete Fourier transform is quite computationally intensive. Each discrete Fourier transform of length N requires N^{2} multiplications of complex numbers. The fact that the number of computations in the discrete Fourier transform is proportional to N^{2} labels the transform as an O(N^{2}) algorithm.
An alternative is to use the fast Fourier transform, or FFT. The FFT is not a transform, but is rather an algorithm for faster discrete Fourier transform computations. There are a number of good programmatic implementations of the FFT readily available and hence we will not present one here. We only present the theoretical foundation of the FFT, which is quite simple.
The FFT relies on the following equation, known as the Danielson-Lanczos lemma. The discrete Fourier transform of N points H_{N}(x(k)), can be written as follows
In other words, the discrete Fourier transform of N points can be computed as the sum of two discrete Fourier transforms of N / 2 points, where the first transform traverses the even points of the original discrete Fourier transform and the second transform traverses the odd points of the original transform. The second transform – of odd points – must be multiplied by some constant.
If we can split the discrete Fourier transform in to two transforms of length N / 2, then we can also split these two new transforms into four transforms of length N / 4. In fact, if we select the easy case where N is a power of 2, we can continue splitting up the transform into smaller transforms until we have a number of transforms of length 1.
For a discrete Fourier transform of length N, the FFT would require N transforms of length one and N complex computations because of the constants that appear in front of the transforms of the odd points. The FFT, however, would also require log_{2}(N) operations to perform the discrete Fourier transform split into smaller transforms. Thus, the number of operations in the FFT is proportional to N log_{2}(N), which means that the FFT is an O(N log_{2}(N)) algorithm. On large sets of data, the FFT would be much faster than the discrete Fourier transform. For example, the discrete Fourier transform and FFT are useful in audio pitch shifting. A three-minute audio track may require up to 8 billion computations to be pitch shifted with the discrete Fourier transform, but it would require only about 80 million computations to be pitch shifted with the FFT.