Hi I'd be grateful if somebody could point me to the right literature for the following problem: I have a function r(t) which is known as well as its Fourier transform R(f). Thus R(f) --> IFFT --> r(t). Both of them are known. Now suppose I have a bandpass version of R(f) [let us call it R_b(f)] such that R_b(f) = R(f) for f_1 <= f <= f_2 = 0 otherwise Is there a way of calculating the inverse fourier transform of R_b(f) in terms of the known quantities ? Many thanks, Anand.
efficient inverse fft of a band-pass function
Started by ●April 23, 2008
Reply by ●April 23, 20082008-04-23
anando wrote:> Hi > > I'd be grateful if somebody could point me to the right literature for the > following problem: > > I have a function r(t) which is known as well as its Fourier transform > R(f). Thus R(f) --> IFFT --> r(t). Both of them are known. > > Now suppose I have a bandpass version of R(f) [let us call it R_b(f)] such > that > R_b(f) = R(f) for f_1 <= f <= f_2 > = 0 otherwise > > Is there a way of calculating the inverse fourier transform of R_b(f) in > terms of the known quantities ? > > Many thanks, > Anand. > >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
Reply by ●April 23, 20082008-04-23
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. Again, many thanks for your help. Cheers, Anando.
Reply by ●April 24, 20082008-04-24
On Apr 23, 7:20 am, "anando" <meet_ana...@yahoo.com> wrote:> Now suppose I have a bandpass version of R(f) [let us call it R_b(f)] such > that > R_b(f) = R(f) for f_1 <= f <= f_2 > = 0 otherwise > > Is there a way of calculating the inverse fourier transform of R_b(f) in > terms of the known quantities ?i.e. you want to take advantage of the fact that you are computing the ifft of a function that is partially or mostly zero. This is called a "pruned FFT", and in principle for a transform of length N and K nonzero inputs you can reduce the complexity to O(N log K) instead of O(N log N). However, unless K is less than 1% of N it is probably not worth it, in my experience. Google "pruned FFT" for more info. Regards, Steven G. Johnson
Reply by ●April 24, 20082008-04-24
"anando" <meet_anando@yahoo.com> wrote in message news:1MedncKzcPL2hpLVnZ2dnUVZ_jmdnZ2d@giganews.com...> Hi > > I'd be grateful if somebody could point me to the right literature for the > following problem: > > I have a function r(t) which is known as well as its Fourier transform > R(f). Thus R(f) --> IFFT --> r(t). Both of them are known. > > Now suppose I have a bandpass version of R(f) [let us call it R_b(f)] such > that > R_b(f) = R(f) for f_1 <= f <= f_2 > = 0 otherwise > > Is there a way of calculating the inverse fourier transform of R_b(f) in > terms of the known quantities ? > > Many thanks, > Anand.This is a good question and one that I pondered a couple of years ago. Unfortunately, there's no improvement possible. An arm-waving explanation is that after the first step in the FFT/IFFT none of the values are any longer zero. Thus, most of the computations can't be eliminated. Fred
Reply by ●April 24, 20082008-04-24
On Apr 23, 3:20 am, "anando" <meet_ana...@yahoo.com> wrote:> Hi > > I'd be grateful if somebody could point me to the right literature for the > following problem: > > I have a function r(t) which is known as well as its Fourier transform > R(f). Thus R(f) --> IFFT --> r(t). Both of them are known. > > Now suppose I have a bandpass version of R(f) [let us call it R_b(f)] such > that > R_b(f) = R(f) for f_1 <= f <= f_2 > = 0 otherwise > > Is there a way of calculating the inverse fourier transform of R_b(f) in > terms of the known quantities ?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. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Reply by ●April 24, 20082008-04-24
I am guessing you can take advantage of the fact that for a bandpass signal it is sufficent to sample it by (f_2-f_1), but the method that you describe will yield samples that are sampled at the original Fs.. This means that you can save not only at the first stage, but also the last stage of the FFT.. i.e. you will get [Fs/(f_2-f1)] periods in the last stage If (f_2-f_1) is known or not variable, you can try some tricks to simplify.. Hope that helps
Reply by ●April 24, 20082008-04-24
>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. Asmentioned>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 its(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. When you say "write down...", do you mean how to digitally calculate the result, or how to write down the equation? 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. Here's some links: http://www.dspguide.com/ch9/2.htm http://www.dspguide.com/ch9/3.htm Steve
Reply by ●April 25, 20082008-04-25
> >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.
Reply by ●April 25, 20082008-04-25
> >>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. When you say "write down...", do you mean how to >digitally calculate the result, or how to write down the equation? Asan>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. 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. Cheers, Anando.