Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"anando" <m...@yahoo.com> wrote in message 
news:1...@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 

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

  


       

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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


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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.