Re: [Discuss-gnuradio] Floating point FFT usage - suppress half of it?

[Maximilian Stiefel]

Hi Brad,
Hi Marcus,

@ Brad:

The basic properties of the Fourier transform give you this symmetry.
In general the Fourier transform has the following property, usually 
refered to as conjungation:

F{ x*(t) } = X*(-jw).

For purely real input signals, this boils down to

Xr(jw) = Xr(-jw) (even) and Xi(jw) = -Xi(-jw) (odd).
  ^                     ^
real part           imaginary part of the Fourier transform

For purely imaginary input signals, it boils down to

Xr(jw) = -Xr(-jw) (odd) and Xi(jw) = Xi(-jw) (even).
  ^                     ^
real part           imaginary part of the Fourier transform

Hence, you will always get a symmetric spectrum for a purely real or 
purely imaginary input, since purely real or purely imaginary signals 
need two frequencies (a positive and a negative one) to cancel out the 
imaginary part or the real part respectively 
(http://whiteboard.ping.se/SDR/IQ).

Think e.g. about a real cosine (even); it's Fourier transform will be 
real and even (two positive diracs at -w0 and w0). If you have a real 
sine (odd), the Fourier transform will be imaginary and odd (a positive 
dirac at w0 and a negative dirac at -w0).

If you think about a complex signal instead e.g. x(t) = A * e^{jw0t}. 
This will not yield a symmetric spectrum (one dirac at w0).

Thus, you can not really discard the negative frequencies if you want to 
be able to go back to time domain, but you can predict, what they are 
going to be. If you do an IFFT with the positive frequencies only, you 
will get rubbish at the output. You do not really waste CPU time if you 
calculate the full spectrum as it is just natural to obtain a result 
from the FFT which spans from -fs to fs (assuming you are sampling 
complex with fs). The negative frequencies are simply a part of a purely 
real signal, that you have in your case.

@ Marcus: The FFTW lib probably still needs to compute the negative 
bins, right?

As I understood it, correct me if I am wrong, you have to change physics 
to get around the negative frequencies to be calculated. Indeed, it is 
an interesting question, though.

Regards,

Max

On 2018-03-18 15:17, Müller, Marcus (CEL) wrote:
> Hi Brad,
>
> > Put another way, is it safe to
> > discard the left side of the output as it appears to consist only of
> > aliases of the true data?
>
> Well, it does not contain information that's not in the other side
> (it's not really an alias, though, but the conjugate mirror of the
> other side).
>
> > best way to recover the useful information from the FFT
>
> What's the thing you want to achieve? Because "useful" and "best" are
> meaningless without knowing what you want to do! :)
>
> Regarding the numerical inefficiency of computing both sides of
> something symmetric: The FFTW, the library used to actually compute
> these DFTs, does come with an effort-reduced FFT for real-valued input
> data, which will also only output one side of the spectrum.
> The savings in CPU cycles are usually relatively modest (because the
> non-hermitian FFT is already very optimized, and leaving out the
> results stage doesn't simply go and half the effort) – the main
> advantage would, in practice, probably be reduced memory bandwidth.
>
> But: audio sample rates on modern CPUs with FFTs of benign length might
> not really be what you should worry about computationally, I'd guess.
> What is the computational bottleneck you need to widen?
>
> Best regards,
> Marcus
>
> On Sun, 2018-03-18 at 09:29 -0400, Brad Hein wrote:
> > Frequency domain output of the FFT block seems to be mirrored when
> > using floating point data type. I recall that when using complex
> > numbers this mirroring doesn't occur. The input I'm working with is
> > 48khz sound from a wav file. I understand this mirroring is a
> > characteristic of the Fourier transform, but what I'm wondering is
> > what is the best way to recover the useful information from the FFT
> >
> > I tried marshaling the data into complex data before feeding it into
> > the FFT but I couldn't get a reliable process.
> >
> > If discarding half of the FFT output is the way to go then what about
> > the wasted CPU in calculating that half of the frequency domain - is
> > there a better way to recover the useful frequency domain
> > information?
> >
> > Thanks!
> >
> > _______________________________________________
> > Discuss-gnuradio mailing list
> > address@hidden
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >
> >
> > _______________________________________________
> > Discuss-gnuradio mailing list
> > address@hidden
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio