Forums

Calculating a "partial" IFFT

Started by LM September 2, 2006
Hi All,

I�m wondering if there is some way to save processing time when you want
only a subset of the data from an IFFT.

To be more concrete, suppose you perform an N point IFFT on some frequency
data, but you are interested in only a subset of the resulting time domain
values.  Is there a way to perform a smaller IFFT that will let you
recover those values of interest?  I am not speaking of the case in which
you want simply to decimate the time domain data to recover every Mth
value.  I am thinking in particular of the case in which you want to
recover a RANGE of values.

For example,

x1  = [ 0  0  0  0  0  0  0  0  1  1  1  1 10 10  1  1];
x2  = [ 0  0  0  0  0  0  0  0  1  1 10 10  1  1  1  1];
X1 = fft(x1);
X2 = fft(x2);
RXY = X1 .* conj(X2);
Rxy = ifftshift(ifft(RXY));

Rxy:
0	1	2	3	4	23	42	43
44	124	204	122	40	21	2	1

Suppose you wanted only values 5, 6, 7 and 8 from Rxy above.  Is there a
way to perhaps filter and decimate, then do a smaller IFFT, say 4 point
instead of 16 point, to recover only those values?

In my particular case I�m correlating the output of two phones (a few k
samples per FFT) and I know that only a small number of time delays will
actually be of interest.

Thanks very much,

LM



LM wrote:
> Hi All, > > I'm wondering if there is some way to save processing time when you want > only a subset of the data from an IFFT. > > To be more concrete, suppose you perform an N point IFFT on some frequency > data, but you are interested in only a subset of the resulting time domain > values. Is there a way to perform a smaller IFFT that will let you > recover those values of interest? I am not speaking of the case in which > you want simply to decimate the time domain data to recover every Mth > value. I am thinking in particular of the case in which you want to > recover a RANGE of values. > > For example, > > x1 = [ 0 0 0 0 0 0 0 0 1 1 1 1 10 10 1 1]; > x2 = [ 0 0 0 0 0 0 0 0 1 1 10 10 1 1 1 1]; > X1 = fft(x1); > X2 = fft(x2); > RXY = X1 .* conj(X2); > Rxy = ifftshift(ifft(RXY)); > > Rxy: > 0 1 2 3 4 23 42 43 > 44 124 204 122 40 21 2 1 > > Suppose you wanted only values 5, 6, 7 and 8 from Rxy above. Is there a > way to perhaps filter and decimate, then do a smaller IFFT, say 4 point > instead of 16 point, to recover only those values?
An IFFT is n*log(n) method of calculating an IDFT. An IDFT is a basis transform which can be calculated by an n*n matrix multiply. If you only need m points, then you can use a smaller n*m matrix multiply. One question to ask is whether n*m < n*log(n). If not, it may be faster to do an IFFT and throw away the unwanted values. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
LM wrote:
> I'm wondering if there is some way to save processing time when you want > only a subset of the data from an IFFT.
This is called a "pruned FFT" and is generally more trouble than it is worth, unless the number of outputs you want is very small. (Note than the IFFT and FFT are essentially the same thing, just differing by a complex conjugation). See: http://www.fftw.org/pruned.html for more information. Cordially, Steven G. Johnson
LM wrote:
> Hi All, > > I&#2013266066;m wondering if there is some way to save processing time when you want > only a subset of the data from an IFFT.
... It depends on the size or the subset. It is cheaper to calculate one point directly than to do the entire FFT. The size of the subset where the old-fashioned DFT matches the entire FFT is greater than one. Jerry -- Engineering is the art of making what you want from things you can get. &#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
>LM wrote: >> Hi All, >> >> I&#2013266066;m wondering if there is some way to save processing time when you
want
>> only a subset of the data from an IFFT. > > ... > >It depends on the size or the subset. It is cheaper to calculate one >point directly than to do the entire FFT. The size of the subset where >the old-fashioned DFT matches the entire FFT is greater than one. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095; >
Thanks much everyone for giving so freely. Ron, yes, I'm probably better off sticking with the IFFT if only because it would take me some time to get the mechanics of the matrix multiply correct. Steven, from the link you posted it sounds like this part of the code could see perhaps at best a two-fold increase in speed in my case. It's only one part of the processing so the overall increase would be less, but it's still a very useful hammer to have in the toolbox. Jerry, by "directly" do you mean work in the time domain on a subset of the data? Right now I'm reusing the FFT'd data for more than one type of processing (with the branch in question needing the pruned IFFT result) but that could be changed. LM
"LM" <mcourtn1@san.rr.com> a &#2013265929;crit dans le message de news: 
6vCdnXhCZISypmfZnZ2dnUVZ_rednZ2d@giganews.com...
> > Hi All, > > I'm wondering if there is some way to save processing time when you want > only a subset of the data from an IFFT. >
Hi, I don't honestly know if it is a "common" method or even if it will be effective in terms of mips in your application, but why not translating the spectrum with a numerical "heterodyne mixer", as in the old good analogic world ? Say, as it is easier to explain, that you have a 20Msamples time signal sampled at 20Msps, and you want to know its frequency spectrum from 6MHz to 6,01MHz with a very good frequency resolution (say 1Hz), then you can either : 1/ do a brute-force 20000000 points FFT and extract the 10000 frequency bins that you are interested in 2/ or : - Multiply, sample per sample, the input time signal with a synthetized 6MHz sine with the same sampling rate - Low pass filter the signal, you got a DC-10KHz signal (the filter can be quite simple), resample the out put signal to get a 20000 points time signal - Do a 20000 points FFT on the output signal Why not ? Friendly, -- Robert Lacoste ALCIOM - The mixed signal experts www.alciom.com
LM wrote:

