efficient inverse fft of a band-pass function

"anando" <meet_anando@yahoo.com> wrote in message 
news:v5CdndW3OpOF94zVnZ2dnUVZ_v2pnZ2d@giganews.com...
>
>>
>>For an IFFT of length N, if the number of non-zero coefficients
>>K is much less than log N, then one could just compute a naive
>>inverse DFT pruned to just calculating for K bins.
>>
>>If you actually want something different from the entire
>>and precise IFFT result vector, then you could note that
>>this complete IFFT looks very similar to a modulated
>>and upsampled result for some narrow baseband signal.
>>You might be able to translate your non-zero bins to
>>baseband, un-zero-pad, and perform a much shorter IFFT.
>>But this is unlikely to be more efficient unless you don't
>>need, or have some other (analog?) solution for, upsampling
>>interpolation and modulation later in your desired process.
>>
>
> Thanks a ton to all of you who have replied. This idea is one that appeals
> to me a lot and I might try it.
>
> So if I understand you correctly, I could
> * heterodyne the signal such that my zero frequency lies at
>     f_0 = 0.5*(f_1 + f_2) - then
> * I could take an IFFT of a much much smaller vector.
>
> Of course the time samples will be much coarser than the original IFFT -
> but I guess I can always interpolate ?
>
> Please correct me if I am mistaken. What did you mean by un-zero pad ?
>
> Cheers,
> Anando.

After decimating you don't need to interpolate any more than you did before.

Consider this:

An AM signal.  The carrier is of no real interest.  The interesting part is 
all in the waveform envelope.  So, the decimation still gets you a good 
representation of the envelope.

Fred 

On 25 Apr., 07:27, "anando" <meet_ana...@yahoo.com> wrote:
> >>Thanks for your reply. I do realize that R_b(f) can be written as a
> >>product of R(f) and a boxcar function in the frequency space. As
> >mentioned
> >>before, I know the inverse FT of R(f) [as r(t) is known] and also the
> >>boxcar function [some combination of sinc functions - let us call it
> >s(t)
> >>].
>
> >>So I guess my query is how would I write down the inverse FT of R_b(f)
> >>using r(t) and s(t) in a computationally efficient manner.
>
> >>Again, many thanks for your help.
>
> >>Cheers,
> >>Anando.
>
> >Hi Anando,
> >I agree with what the others have said, but I'm not sure they answered
> >what you were asking. &#4294967295;When you say "write down...", do you mean how to
> >digitally calculate the result, or how to write down the equation? &#4294967295;As
> an
> >equation, the Inverse FT of R_b(f) is equal to the convolution of r(t)
> and
> >s(t). As a previous post pointed out, if this is for digital signals you
> >need to worry about circular convolution. &#4294967295;Here's some links:
>
> >http://www.dspguide.com/ch9/2.htm
> >http://www.dspguide.com/ch9/3.htm
>
> >Steve
>
> Hi Steve
>
> Thanks for your mail.
>
> I was hoping to calculate the result I guess.
>
> Just to clarify my question, in a slightly abstract form, my query is,
> would it be possible to recreate the inverse FT of a band-pass signal from
> the inverse FT of the full signal ? I'd be very grateful if you have
> pointers for that.

Sure. Let's say that y[n] is the desired bandpass signal, and x[n] is
the full band signal. You want to calculate y[n], given x[n]. That's
easy:

y[n] = IDFT[ rect[k] DFT[x[n] ]

where rect[k] is the suitably chosen rectangular bandpass.

Regards,
Andor

On Apr 23, 11:11 am, "anando" <meet_ana...@yahoo.com> wrote:
> Hi
>
>
>
>
>
> >Another way to express your band-limited signal is  R_b(f) = R(f) H(f)
> >Where H(f)= 1     f_1<= |f| <=f_2
> >           = 0     otherwise
>
> >There are some variations between the versions of the Fourier transform,
> >but there is properties that relates multiplication in Fourier space to
> >convolution in time.  In your case (FFT), it goes by two names:
> >"circular convolution" property and "cyclic convolution" property.
>
> >Circular convolution has some subtleties of which you need to be aware.
> >It's not the convolution your mother taught you. So if you are not
> >familiar with it do some web searches.
>
> >Cheers,
> >J. Elms
>
> Thanks for your reply. I do realize that R_b(f) can be written as a
> product of R(f) and a boxcar function in the frequency space. As mentioned
> before, I know the inverse FT of R(f) [as r(t) is known] and also the
> boxcar function [some combination of sinc functions - let us call it s(t)
> ].
>
> So I guess my query is how would I write down the inverse FT of R_b(f)
> using r(t) and s(t) in a computationally efficient manner.

Given that s(t) has infinite support, the most computationally
efficient manner might well be to just (re)do a finite length
FFT/boxcar/IFFT (or pruned FFT/IDFT), or to accept some form
of approximation to your desired boxcar filtered r(t), using
something such as FIR or IIR time domain filters, over a
circular buffer if needed, for instance.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

>On Apr 23, 11:11 am, "anando" <meet_ana...@yahoo.com> wrote:

>> Thanks for your reply. I do realize that R_b(f) can be written as a
>> product of R(f) and a boxcar function in the frequency space. As
mentioned
>> before, I know the inverse FT of R(f) [as r(t) is known] and also the
>> boxcar function [some combination of sinc functions - let us call it
s(t)
>> ].
>>
>> So I guess my query is how would I write down the inverse FT of R_b(f)
>> using r(t) and s(t) in a computationally efficient manner.
>
>Given that s(t) has infinite support, the most computationally
>efficient manner might well be to just (re)do a finite length
>FFT/boxcar/IFFT (or pruned FFT/IDFT), or to accept some form
>of approximation to your desired boxcar filtered r(t), using
>something such as FIR or IIR time domain filters, over a
>circular buffer if needed, for instance.
>
>
>IMHO. YMMV.
>--
>rhn A.T nicholson d.0.t C-o-M
>

Hi 

Many thanks for your suggestions. Any links to time-domain FIR/IIR
filtering will be greatly appreciated (second part in your reply).

Also, could wavelets be used for my problem ? For example, could I wavelet
transform r(t) to give me the boxcar filtered r(t) ?

Cheers,
Anando.