Path: utzoo!attcan!uunet!cs.utexas.edu!rice!uw-beaver!ubc-cs!alberta!calgary!enel!smit From: smit@enel.ucalgary.ca (Theo Smit) Newsgroups: comp.dsp Subject: Re: FFTs of Low Frequency Signals (really: decimation) Summary: Efficient interpolation FFTs Message-ID: <2150@cs-spool.calgary.UUCP> Date: 22 Nov 89 22:55:53 GMT References: <5624@videovax.tv.tek.com> <5619@videovax.tv.tek.com> <10208@cadnetix.COM> <2586@irit.oakhill.UUCP> <5305@orca.WV.TEK.COM> <5340@orca.WV.TEK.COM> Sender: news@calgary.UUCP Reply-To: smit@enel.UUCP (Theo Smit) Organization: U. of Calgary, Calgary, Alberta, Canada Lines: 81 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)