Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!zephyr.ens.tek.com!orca!mhorne%ka7axd.WV.TEK.COM From: mhorne@ka7axd.WV.TEK.COM (Michael T. Horne) Newsgroups: comp.dsp Subject: Re: FFTs of Low Frequency Signals (really: decimation) Message-ID: <5305@orca.WV.TEK.COM> Date: 10 Nov 89 22:09:54 GMT References: <5619@videovax.tv.tek.com> <10208@cadnetix.COM> <2586@irit.oakhill.UUCP> Sender: nobody@orca.WV.TEK.COM Reply-To: mhorne%ka7axd.wv.tek.com@relay.cs.net Organization: Tektronix Visual Systems Group, Wilsonville, OR Lines: 127 In a recent article by Bart Massey: > >The typical technique for coping (with) the problem is, I believe, to "make >the signals higher-frequency", through the magic of decimation. Assume that >all the signals of interest are in the range 0-1KHz, and you're sampling at >16KHz (32000 samples/sec). If necessary, run a low-pass filter over the >input, to remove signals in the range 1-16KHz. Note that the record length >of this filter will itself be very large, but at least it's a linear process, >so *relatively* cheap. Now, just take every 16th sample! > >What've you just done? You've mapped the sample frequency domain 0-1KHz >onto the range 0-16KHz! Now, if you do e.g. a 16-point FFT on your new >record, your bin centers will be at 500Hz, 1500Hz, .. , 15500Hz in the new >range, which corresponds to (500/16)Hz .. (15500/16)Hz, i.e. 31.25Hz .. >968.75Hz in the original domain. Note that even with the FFT cost of O(N) = >N lg N, you have saved quite a bit over doing the FFT directly on the >original data. In particular, for the FFT on the original data, the cost >was roughly 256 * 8 = 2048 units, whereas the low-pass filter plus the short >FFT costs roughly 256 + 16 * 4 = 320 units -- a significant savings, even >though you get the same amount of info about the band in question either way! I agree in part with Bart's comments, however decimating the data will not provide you with any better frequency domain resolution directly. This is most easily shown by example. We'll use Bart's sampling criteria as shown above, that is: F = 32 kHz (original sampling rate) M = 16 (decimation factor to use) F' = 2 kHz (desired sampling rate, from F/M) Fc = 1 kHz (signals of interest are below Fc) The form of a standard sampling rate converter that decimates by a factor M is: +------+ +---+ x(n) ----->| h(n) |----->| M |-------> y(m) +------+ +---+ h(n) is designed to filter out spectral components in the range of F/M to (F - F/M). As Bart describes above, this would be a filter that passes signals from 0 to ~1 kHz, and suppresses signals (ideally) from 1 to 16 kHz. The `M' box is the decimator that throws out every M-1 filtered samples (i.e. every M-th sample is kept). Typical signals for the above system might look like this (using the same frequency scale for all plots): | |------------------------//-- --//------------------------| | \ / | |X(w)| | \ / | +-----|-----|-----|-----//-----|-----//-----|-----|-----|-----| 0 1 2 3 16 29 30 31 32 kHz | |---- ----| | \ / | |H(w)| | | | | +-----|-----|-----|-----//-----|-----//-----|-----|-----|-----| 0 1 2 3 16 29 30 31 32 kHz | |---- --------- ----//-----------//---- --------- ----| | \ / \ / \ / \ / | |Y(w')| | | | | | | +-----|-----|-----|-----//-----|-----//-----|-----|-----|-----| 0 1 2 3 16 29 30 31 32 kHz Filtering the input data stream reduces the spectral content to just the band of interest, while the act of throwing away samples reduces the sampling frequency to F/M. For example, if you originally took 256 samples at 32 kHz, the output of the sample rate converter with M=16 will be 256/16 = 16 samples at 32kHz/16 = 2kHz sample rate (this assumes a continuous stream of data points to keep the filter `primed'). The frequency resolution of an N-pt DFT is given by: resolution = (sample rate)/(# of samples taken) which is really just the inverse of the duration of the sampling sequence. If you take the DFT of the 256 sample sequence, you will find that the `bins' are separated by 32kHz/256 = 125 Hz. Note, however, that after you have decimated the signal to just 16 samples at a 2 kHz sample rate, you still have 2kHz/16 = 125 Hz resolution. You have *not* increased your frequency domain resolution by changing the sample rate (through decimation). The point that I am trying to make is that just doing decimation doesn't help you achieve more frequency resolution (though it can increase your time-domain amplitude resolution through noise reduction); however, it does provide you with smaller data sets to work with, a very desirable property. You *can* get better resolution by doing 1) zero padding of the data, or 2) sampling longer at F and then decimating to reduce the data set, then performing the DFT on the reduced data. Both of these methods effectively increase your sample duration, thereby increasing your frequency domain resolution. As a side note, there are many techniques known for reducing the computational requirements of the filter section. For example, since you are only keeping every M-th output from the filter, you don't need to calculate the filter output for those samples you throw out. This reduces the effective filtering rate from F calculations/sec to F/M calculations/sec, a significant difference for large M. Also, multi-stage filters are possible that allow you to relax the filtering requirements in the first few stages (by inserting "don't care" bands). For example, you can effectively achieve a decimate-by-16 sample rate converter by cascading two decimate-by-4 converters, yet use considerably fewer filtering taps in the two M=4 stages combined than in the single M=16 stage. For extended info on this topic, I'd strongly recommend getting a copy of Crochiere & Rabiner's "Multirate Digital Signal Processing" (Prentice-Hall). >In short (no pun intended :-), decimate your data -- IMHO you'll be glad >you did! When your bands of interest are << than your sampling rate, this is a very good recommendation from a computational point of view. > Bart Massey > ..tektronix!videovax.tv.tek.com!bart > ..tektronix!reed.bitnet!bart Mike Horne mhorne@ka7axd.wv.tek.com ...!tektronix!mhorne%ka7axd.wv.tek.com