efficient inverse fft of a band-pass function
in [DSP]
|
Prev: Wholesale AAA Omega Double Eagle Chronometer Mens Watch 1503.30 Replica
Next: Zeroforcing precoding/beamforming
From: anando on 23 Apr 2008 07:20 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.
From: J Elms on 23 Apr 2008 09:07 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
From: anando on 23 Apr 2008 14:11 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.
From: Steven G. Johnson on 24 Apr 2008 11:52 On Apr 23, 7:20 am, "anando" <meet_ana...(a)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
From: Fred Marshall on 24 Apr 2008 12:21
"anando" <meet_anando(a)yahoo.com> wrote in message news:1MedncKzcPL2hpLVnZ2dnUVZ_jmdnZ2d(a)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 |