> > Hi All, > > I&#2013266066;m wondering if there is some way to save processing time when you want > only a subset of the data from an IFFT. > > To be more concrete, suppose you perform an N point IFFT on some frequency > data, but you are interested in only a subset of the resulting time domain > values. Is there a way to perform a smaller IFFT that will let you > recover those values of interest? I am not speaking of the case in which > you want simply to decimate the time domain data to recover every Mth > value. I am thinking in particular of the case in which you want to > recover a RANGE of values. > > For example, > > x1 = [ 0 0 0 0 0 0 0 0 1 1 1 1 10 10 1 1]; > x2 = [ 0 0 0 0 0 0 0 0 1 1 10 10 1 1 1 1]; > X1 = fft(x1); > X2 = fft(x2); > RXY = X1 .* conj(X2); > Rxy = ifftshift(ifft(RXY)); > > Rxy: > 0 1 2 3 4 23 42 43 > 44 124 204 122 40 21 2 1 > > Suppose you wanted only values 5, 6, 7 and 8 from Rxy above. Is there a > way to perhaps filter and decimate, then do a smaller IFFT, say 4 point > instead of 16 point, to recover only those values? > > In my particular case I&#2013266066;m correlating the output of two phones (a few k > samples per FFT) and I know that only a small number of time delays will > actually be of interest. > > Thanks very much, > > LM
LM, In a nutshell, the discrete Fourier transform can be seen as a narrowband FIR filter for each output point. This requires n*m multiplications for m output points. The FFT takes n*log2(n) operations. This is optimal in the sense that operations are re-used. There is not much benefit in dropping a small number of output points from a FFT. For a small number of output points, you can revert back to the discrete FT. Depending on your processor, the breakeven point can be beyond log2(n) output points, as the discrete FT is algorithmically simpler. Kind regards, Iwo
Robert Lacoste wrote:
> I don't honestly know if it is a "common" method or even if it will be > effective in terms of mips in your application, but why not translating the > spectrum with a numerical "heterodyne mixer",
In a sense, this is very close to what a pruned FFT algorithm does. If you only want K outputs from an FFT of length N, you only need to compute a set of transforms of every N/K-th point (equivalent to resampling), and then combine N/K of these (equivalent to the low-pass filter). If the K outputs you want are not the lowest frequencies, then you need to shift the spectrum by premultiplying the input by a linear phase (i.e. heterodyning). (See fftw.org/pruned.html). This is not a bad approach as long as the inputs you want are consecutive frequency bins of the "full" FFT. However, in this case you might as well do the full FFT unless N/K > 100 in my experience (i.e. unless you want less than 1% of the FFT outputs). Several other people on this thread have suggested using the DFT definition directly if you only want a few outputs. However, I've found a pruned FFT to be faster than using the DFT definition for computing as few as 10 outputs, so if you really care about speed and are computing more than a few bins you might think about this. Also, a pruned FFT, like an FFT, can be much more accurate than using the DFT definition directly if K is not too small. Applying the DFT definition directly (or Goertzel, etc), can have one substantial advantage over a pruned FFT, however: if you are reading/computing the data on the fly, the storage required if you use the DFT definition is only proportional to the number of *outputs* (you don't need to store all the inputs at once). Cordially, Steven G. Johnson
I agree with the hetrodyning approach.  It will require a bandpass filter 
followed by the multiplication by a sinusiod followed by a lowpass filter and 
decimation.  I would not try to decimate to DC using a 6 MHz sine wave for 
hetrodyning since there are signal wraparound issues with the skirts of the 
bandpass filter.

In article <44fbcd0b$0$25935$ba4acef3@news.orange.fr>, "Robert Lacoste" 
<see-my-email-at@www.alciom.com> wrote:
>"LM" <mcourtn1@san.rr.com> a &#2013265929;crit dans le message de news: >6vCdnXhCZISypmfZnZ2dnUVZ_rednZ2d@giganews.com... >> >> Hi All, >> >> I'm wondering if there is some way to save processing time when you want >> only a subset of the data from an IFFT. >> > >Hi, >I don't honestly know if it is a "common" method or even if it will be >effective in terms of mips in your application, but why not translating the >spectrum with a numerical "heterodyne mixer", as in the old good analogic >world ? Say, as it is easier to explain, that you have a 20Msamples time >signal sampled at 20Msps, and you want to know its frequency spectrum from >6MHz to 6,01MHz with a very good frequency resolution (say 1Hz), then you >can either : > >1/ do a brute-force 20000000 points FFT and extract the 10000 frequency bins >that you are interested in > >2/ or : >- Multiply, sample per sample, the input time signal with a synthetized 6MHz >sine with the same sampling rate >- Low pass filter the signal, you got a DC-10KHz signal (the filter can be >quite simple), resample the out put signal to get a 20000 points time signal >- Do a 20000 points FFT on the output signal > >Why not ? >Friendly, >