A DSP algorithm for frequency analysisThe Chirp-Z Transform (CZT), a little-known spectrum analysis algorithm, offers engineers a high-resolution FFT combined with the ability to specify bandwidth. Here's a look at how CZT works and what it has to offer.
Engineers working in the field of digital signal processing often use the fast Fourier transform (FFT) algorithm to detect tones, frequencies, signatures, and other events. In specific situations, however, other algorithms may actually work better than the FFT. Knowing when to use what algorithm can help you improve the system you're working on.
For instance, to detect specific frequencies when you're looking for tones from telephones or to detect 60Hz noise on power lines, the Goertzel algorithm ("The Goertzel Algorithm," by Kevin Banks, Embedded Systems Programming, Sept 2002, p. 34) finds specific frequencies faster than the FFT.
For analyzing a range of frequencies, such as recording frequency response measurements, matching voice patterns, or displaying spectrum information on the face of an amateur radio, what algorithm works best? Although most engineers would use the FFT, another, lesser-known algorithm gives you additional flexibility to specify both spectral analysis bandwidth and the resolution within that bandwidth and provides real and imaginary outputs from which you can compute spectral magnitude and phase. In this article, I'll introduce you to that algorithm, known as the Chirp-Z transform (CZT), and we'll compare it to the better known Goertzel and FFT.
To understand the CZT, first visualize the FFT. As shown in Figure 1A, when calculating the FFT, the cyclic frequency range of 0Hz to the sampling frequency (ƒs) is equal to 0 thru 2π radians around the unit circle with samples taken equal distance around it. The CZT is capable of calculating the spectrum of a signal over an arc of the unit circle as shown in Figure 1B or, in other words, a signal between two arbitrary frequencies below the sampling frequency such as 255Hz to 1,234Hz.
Figure 1: Unit circle representation of spectrum
Figure 2: Data flow through CZT
The CZT is not restricted to calculating the spectrum on the unit circle and can compute the z-transform at points along circles or spirals on the z-plane, as shown in Figure 1C and 1D. These calculations, however, are beyond the scope of this article.
You can understand the details of the CZT as the convolution of the sampled input and the unit circle arc coefficients defined when selecting the resolution of the CZT, as shown in Figure 1B. As seen in Figure 2, two FFTs and one inverse FFT are used to calculate the CZT. Therefore, to quickly determine the CZT, the number of points sampled must be a power of two. You're not restricted to this rule, however, because the CZT code, which is posted online at ftp://ftp.embedded.com/pub/2004/02sirin, will zero-pad the input samples to a power of two. If you're using the CZT in real-time spectrum analysis, knowing the following values will increase the CZT's computing speed:
- What is the sampling frequency of the input?
- How many input samples are there?
- What is the start frequency of the bandwidth of interest?
- What is the stop frequency of the bandwidth of interest?
- What spectral resolution do you want in the bandwidth of interest?
Most likely the sampling frequency and number of input samples will not change after each use of the CZT. Therefore, if you designate a constant output resolution and start and stop bands, you can precompute the arc coefficients at initialization, thereby speeding up the CZT computation at the expense of flexibility.
Sampling frequency, input samples
The sampling frequency usually depends on the application. For example:
- 8kHztelephony standard
- 16kHzG.722 audio compression standard for video teleconferencing
- 32kHzused in digital radio
- 44.1kHzCD quality audio
The CZT uses the sampling frequency as a reference to determine where the start and stop bands are located on the unit circle. The resolution, also known as bin size, is determined by dividing the sampling frequency bandwidth by the number of input samples. For instance, if the sample frequency bandwidth is 44.1kHz and 1,024 samples were recorded in 23ms, then the resolution would be 44,100/1,024 = 43Hz.
Increasing the number of samples to 2,048 recorded over 46ms would offer a resolution of 44,100/2,048 = 21.5Hz.
Start and stop frequency, frequency resolution
Engineers are often interested in a small range of frequencies and over-sample an analog signal to satisfy the Nyquist criterion. Having over-sampled, the bins below and above the bandwidth of interest don't aid in creating a clear picture of the desired frequencies, as shown in Figure 3.
Figure 3: Resolution using FFT
Figure 4: Sample spectrum using FFT
With the CZT, the user can define not only the start and stop frequencies but also the number of bins contained by that bandwidth.
You can see the significance of resolution if two frequencies appear between the set bin sizes. Suppose 128 samples at 8kHz are taken of an audio signal. The resolution is 8,000/128 = 62.5Hz, and three of the bins are calculated to be 437.5Hz, 500Hz, and 562.5Hz respectively.
62.5 * N = 437.5, 500, 562.5Hz (where N = 7, 8, 9)
If two tones were acquired at 470Hz and 530Hz between the established bins, the spectrum output would appear similar to the yellow shaded area in Figure 4. Analysis of this spectrum would indicate a tone at 500Hz has been detected, also shown in Figure 4.
Using the CZT with a start and stop frequencies of 100Hz and 1,000Hz respectively, 128 output samples would give a resolution of 7Hz, similar to the enhanced resolution shown in Figure 5.
Figure 5: CZT resolution superimposed over FFT
Figure 6: Sample spectrum using CZT
With a higher resolution of 7Hz per bin, the two tones at 470Hz and 530Hz can clearly be resolved, as seen in Figure 6. This configuration allows resolution of any two tones that are separated by at least 7Hz.
To summarize, the CZT requires the sampling frequency and number of input samples be coupled with the start and stop frequencies to determine the arc along the unit circle with which the sampled inputs will be convolved. The CZT also requires the number of output samples to establish the resolution between the start and stop frequencies.
CZT vs. FFT
Having expended so much effort on increasing the speed and accuracy of the FFT, why would there be a need for anything else? The answer lies in the sacrifices made to the FFT to achieve speed. One such limitation is the power-of-two rule, requiring the number of input samples to be an integer power of two (in other words, 128, 256, 512). While in itself this may not seem important, coupled with the fact that sampling frequencies are often dictated by the sampling hardware to common sampling frequencies, such as 44.1kHz, 22.050kHz, 16kHz, 11.025kHz, and 8kHz resolution, choices start becoming severely limited as shown in Table 1.
Table 1: Possible bins sizes with common sampling frequencies and power-of-two number of samples
Add to this scenario the Nyquist criterion, requiring the sampling frequency to be twice the highest frequency being sampled. Then, choosing to lower sampling frequencies for better resolution is no longer a viable option. A clever engineer would simply increase the number of samples being taken. However, this solution quickly gets out of hand.
Every increase in samples collected must be twice that previously sampled in order to satisfy the power-of-two rule shown in Table 2. The sampling frequency and number of samples acquired define the sampling time interval. For example, to capture 1,024 samples with a sampling rate of 8kHz requires (1/8,000)*1,024 = 0.128 seconds. Stepping up to the next power of two, the sampling time required is (1/8,000)*2,048 = 0.256 seconds. Here's the pattern: to attain twice the resolution, twice the number of samples is required, which takes twice the time to acquire.
Table 2: Valid power of two samples
Compared to the FFT, the CZT is much more flexible. Given the sampling rate and the number of samples taken, you can tailor the resolution to your application by adjusting the start and stop frequencies and the number of output samples (bin size). It's ironic, however, that to make spectrum analysis more flexible, the CZT uses the FFT itself. The faster the FFT becomes, the more efficient the CZT becomes. In spite of this, the CZT will never be faster than the FFT.
CZT vs. Goertzel
The Goertzel algorithm is a faster method of pitch detection than the FFT for single frequencies. The Goertzel's amazing speed comes from focusing on detecting the amplitude and phase of a single frequency. Although the Goertzel isn't limited by the power-of-two rule, the same sampling and bin size considerations of the FFT apply. Not bound by the power-of-two rule, the Goertzel is more flexible at adjusting bin sizes. Assuming that sampling rates are dictated by hardware (in other words, 44.1kHz, 8kHz), you only need to change the number samples to achieve the desired bin size.
To determine the number of samples to obtain in the Goertzel algorithm, find the smallest integer value of k that provides an integer value number of samples (in other words, 205, 301). If you can't find an integer value of k and you use an approximate resolution, be aware that you might not get an accurate magnitude measurement. If the Goertzel algorithm is used for tone detection, this problem may not be an issue. Be aware that a larger number of samples takes longer to sample. Therefore, for real-time applications you may need to minimize the sampling duration.
Although the Goertzel algorithm is better suited to tone detection, you can use it for spectrum analysis by looking at multiple tones to create a spectrum. To do this, you should change the target frequency and sweep it across the spectrum of interest. This method is acceptable for very small bandwidths but becomes much slower as the number of frequencies being swept across grows. The FFT and CZT, on the other hand, are much more time efficient at calculating the spectrum of larger bandwidths.
Compared to the FFT, the Goertzel algorithm is more flexible. Given the sampling rate and the target frequency, the number of samples acquired can easily be adjusted to obtain the desired bin size. The advantages of speed and flexibility are spoiled by the Goertzel's singular focus on a solitary frequency. The CZT, in contrast, offers more choices than the Goertzel for selecting resolutions, but does so at the price of speed. In addition, the CZT output resolution can be tailor made by adjusting the start and stop frequencies, and the number of output samples (bin size) over a range of frequencies.
The CZT is capable of analyzing a range of frequencies to record frequency response measurements, match voice patterns, or display spectrum information. It gives the engineer the flexibility to specify bandwidth and resolution, and outputs real and imaginary frequency components from which the magnitude and phase can be computed.
With a better understanding of the CZT algorithm, the widespread and enduring use of the FFT begs the question, "Is the need for more resolution and flexibility worth the computational load and time delay?" The CZT is another tool in the engineer's arsenal when engineers are challenged to detect tones, frequencies, signatures, or some telltale sign of a condition of interest. Similarly, the Goertzel algorithm is a powerful tool, which finds specific frequencies faster than the FFT. The pertinent design question to ask yourself is "Is the single frequency detection of the Goertzel algorithm too narrow and the FFT too wide for my application?"
Simon Sirin is an engineer at the Remote Sensing Laboratory, operated for the U.S. Department of Energy by Bechtel Nevada, where he works on embedded and real-time software and hardware applications. He holds a BS in electrical engineering from the University of Nevada, Las Vegas. You can reach him at email@example.com.
This work was supported by the U.S. Department of Energy, National Nuclear Security Administration Nevada Site Office, under Contract No. DE-AC08-96NV11718. DOE/NV/11718833.
Banks, Kevin. "The Goertzel Algorithm," Embedded Systems Programming, September 2002, pp. 32"42.
Taft, Jeffrey. "The Java Chirp Z-Transform Source Code Page," September 2003, www.nauticom.net/www/jdtaft/JavaCZT.htm
Taft, Jeffrey. "The Chirp Z-Transform Page," September 2003, www.nauticom.net/www/jdtaft/czt.htm
Oliver, William. "Chirp z-Transform," June 2003, http://feynman.stanford.edu/people/Oliver_www/singhtml/node44.html
Bluestein's FFT Algorithm. Wikipedia, July 2003, http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm
The figures in the article are misleading. The distance between bin centers ("bin size" in the figures) is altered from the FFT to the CZT. The bin shape (the yellow hump in the figures) or frequency resolution is determined by the input sample set: 1 / (# of samples times Sample Frequency). This does not change between the FFT and the CZT. The resolution does not change. You can read this in the wikipedia reference.
Dale B. Dalrymple
That k must be an integer in the Goertzel algorithm is a common misconception. Choosing it so somewhat simplifies the analysis and greatly simplifies the explanation, but it is by no means required by the mathematics. For a fixed sqmple rate and frequencies to be detected (such as DTMF and FSK), non-integer k can significantly improve the accuracy of discrimination.
Refer to recent threads on group:comp.dsp (Goertzel detector to Goertzel filter?), (Another Goertzel question, and Goertzel's Algorithm for RF Spectral Monitoring), or simply try it and see.