Digital Filtering Using the FFT - Practical Analog and Digital Filter Design - page 214

Solution: In each case, the resolution ∆ f required is 1 kHz in order to clearly
see the three frequencies. In Example 9.1, m w will be 1, and for Example 9.2, we
will use a value of 2. Equation (9.3) can then be used to determine that the number
of time samples N needed would be 20 for Example 9.1 and 40 for Example 9.2.
Figures 9.1 and 9.3 seem to support these values.
From the previous examples we see that we must choose N carefully to get the
resolution required for our system. It seems obvious that the more time domain
samples available, the clearer the picture of the frequency spectrum will be, and
that is true. But once the minimum number of data samples is determined, is there
any advantage to increasing the number of frequency points computed? It may not
be clear at this point, but providing more frequency points does not improve the
resolution, it simply provides a more continuous graph of the spectrum. This is
seen in Figure 9.4, which shows the Hamming window case with N = 20 and K =
20. Comparing this to the 20-point graph in Figure 9.3, we note that the 3-kHz
component is obscured in either case. Increasing the number of frequency data
points 50-fold did nothing to improve the resolution of the DFT.
In a similar argument, if you have available many time samples, but compute
far fewer frequency points, you are losing valuable frequency information.
Therefore, a general rule of thumb is to let N = K as a starting point in the design
of a DFT system. On occasion, it may be necessary to allow K to increase to find a
more exact value of the frequency of a maximum.
9.2 THE FAST FOURIER TRANSFORM (FFT)
While the computation of the DFT may be straightforward, it is not without
computational cost. For an N -point DFT, each frequency point will require N
multiplications of the real valued x ( n ) times the complex valued exp ( -j ω k n ). (This
operation effectively requires two real multipliers.) Then, assuming there are N
different frequency points, there will be N 2 complex multiplications necessary for
the computation of the DFT. This can produce large numbers very quickly.
The fast Fourier transform (FFT) had its beginnings in 1965, long before the
DSP chip was even a dream of engineers. However, it took the computational
power of computers to bring its importance to the attention of designers. It is
sometimes thought that the FFT produces a different result than the DFT, but it
does not. The FFT is simply a faster method of computing the DFT. Derivations of
the FFT algorithm can be found in the references in Appendix A, but it is
worthwhile to see a simple illustration of how computational savings can be made
using the FFT.