🚀 go-pugleaf

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