🚀 go-pugleaf

In article <5340@orca.WV.TEK.COM> mhorne%ka7axd.wv.tek.com@relay.cs.net writes:
>
>This is interesting.  Considering the fact that the complexity of the DFT
>is O(NlogN), wouldn't some sort of direct interpolation of the DFT output
>be faster?  At first glance, it would appear that sample-rate conversion
>techniques can be applied directly to frequency-domain data, much like it is
>done for time-domain data.  It would seem that if the time-domain data set has
>met the Nyquist criteria, then so has the frequency-domain data (that is, the
>imaginary and real data parts, not the sqrt(i^2 + r^2)), and for large L
>(interpolation) values, you might get a big win in computation rate compared
>to a zero-padded DFT.  Has anyone looked into this, or is there something
>fundamental that I am overlooking?
>
>Mike Horne
>mhorne%ka7axd.wv.tek.com@relay.cs.net

If you add a pile of zeros to the end of the DFT input, you are wasting 
computational time. Consider the case where you have a sequence of four
samples, and you want to interpolate them into a 16 point DFT. I know, this
is trivial, but it illustrates the point.
Anyway, you take x0 to x3 and add 12 zeros to the end:

xn:	x0 x1 x2 x3  0  0  0  0  0  0  0  0  0  0  0  0

n:	0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15

Then bitreverse the data orders before doing a decimation-in-time FFT:

x(bitrev(n)):	x0 0  0  0  x2 0  0  0  x1 0  0  0  x3 0  0  0

n:		0  8  4  12 2  10 6  14 1  9  5  13 3  11 7  15

I would like to draw a 16 point DIT FFT butterfly diagram at this point,
but that's a pain, so you'll have to wait until the middle of 1990 when
my paper on this comes out in the IEEE ASSP journal. :-)

Anyway...

We have the FFT butterfly:
		A' = A + BW         A -   - A'
				       \ /
				        x
				       / \
		B' = A - BW	    B -W  - B'

(You know what I mean)

Now, in the first pass, the B terms are zero for all of the butterflies,
and the A terms are zero for half of the butterflies.
We know:
		A + 0W = A	(1)

		0 + 0W = 0	(2)

So half of the butterflies can be eliminated outright, and the other half
can be replaced by a replication of the upper input at both outputs.
The second pass gives us a situation where equation (1) applies to all
butterflies, so in the first two passes all we have done is to copy a
bunch of numbers around. Not too hard, even for a microprocessor. Then we
go on to do pass 3 and 4 just like in a normal FFT, and presto! we've cut
the time required to do the FFT in half. You can eliminate the time required
to copy the numbers by rewriting 'pass 3' (or wherever you have to start
calculating values) to take all inputs from the same location. In general,
if you want to interpolate from 2^m points to 2^n points, you can eliminate
the first n-m passes of the FFT.

This work, and ways to efficiently look at parts of the FFT output without
calculating all of it, has been published previously by Screenivas and Rao
in 1977 (I think - I don't have the reference handy). I extended their method
to include the case where you want to place the interpolating zeros in
the center of the sequence, which is handy if you're trying to go from the
frequency domain to the time domain.

(A side note: It takes a lot of time to get submissions published. We did this
stuff in 1987, and received word about a month ago that they were going
to publish this in 1990.)

If anyone is interested, I can provide code of our efficient zooming FFT
(That's right, EZFFT) in C.

Theo Smit (smit@enel.ucalgary.ca)