COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

Is there a way to reduce the number of operations in this FFT procedure?

• Email
• Follow

```Hi all,

Suppose my signal is a complex valued signal, and it is complex conjugated
with respect to the center t=0.

That's to say f(-t)=f(t)*, where "*" denotes the complex conjugate.

Suppose now I do the truncation of above signal into between [-B, B),

and I sample it using stepsize dB,

then in Matlab, the sampling points are cfs=[-B:dB:B-dB],

which has 2B/dB data points, e.g. -B, -B+dB, -B+2*dB, ... , 0, dB, 2*dB, ...
B-dB.

Let's assume 2B is divisable by dB.

I found out that I have to do fftshift(cfs) before feeding into fft
function, then I will obtain my desired output:

so,

output = fft(fftshift(cfs)),

and the output are all real numbers. This is our desired output.

Now I want to ask: is there some trick in FFT that I can use to further
reduce computations?

Let's say, since my output is going to be real, and my input is complex
conjugate, is there a way to throw away the real part, and only do the FFT
on the real part, or something like that? I saw somewhere on the web that
there is a special program for real input and real output FFT which can be
even faster than a standard complex FFT.

Moreover, my input is complex conjugate, is there a way that I can throw
away the f(t)'s for t<0, and thus only do fft on half of the orginal data
sequence?

Thanks a lot!

```
 0
Reply lunamoonmoon (258) 8/9/2007 3:50:22 AM

See related articles to this posting

```<SNIP>
> Suppose my signal is a complex valued signal, and it is
complex conjugated
> with respect to the center t=0.
>
> and the output are all real numbers. This is our desired
output.
>
> Now I want to ask: is there some trick in FFT that I can
use to further
> reduce computations?

Probably!

What you seem to be saying is that The real part of your
signal is even, and the imaginary part is odd, so when you
transfer it into the frequency domain, you get a real only
spectrum.

Suppose you multiply your next signal by -i (-j) so this
will have an odd real part, and a even imaginary part, then
Passing the summed signal into the FFT you will end up
doing exactly the same calculation that you did before, but
now the spectrum you will get out will be complex - but
note that the real component will be the spectrum of signal
1 and the imaginary part will be the spectrum of signal 2
(albeit multiplied by -i (-j)) So you will now be able to
almost double the performance of your algorithm.

Hope that this is of some help.

Regards

Dave Robinson

```
 0
Reply dave.robinson (1276) 8/9/2007 8:34:32 AM

```On Aug 9, 4:34 am, "Dave Robinson" <dave.robin...@somewhere.biz>
wrote:
> <SNIP>
>
> > Suppose my signal is a complex valued signal, and it is
> complex conjugated
> > with respect to the center t=0.
>
> > and the output are all real numbers. This is our desired
> output.
>
> > Now I want to ask: is there some trick in FFT that I can
> use to further
> > reduce computations?
>
> Probably!
>
> What you seem to be saying is that The real part of your
> signal is even, and the imaginary part is odd, so when you
> transfer it into the frequency domain, you get a real only
> spectrum.
>
> Suppose you multiply your next signal by -i (-j) so this
> will have an odd real part, and a even imaginary part, then
> add this to your first signal (fft is a linear process).
> Passing the summed signal into the FFT you will end up
> doing exactly the same calculation that you did before, but
> now the spectrum you will get out will be complex - but
> note that the real component will be the spectrum of signal
> 1 and the imaginary part will be the spectrum of signal 2
> (albeit multiplied by -i (-j)) So you will now be able to
> almost double the performance of your algorithm.
>
> Hope that this is of some help.
>
> Regards
>
> Dave Robinson

Thanks Dave....I don't see how does it double my performance?

```
 0
Reply lunamoonmoon (258) 8/9/2007 1:13:42 PM

```> Thanks Dave....I don't see how does it double my
performance?
>

Lets say you are currently doing a 1024 point complex FFT

What I am suggesting is that you take two of these
waveforms and add them together via the complex
manipulation I told you about. You still have a 1024 point
you get a complex answer in which the real part is the
spectrum of signal 1 and the imaginary part is spectrum 2;
still in time t.

So you are getting 2 signals calculated in the same time
(nearly) that it previously took to do 1.

Sounds mighty close to doubling your performance to me.

Mark you I guess the method, as it stands is no good if you
only have one waveform.

Regards

Dave Robinson

Regards

Dave Robinson

```
 0
Reply dave.robinson (1276) 8/9/2007 2:35:07 PM

3 Replies
33 Views

Similar Articles

12/7/2013 11:18:21 PM
[PageSpeed]