DSP Main | Archives | Feedback

The FFT is one of the first tools we reach for when given a data sequence to analyze; one of the first results we typically look at is the periodogram, a plot of the FFT output magnitude as a function of frequency. That plot usually gives good preliminary answers to questions about the signal's character: Does it contain periodic components? Is it made up of one or more narrowband components? How noisy is it?

An added benefit of periodogram analysis is that it requires no assumptions about the signal. Unlike parametric spectral-analysis techniques such as Burg's, you don't need to correctly specify a model order to get useful results.

The FFT spectrum analyzer does, however, have some limitations, one big one being that it only produces results at a discrete set of frequencies. If you want to know the frequency of a peak on the spectrum plot, you can't directly obtain an answer with a resolution better than 1/T, where T is the length of the data sequence. In this article I'll explain one way around this problem.

Before getting started, it's important to understand what kind of resolution improvement we're talking about. The problem we're addressing here is improving the resolution of the measurement of the frequency of a single peak in the spectrum. If you need to resolve multiple spectral components spaced less than 1/T apart, then what follows won't help; you need a longer data record or a super-resolution analysis tool.

But for resolving one peak, imagine you have a sequence of N observations x₀, x₁, ..., x_N-1. The periodogram estimate for its power spectral density is:

You can solve the problem of locating a peak in S(ω) indirectly by finding the roots of ∂S/∂ω. Let y_k = kx_k for k = 0,...,N-1,

A little elementary calculus yields

Thus, to locate peaks in the periodogram you can turn to any numerical method that solves the equation

Of popular methods, the binary search technique is simple and nearly foolproof. To use it, first compute the periodogram over a discrete set of frequencies with an FFT. Once you've identified a peak of interest, you must specify a range of frequencies to search, typically the frequency of the FFT bin containing the peak plus or minus half of the bin's bandwidth.

Let's call the limits of the search ω₀ and ω₁. If a peak falls between those two, then the signs of

should be different.

Now define a new frequency If the sign of

agrees with that of

then set ω₀ = ω_mid; otherwise set ω₁ = ω_mid. The new values for ω₀ and ω₁ now define a frequency interval containing the peak with half the uncertainty as the previous interval. You can repeat this procedure as many times as needed to reach the required accuracy, gaining one bit of frequency resolution per iteration.

A variation on the binary search method is the method of false position, sometimes called regula falsi. It replaces the computation of ω_mid with the equation

The false-position method usually converges much more quickly than a binary search, but you might encounter certain pathological datasets where the algorithm fails to converge at all.

Fig 1--The periodogram in (a) was generated from 16 samples of a sinewave with a frequency of 19/64, which is slightly less than that of the peak that appears in Bin 5. Using the two algorithms described in this column you can refine the location of the peak as shown in (b), where the frequency resolution increases with each iteration of the algorithm.

Fig 1 displays the results of a computer simulation of both techniques. Fig 1a shows the periodogram obtained by taking a 16-point FFT of the sequence sin((2π19/64)k) for k = 0,...,15. The periodogram exhibits a peak in the fifth "bin" corresponding to a frequency of 2π20/64, so I chose initial values for the limits of the search to be ω₀ = 2π18/64 and ω₁ = 2π22/64. Fig 1b shows, the method of false position converges much more rapidly than a binary search for this example.

Other techniques can provide more accurate estimates of spectral peak locations, particularly if you have a good model of the signal source, but if all you need is a quick and dirty answer, you might consider trying these two methods.

Mark Sullivan (dalek@radix.net) is Chief Scientist at SkyBitz Inc (Herndon, VA), a developer of tracking and communications services based on the GLS (Global Locating Systems) technology it invented. Mark received a PhD in Information Technology from George Mason Univ.

This article originally appeared in Personal Engineering & Instrumentation News, August 1996, pgs 65-66. Reprinted with permission of PEC Inc; all rights reserved.

		Click here to get your listing up.