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 &#4294967295;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 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

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?
> 
> 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,

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

"LM" <mcourtn1@san.rr.com> a &#4294967295;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�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.
>�����������������������������������������������������������������������
>

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 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.

   ...

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.
�����������������������������������������������������������������������

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'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

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