<< Chapter < Page | Chapter >> Page > |
Some applications require only a few DFT frequencies. One example is frequency-shift keying (FSK) demodulation, in which typically two frequencies are used to transmit binary data; another example is DTMF , or touch-tone telephone dialing, in which a detection circuit must constantly monitor the line fortwo simultaneous frequencies indicating that a telephone button is depressed. Goertzel's algorithm reduces the number of real-valued multiplications by almost a factor of two relative to direct computation via the DFT equation . Goertzel's algorithm is thus useful forcomputing a few frequency values; if many or most DFT values are needed, FFT algorithms that compute all DFT samples in $O(N\lg N)$ operations are faster. Goertzel's algorithm can be derived by converting the DFT equation into an equivalent form as a convolution, which can be efficiently implemented as a digital filter. For increased clarity, in the equations below the complex exponential is denoted as $e^{-(i\frac{2\pi k}{N})}={W}_{N}^{k}$ . Note that because ${W}_{N}^{-Nk}$ always equals 1, the DFT equation can be rewritten as a convolution, or filtering operation:
We want $y(n)$ not for all $n$ , but only for $n=N$ . We can thus compute only the recursive part, or just the left side of the flow graph in , for $n$
For certain frequencies, additional simplifications requiring even fewer multiplications are possible. (For example, for the DC( $k=0$ ) frequency, all the multipliers equal 1 and only additions are needed.)A correspondence by C.G. Boncelet, Jr. describes some of these additional simplifications.Once again, Goertzel's and Boncelet's algorithms are efficient for a few DFT frequency samples; if more than $\lg N$ frequencies are needed, $O(N\lg N)$ FFT algorithms that compute all frequencies simultaneously will be more efficient.
Notification Switch
Would you like to follow the 'The dft, fft, and practical spectral analysis' conversation and receive update notifications?